Рекурсия и не только

Рекурсия предполагает решение задачи с помощью подпрограмм (процедуры или функции) с обязательным вызовом самой себя  внутри кода. Например, вы открываете сумку, достаете кошелку, открываете ее, достаете кошелек, открываете и достаете деньги, чтобы оплатить проезд, получаете билет и сдачу, и проделываете обратную процедуру: деньги в кошелек, кошелек в кошелку, кошелка в сумку. Или другой пример: открытие матрешек или, например, дверей в проходе по коридору царского дворца. Можно придумать еще много ассоциаций, но суть будет одна: нужно каждый раз что-то "открывать" (вызывать подпрограмму) до тех пор, пока не встретится искомое решение или не выполнится какое-то условие (условие останова или возврата). Вроде все просто и понятно.
Но есть подводные камни: такой алгоритм не может быть достаточно долгим или бесконечным, так как память компьютера конечна, и может возникнуть сообщение "Stack overflow". Такой алгоритм похож на некое подобие сбора и разбора пирамидки, так как он организуется по принципу стека (первый вошел, последним вышел). Таким образом стековая память заполняется этими "кодами подрограмм" - еще не завершен первый код, как уже вызывается следующий и т.д. Кроме этого в подпрограммах передаются параметры, которые тоже требуют размещения в памяти компьютера каждый раз при вызове подпрограммы и висит там до тех пор, пока подпрограмма не завершится. Т.е. нужно иногда думать не только как организовать рекурсию, но и какие параметры туда стоит передавать, а какие достаточно объявить глобально. Непростая задача даже для опытного программиста!!! Что же делать начинающим?

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

Но наша цель не использование готовых решений, а самостоятельное их нахождение.

Разберем простой пример: вычисление факториала (это произведение первых n натуральных чисел). Его можно записать так: f:=n*f(n-1), если n>0 и f:=1, если n=0.
Оформим рекурсию в виде функции:
function f(n:longint):longint;
begin
  if n=0 then f:=1 {условие останова}
         else f:=f(n-1)*n; {рекурсивный вызов функции}
end;
Итак, покажем как рекурсивно вызывается код подрограммы при вызове функции F(4):

1. n=4, вызов F(3) в формуле F:=F(n-1)*n;
2. n=3, вызов F(2) в формуле F:=F(n-1)*n;
3. n=2, вызов F(1) в формуле F:=F(n-1)*n;
4. n=1, вызов F(0) в формуле F:=F(n-1)*n;
5. n=0, и только теперь F:=1.
6. Теперь "собираем матрешку". Возвращаемся в подпрограмму п. 4 и вместо F(0) подставим 1 в формулу F:=F(n-1)*n; получим следующее выражение F:=1*1=1.
7. Возвращаемся в подпрограмму п. 3 и вместо F(1) подставим 1 в формулу F:=F(n-1)*n; получим следующее выражение F:=1*2=2.
8. Возвращаемся в подпрограмму п. 2 и вместо F(2) подставим 2 в формулу F:=F(n-1)*n; получим следующее выражение F:=2*3=6.
9. Возвращаемся в подпрограмму п. 1 и вместо F(3) подставим 6 в формулу F:=F(n-1)*n; получим следующее выражение F:=6*4=24.
10. Возвращаемся в точку вызова функции F(4) и получаем в результате число 24.

Я расписала подробно саму процедуру вызова и возврата, чтобы затем было проще представлять алгоритмы в виде рекурсивных подпрограмм.
Но этот пример не используется в программировании. Вместо этого используют обычный алгоритм вычисления произведения в цикле:
F:=1;
For i:=1 to n do 
  F:=F*i;
В цикле используется рекуррентное соотношение, когда следующее значение переменной относительно предыдущего изменяется на некоторую величину.
Такие соотношения используются и в вычислениях суммы ряда, где есть факториалы и степени. При этом не надо вычислять сами факториалы, достаточно определить изменяемую величину и вставить ее вместо переменной i в предыдущем примере. Например, вычислить сумму ряда для a[n]=x^n/n!. Получим нужный множитель из формулы a[n+1]=I*a[n], где a[n+1]=x^(n+1)/(n+1)! => I=a[n+1]/a[n]=x^n/n! /(x^(n+1)/(n+1)!)= (n+1)/x. Итак, наш код будет выглядеть так:

F:=1; {при n=0, a[0]=x^0/0!=1/1=1}
For i:=1 to n do 
  F:=F*(i+1)/x;

В литературе приводится пример нахождения наибольшего общего делителя двух чисел:
                      HOД(m-n, n), если m>n 
НОД(m, n) = HOД(n-m, m), если n>m
                      m, если m=n 
Приведем пример функции:
Function HOD(m,n:longint):longint;
begin
  if m=n then HOD:=m
         else if m>n then HOD:=HOD(m-n,n)
                     else HOD:=HOD(n-m,m); 
end; 
Сравнивая две функции НОД(m,n) и F(n) можно заметить, что в начале кода всегда проверяется условие останова и возвращается то значение, которое не имеет вызова функции,  а только потом используются формулы с рекурсивным вызовом.
Практически после получения формулы для расчета НОД(m,n) и F(n) можно сразу написать по ней рекурсивную функцию.
В функции HOD вместо вычисления разности можно использовать операцию mod.
Эту функцию можно использовать для вычисления НОД нескольких переменных, используя тот факт, что НОД (m,n,c)=НОД(НОД(m,n),c). Попробуйте не использовать рекурсивную функцию в этом случае. Замените ее циклом.
Также можно использовать эту функцию для вычисления НОК(m,n)=m*n/HOД(m,n).

Приведем формулу для возведение числа a в степень натурального положительного n:

                   SQR (Stepen(n div 2)), если n  четное

Stepen(n) = Stepen(n -1)*a, если n нечетное
                   1, если n=0
Приведем пример применения формулы для n=10: a^10 = (a^5)^2 = (a*a^4)^2 = (a*(a^2)^2)^2 = (a*((a^1)^2)^2)^2 = (a*((a*a^0)^2)^2)^2 = (a*((a*1)^2)^2)^2. Напишите сами рекурсивную функцию. Для проверки нечетности можно использовать функцию ODD(n).

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