И коммуникаций республики узбекистан

10. Рекурсивные алгоритмы и их функции

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

Определение рекурсивной функции имеет один или несколько базовых случаев, то есть есть входные данные, для которых функция выдает результат тривиально (без повторения), и один или несколько рекурсивных случаев, что означает ввод (ы) для программы повторения (вызывает себя). Например, функция факториала может быть определена рекурсивно уравнениями 0! = 1 и для всех n>0 n! = п (п - 1)!. Ни одно уравнение само по себе не составляет полного определения; первый - базовый, второй - рекурсивный. Временный базовый случай разрывает цепочку рекурсии, его иногда также называют «завершающим случаем».

Работа с рекурсивными случаями можно рассматривать как разбиение сложных входных данных на более простые. В спроектированной рекурсивной функции при каждом рекурсивном вызове проблема ввода должна быть упрощена таким образом, чтобы в итоге был достигнут базовый случай правильно. (Функции, которые не предназначены для завершения при нормальных обстоятельствах - например, некоторые системные и серверные процессы являются исключением из этого правила.) Пренебрежение написано базовым вариантом или его неправильное тестирование может вызвать бесконечный цикл .
Для некоторых функций (например, для вычислений серии для e = 1/0! + 1/1! + 1/2! + 1/3! + ...) входные данные не подразумевают очевидного базового случая; для них можно добавить параметр (например, добавляемых терминов в нашем примере серии), чтобы использоватьколичество «критерий остановки», который устанавливает базовый случай. Такой пример более естественно в corecursion , где последовательные члены выходных данных являются частичными суммами; это можно преобразовать в рекурсию, используя параметр индексации, чтобы сказать «вычислить n-й член (n-я частичная сумма)».