Формы рекурсивных процедур
End.
PopeAndDog2
Begin
End;
PopeAndDog2;
Begin
Procedure PopeAndDog2;
Writeln('y попа была собака, он ее любил.');
Writeln('Oнa съела кусок мяса, он ее убил,');
Writeln('похоронил и надпись написал:');
то такая программа ничего не напечатает, хотя и будет работать также бесконечно, как и первая. Это объясняется тем, что оператор вызова процедуры стоит первым и, соответственно, вызов новой копии процедуры PopeAndDog2 произойдет раньше, чем вывод текста. В следующей копии процедуры будут сделаны аналогичные действия, и так далее. В результате произойдет бесконечный вызов процедуры PopeAndDog2 без какого-либо вывода текста, хотя оператор вывода в процедуре присутствует. В действительности при исполнении на компьютере такой бесконечный вызов приводит к переполнению стека и возникновению ошибки времени исполнения.
Программы, в которых используются рекурсивные процедуры, отличаются простотой, наглядностью и компактностью текста. Такие качества рекурсивных алгоритмов вытекают из того, что рекурсивная процедура указывает, что нужно делать, а не рекурсивная больше акцентирует внимание на том, как нужно делать.
Однако за эту простоту приходится расплачиваться неэкономным использованием оперативной памяти, так как выполнение рекурсивных процедур требует значительно большего размера оперативной памяти во время выполнения, чем не рекурсивных. При каждом рекурсивном вызове для локальных переменных, а также для параметров процедуры, которые передаются по значению, выделяются новые ячейки памяти. Максимальное число рекурсивных вызовов процедуры без возвратов, которое происходит во время выполнения программы, называется глубиной рекурсии. Число рекурсивных вызовов в каждый конкретный момент времени, называется текущим уровнем рекурсии.
В общем случае любая рекурсивная процедура Rec включает в некоторое множество операторов S и один или несколько операторов рекурсивного вызова.
Как было показано на предыдущем шаге, безусловные рекурсивные процедуры приводят к бесконечным процессам, и на эту проблему нужно обратить особое внимание, так как практическое использование процедур с бесконечным самовызовом невозможно. Такая невозможность вытекает из того, что для каждой копии рекурсивной процедуры необходимо выделить дополнительную область памяти, а бесконечной памяти не существует.
Следовательно, главное требование к рекурсивным процедурам заключается в том, что вызов рекурсивной процедуры должен выполняться по условию, которое на каком-то уровне рекурсии станет ложным.
Если условие истинно, то рекурсивный спуск продолжается. Когда оно становится ложным, то спуск заканчивается и начинается поочередный рекурсивный возврат из всех вызванных на данный момент копий рекурсивной процедуры.
Структура рекурсивной процедуры может принимать три разных формы:
1. Форма с выполнением действий до рекурсивного вызова (с выполнением действий на рекурсивном спуске):