Рекурсивные функции

Известно, что рекурсия есть способ определения значения функции в некоторой точке через известные значения этой функции в других, предшествующих точках. Очевидно, что в каждой точке должен быть задан набор значений аргументов данной функции, а в некоторой исходной точке – значение самой функции.

В тех случаях, когда речь идет о числовых функциях, области определения и значения которых заданы на множестве целых неотрицательных чисел, это описание рекурсии задает способ вычисления численных значений определяемой функции для заданного набора числовых значений аргументов и числовых значений этой функции в исходной точке.

Числовые функции, для которых существует алгоритм вычисления их значений, называют рекурсивными функциями.

Если числовая функция определена не для всех значений аргументов, ее называют частично рекурсивной функцией. Если для всех значений – то общерекурсивной функцией.

Иследование алгоритмов на множестве рекурсивных функций оправдано тем, что любое вещественное число может быть представлено цепочкой <целое> «.»<целое>, для которой существует только одна синтаксическая переменная – <целое>. Следовательно, любую функцию можно свести к рекурсивной, если значения аргументов и значения функции рассматривкать принадлежащими синтаксической переменной <целое>.

Последовательность функциональных равенств, описывающих по шагам дискретный процесс вычисления числовой функции от ее исходного значения при заданных значениях независимых переменных аргумента, называют рекурсивным описанием, или протоколом.

Формализм вычисления является универсальной моделью описания последовательности шагов в реализации алгоритма.

Для этой модели должны быть заданы наборы элементарных объектов и элементарных действий в описании механизма реализации алгоритма. Такими элементарными объектами являются три базовые функции, а элементарными действиями – три элементарных операции.