Pascal. Подпрограммы. Рекурсия


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

Если вспомнить математику, то там можно встретить принцип математической индукции. Он заключается в следующем:

Некоторое утверждение справедливо для всякого натурального n, если
    1. оно справедливо для n = 1 и
    2. из справедливости утверждения для какого-либо произвольного натурального n = k следует его справедливость для n = k+1.

В программировании этот прием называют рекурсией

Рекурсия - это способ определения множества объектов через само это множество на основе заданных простых базовых случаев.

Рекурсивной же будет называться процедура (функция), которая вызывает саму себя напрямую или через другие процедуры и функции
Пример рекурсивной процедуры: 
procedure Rec(a: integer);
begin
    if a > 0 then
        Rec(a - 1);
    write(a);
end;
Схематично работу рекурсии можно изобразить блок-схемой

 
Процедура Rec() выполняется с параметром 3. Затем в внутри процедуры с параметром 3 вызывается процедура с параметром 2 и т.д., пока не произойдет вызов процедуры с параметром 0. При вызове процедуры с параметром 0 рекурсивного вызова уже не произойдет и процедуры с параметром 0 напечатает число 0 и закончит работу. Затем управление передается обратно в процедуру с параметром 1, она также заканчивает свою работу печатает число 1 и т.д. до процедуры с параметром 3. 

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

Задача для тренировки:

Рекурсия. Что это?

Мы увидели, что рекурсия - это повторное выполнение содержащихся команд в подпрограмме. А это в свою очередь аналогично работе цикла. Существуют языки программирования, в которых конструкция цикла отсутствует вовсе, например, Пролог. 
Попробуем сымитировать работу цикла for. 
Цикл for содержит переменную-счетчик шагов. В рекурсивной подпрограмме такую переменную можно передавать в качестве параметра. 
//Процедура LoopImitation() с двумя параметрами
//Первый параметр – счетчик шагов, второй параметр – общее количество шагов
procedure LoopImitation(i, n: integer);
begin
    writeln('Hello N ', i); // Оператор, который необходимо повторить при любом значении i
    if i < n then //Пока счетчик цикла не станет равным значению n,
        LoopImitation(i + 1, n); //вызываем новый экземпляр процедуры, с параметром i+1 (переход к следующему значению i)
end;

Задача для тренировки:

Рекурсия. Имитация работы цикла

Чтобы понять рекурсию, надо понять рекурсию...
 
Итерация в программировании — в широком смысле — организация обработки данных, при которой действия повторяются многократно, не приводя при этом к вызовам самих себя (в отличие от рекурсии). В узком смысле — один шаг циклического процесса обработки данных. 
Часто итерационные алгоритмы на текущем шаге (итерации) используют вычисленный на предыдущих шагах результат такой же операции или действия.  Одним из примеров таких вычислений служат вычисления рекуррентных соотношений. 
Простым примером величины, вычисляемой с помощью рекуррентных соотношений, является факториал: \(N!=1 \cdot 2 \cdot 3 \cdot \ ... \ \cdot N\)
Вычисление значения на каждом шаге (итерация) это \(N=N \cdot i\) .  При вычислении значения \(N\), мы берем уже сохраненное значение \(N\).

Факториал числа можно также описать с помощью рекуррентной формулы:



Можно заметить, что это описание является не чем иным, как рекурсивной функцией.
Здесь первая строка (\(n <= 1\)) — это базовый случай (условие окончания рекурсии), а вторая строка - переход к следующему шагу. 
 
Рекурсивная фнкция вычисления факториала будет выглядеть следующим образом Сравните алгоритм нахождения факториала обычным, не рекурсивным способом
function Factorial(n: integer): integer;
begin
    if n > 1 then
        Factorial := n * Factorial(n - 1)
    else
        Factorial := 1;
end;		 x := 1;
for i := 2 to n do
    x := x * i;
writeln(x);

Следует понимать, что вызов функций влечет за собой некоторые дополнительные накладные расходы, поэтому не рекурсивный вариант вычисления факториала будет несколько более быстрым. 
Вывод: там, где можно написать программу простым итерационным алгоритмом, без рекурсии, то надо писать без рекурсии. Но все таки существует большой класс задач где вычислительный процесс реализуется только рекурсией.
С другой стороны - рекурсивные алгоритмы чаще всего более понятны.
 

Задача для тренировки:

Рекурсия и итерации