Рекурсивні функції.Основна гіпотеза теорії алгоритмів

Рекурсією називається такий спосіб організації обробки даних, при якому програма (або функція) викликає сама себе або безпосередньо, або з інших програм (функцій).

Функція називається рекурсивною, якщо під час її обробки виникає її повторний виклик, або безпосередньо, або побічно, шляхом ланцюжка викликів інших функцій.

Рекурсивні функції — клас функцій, введений як уточнення класу обчислюваних функцій. В математиці загальноприйнятою є теза про те, що клас функцій, для обчислення яких існують алгоритми, при найширшому розумінні алгоритму, збігається з класом рекурсивних функцій. У зв'язку з цим, рекурсивні функції грають важливу роль в математиці та її застосуваннях, в першу чергу, в математичній логіці, основах математики та кібернетиці, як ефективно обчислювані функції. Тільки такі функції можна обчислювати на електроних обчислювальних машинах та інших цифрових пристроях.

При введенні класу ефективно обчислюваних функцій природнім чином виникає питання уточнення конструктивних об'єктів, на яких визначено ці функції. Клас всіх таких об'єктів широкий. В той же час, з допомогою методу арифметизації, запропонованого австрійським математиком Куртом Геделем, всі такі об'єкти легко зводяться донатуральних чисел. Тому рекурсивні функції було введено як функції, що визначені на множині натуральних чисел і набувають значення з тієї ж множини натуральних чисел. Перенесення понять і методів вироблених в теорії рекурсивних функцій на функції визначені на складніших конструктивних областях (множини слів деякого алфавіту, формул деякої теорії, графів тощо) не створює принципових ускладнень.

Базовими примітивними функціями, за визначенням, є:

1. нульова функція

2. функція слідування

3. функція проектування

Перед написанням рекурсивних функцій на будь-якій мові програмування, як правило, необхідно записати рекурентне співвідношення, що визначає метод обчислення функцій. Рекурентне співвідношення повинне містити як мінімум дві умови:

I) умова продовження рекурсії (крок рекурсії);

II) умова закінчення рекурсії.

Рекурсію реалізовуватимемо за допомогою виклику функції самої себе. При цьому в тілі функції спочатку слід перевіряти умову закінчення рекурсії. Якщо вона істинна, то виходимо з функції. Інакше здійснюємо рекурсивний крок. Ітеративний варіант функцій реалізовуватимемо за допомогою оператора циклу for.