Подпрограммы в Паскале могут обращаться сами к себе. Такое обращение называется рекурсией.
Для того чтобы такое обращение не было бесконечным, в тексте подпрограммы должно быть условие, по достижению которого дальнейшее обращение к подпрограмме не происходит.
Программист разрабатывает программу, сводя исходную задачу к более простым. Среди этих задач может оказаться и первоначальная, но в упрощенной форме. Например, для вычисления F( N) может понадобиться вычислить F( N-1). Иными словами, частью алгоритма вычисления функции будет вычисление этой же функции.
Пример рекурсивной функции вычисления факториала
Function factorial(N: integer) : longint;
Begin
If N= 0 then
Factorial := 1
Else Factorial := factorial(N-1) * N
End;
Это может показаться удивительным, но самовызов процедуры ничем не отличается от вызова другой процедуры. Что происходит, если одна процедура вызывает другую? В общих чертах следующее:
- в памяти размещаются параметры, передаваемые процедуре (но не параметры-переменные!);
- в другом месте памяти сохраняются значения внутренних переменных вызывающей процедуры;
- запоминается адрес возврата в вызывающую процедуру;
- управление передается вызванной процедуре.
Если процедуру вызвать повторно из другой процедуры или из нее самой, будет выполняться тот же код, но работать он будет с другими значениями параметров и внутренних переменных. Это и дает возможность рекурсии.
Пусть рекурсивная процедура Power( X, N, Y) возводит число X в степень N и возвращает результат Y .
Пример рекурсивной процедуры, возводящей число в степень
Procedure Power (X: real; N: integer; var Y: real);
Begin
If N=0 then
Y:= 1
Else Begin Power(X, N-1,Y);
Y:= Y*X;
End ;
End ;
