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

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

var a: integer;

procedure reverse(n: integer);
    begin
        write(n mod 10);
        if (n div 10) <> 0 then
            reverse(n div 10)
    end;
 
begin
    readln(a);
    
    reverse(a); 

    writeln;
end.

Пример выполнения:

3096
6903

В приведенном примере процедура reverse выводит цифры, переданного ей в качестве фактического параметра числа, в обратном порядке. Т.е. если мы передаем число 35, то процедура выведет на экран число 53. Рассмотрим, как она это делает:

1. Мы передаем число 3096.
2. Процедура reverse выводит на экран остаток от деления на 10. Это число 6.
3. Переход на новую строку не происходит, т.к. используется write.
4. Проверяется условие того, что 3096 при деление нацело на 10 больше нуля.
5. Вызывается reverse с фактическим параметром, равным 309.
6. Вторая запущенная процедура выводит на экран цифру 9 и запускает третью процедуру с параметром 30.
7. Третья процедура выводит 0 и вызывает четвертый reverse с 3 в качестве параметра.
8. Четвертая процедура выводит 3 на экран и ничего больше не вызывает, т.к. условие (3 div 10) <> 0 ложно.
9. Четвертая процедура завершается и передает управление третьей.
10. Третья процедура завершается и передает управление второй.
11. Вторая процедура завершается и передает управление первой.
12. Первая процедура завершается и передает управление в основную ветку программы.

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

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