|
Навигация
|
|||||
|
Оглавление
|
|||||
| Рекурсивные подпрограммы В ряде приложений алгоритм решения задачи требует вызова подпрограммы из раздела операторов той же самой подпрограммы, т.е. подпрограмма вызывает сама себя. Такой способ вызова называется рекурсией. Рекурсия полезна прежде всего в тех случаях, когда основную задачу можно разделить на подзадачи, имеющие ту же структуру, что и первоначальная задача. Подпрограммы, реализующие рекурсию, называются рекурсивными. Для понимания сути рекурсии лучше понимать рекурсивный вызов как вызов другой подпрограммы. Практика показывает, что в такой трактовке рекурсия воспринимается значительно проще и быстрее. Приведенная ниже программа содержит функцию Factorial для вычисления факториала. Напомним, что факториал числа определяется через произведение всех натуральных чисел, меньших либо равных данному (факториал числа 0 принимается равным 1): X! = 1 * 2 * ... * (X - 2) * (X - 1) * X Из определения следует, что факториал числа X равен факториалу числа (X - 1), умноженному на X. Математическая запись этого утверждения выглядит так: X! = (X - 1)! * X, где 0! = 1 Последняя формула используется в функции Factorial для вычисления факториала:
{$APPTYPE CONSOLE} uses function Factorial(X: Integer): Longint; begin При написании рекурсивных подпрограмм необходимо обращать особое внимание на условие завершения рекурсии, иначе рекурсия окажется бесконечной и приложение будет прервано из-за ошибки переполнения стека. Бывает встречается такая рекурсия, когда первая подпрограмма вызывает вторую, а вторая - первую. Такая рекурсия называется косвенной. Очевидно, что записанная первой подпрограмма будет содержать еще неизвестный идентификатор второй подпрограммы (компилятор не умеет заглядывать вперед). В результате компилятор сообщит об ошибке использования неизвестного идентификатора. Эта проблема решается с помощью упреждающего (предварительного) описания процедур и функций. |
