#22 Рекурсия. Рекурсивные вызовы, функции и процедуры в Паскаль

Рекурсия вообще

Для начала скажем, что "рекурсия вообще" это явление в реальности, когда что-то повторяет само себя, причем обычно каким-то "вложенным" образом.

Рекурсия может быть "статической", как повторение формы целого в его частях, например так:

или так:

Но к программированию намного больше подходит иллюстрация "динамическое погружение" раз за разом "само в себя", это неплохо иллюстрируют gif-анимации, например:

Или в трехмерном пространстве (двигаясь по пространству переходим к него же и так раз за разом):

Рекурсия в программировании

Как написано в нашем "Словаре программиста":
Рекурсия -- приём в программировании, когда некоторый модуль программы (фукция, метод) вызывают сами себя.
Такой вызов называет рекурсивным ("самовызов").

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

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

Рекурсивная продпрограмма - такая подпрограмма, в чем теле содержится её собственный вызов.

На псевдокоде такая подпрограмма может выглядеть как-то так:

function имяМоейФункции(входящиеАргументы);
begin
    имяМоейФункции(аргументыРекурсивногоВызова);
end.

-- цель этого примера просто пояснить как именно подпрограмма может вызывать "саму себя".
Подробности рассмотрим далее.

Рекурсия не бесконечна. Условие выхода из рекурсии

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

Таким образом, функция которая сможет работать в реальной системе скорее описывается не так:

function имяМоейФункции(входящиеАргументы);
begin
    имяМоейФункции(аргументыРекурсивногоВызова);
end.

а так:

function имяМоейФункции(входящиеАргументы);
begin
    if (условие)
       имяМоейФункции(аргументыРекурсивногоВызова);
end.

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

Рассмотрим примеры, чтобы внести ясность

Примеры кода -- разбор решений

Пример №1. Возведение числа в степень

Напишем функцию возводящую число в степень в рекурсивном стиле:

function pow(
  i, // число, которое будем возводить в спепень
  s  // значение степени
  :integer):integer;
begin
   if (s = 0) then
     result := 1 // любое число в степени 0 это 1
   else if (s = 1) then
     result := i // в степени один само же число
   else
     result := i * pow(i, s-1); { рекурсивный вызов
     со степенью уменьшенной на 1}
end;

begin
    writeln(pow(2, 3));
    readln();
end.
    

-- обратите внимание, что рекурсия здесь начинает "раскручиваться" в обратную сторону, как только при очередном вызове s становится равной 1, т.е. по коду видно, что так как на каждый очередной вызов мы передаем s в уменьшенном виде:

 result := i * pow(i, s-1);

то рано или поздно на очередном рекурсивном вызове переменная s станет равной 1, при этом:

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

Задачи для самостоятельного решения

1. Дано целое положительное число $N$. Выведите на экран все число от $N$ до 1 (по убыванию).
2. Дано целое положительное число $N$. Выведите на экран все число от 1 до $N$ (по возрастанию).
3. Дано целое положительное число $A$ и целое положительно число $B$. Выведите на экран все числа, расположенные между между ними.
4. Дано целое положительное число $N$, вычислите $N!$ (эн факториал).
5. Пользователь получает на вход целое положительное число N напишите рекурсивную процедуру, которая выведет все числа Фиббоначи от первого до N-ого
6. Пользователь получает на вход целое положительное число N напишите рекурсивную функцию, которая вернет число Фиббоначи стоящии под этим номером
7. Дано натуральное число N. Вычислите сумму его цифр.

   
   (При решении этой задачи нельзя использовать строки, списки, массивы (ну и циклы, разумеется). Разрешена только рекурсия и целочисленная арифметика. Используйте операцию получения остатка от деления, и операцию целочисленного деления).

8. "Калькулятор":
   Напишите функцию, которая получает на вход произвольную строку вида:

   5*(3+4)-7*9+3*(2+(2-7))

   (арифметическое выражение со скобками любого уровня вложенности и операциями умножения, вычитания и сложения)

   и в качестве ответа возвращает результат этого выражения.

   Рекомендация: сначала убедитесь, что число открывающих скобок, равно числу закрывающих.

   Примечание: алгоритмически похожая задача использовалась на собеседовании стажеров в DataArt.

   Подсказки:

   • Базовая идея решения задачи "выражение со скобками": https://youtu.be/n7NqWnXQc5w