2 Рекурсивная реализация алгоритмов

Большинство современных языков высокого уровня поддерживают механизм рекурсивного вызова, когда функция, как элемент структуры языка программирования, возвращающая вычисленное значение по своему имени, может вызывать сама себя с другим аргументом. Эта возможность позволяет напрямую реализовывать вычисление рекурсивно определенных функций. Отметим, что в силу тезиса Черча-Тьюринга аппарат рекурсивных функций Черча равномощен машине Тьюринга, и, следовательно, любой рекурсивный алгоритм может быть реализован итерационно.Анализ трудоемкости рекурсивных реализаций алгоритмов, очевидно, связан как с количеством операций, выполняемых при одном вызове функции, так и с количеством таких вызовов. Графическое представление порождаемой данным алгоритмом цепочки рекурсивных вызовов называется деревом рекурсивных вызовов. Более детальное рассмотрение приводит к необходимости учета затрат как на организацию вызова функции и передачи параметров, так и на возврат вычисленных значений и передачу управления в точку вызова.

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

ЧЁРЧА ТЕЗИС

- принцип, согласно  которому класс функций, вычислимых с помощьюалгоритмов в широком интуитивном смысле, совпадает с классом частично рекурсивных функций. Ч. т.- этоестественнонаучный факт, подтверждаемый опытом, накопленным в математике за всю ее историю. Всеизвестные в математике примеры алгоритмов удовлетворяют ему. Ч. т. впервые был высказан А. Чёрчем (A.Church, 1936). Различным уточнениям интуитивного понятия алгоритма соответствуют свои формулировки Ч.т. Тезис Тьюринга заключается в том, что всякая вычислимая в интуитивном смысле функция вычислима спомощью нек-рой Тьюринга машины, апринцип нормализации Маркова - в том, что всякая вычислимая винтуитивном смысле функция вычислима с помощью нек-рого нормального алгорифма. Из эквивалентностиизвестных уточнений понятия алгоритма следует эквивалентность соответствующих вариантов Ч. т. Этотфакт является еще одним подтверждением Ч. т. Тезис Чёрча не может быть строго доказан, так как в егоформулировке участвует неточное понятие лалгоритм в интуитивном смысле