13.6. Индукция. Рекурсия. Стек

Начнем с классического примера о факториале. Факториалом целого положительного числа N называется произведение всех целых чисел от 1 до N. Например, факториал пяти равен 1*2*3*4*5, то есть 120. Факториал единицы считается равным 1.

Все понятно. Однако существует еще один способ объяснения, что такое факториал:

"Факториал единицы равен 1. Факториал любого целого положительного числа N, большего единицы, равен числу N, умноженному на факториал числа N-1".

Чтобы последнее предложение было понятно, возьмем какое-нибудь конкретное N, например 100. Тогда это предложение будет звучать так: "Факториал числа 100 равен числу 100, умноженному на факториал числа 99".

Чему же равен какой-нибудь конкретный факториал, скажем факториал трех? Будем рассуждать образом:

Смотрим в определение: "Факториал трех равен 3 ум-

ножить на факториал двух". Не знаем, сколько это.

Спускаемся на ступеньку ниже.

Смотрим в определение: "Факториал двух равен 2 ум-

ножить на факториал единицы". Не знаем, сколько это

Спускаемся еще на ступеньку.

Смотрим в определение: "Факториал единицы равен 1".

Вот, впервые конкретное число. Значит, можно под-

ниматься.

Поднимаемся на одну ступеньку. Факториал двух равен

2 умножить на 1, то есть 2.

Поднимаемся еще на ступеньку. Факториал трех равен

3 умножить на 2, то есть 6. Задача решена.

Рассуждая таким образом, можно вычислить факториал любого числа. Способ рассуждения называется рекурсивным, а способ объяснения называется индуктивным.

Какое отношение все это имеет к компьютерам? Дело в том, что рекурсивный способ рассуждений реализован во многих языках программирования, в том числе и в Паскале. Значит, этим языкам должен быть понятен и индуктивный способ написания программ.

Обозначим кратко факториал числа N как Factorial(N) и снова повторим наш индуктивный способ объяснения:

"Если N=1, To Factorial(N) = 1.

Если N>1, то Factorial(N) вычисляется умножением N на Factorial(N-1)."

В соответствии с этим объяснением напишем на Паскале функцию Factorial для вычисления факториала:

FUNCTION Factorial(N: Byte): LongInt;

BEGIN

if N=1 then Factorial:=1;

if N>1 then Factorial :=N* Factorial(N-1)

END;

BEGIN

WriteLn(Factorial(3))

END.

Обратите внимание, что в программе нигде не употребляется оператор цикла. Вся соль программы в том, что функция Factorial вместо этого включает в себя вызов самой себя - Factorial(N-1).

Что же происходит в компьютере во время выполнения программы? Механизм происходящего в точности соответствует нашему рассуждению по рекурсии.

Все начинается с того, что Паскаль пробует выполнить строкуWriteLn(Factorial(3)). Для этого он вызывает функцию Factorial. Выполнение подпрограммы начинается с того, что в стеке отводится место для всех формальных параметров и локальных переменных, а значит, и для нашего формального параметра N. Затем фактический параметр 3 подставляется на место формального параметра N, то есть в стек, в ячейку N, посылается 3. Затем выполняется тело функции. Так как3>1, то Паскаль пытается выполнить умножение 3* Factorjal(3-1) и сталкивается с необходимостью знать значение функции Factorial(2), для чего вызывает ее, то есть отправляется ее выполнять, недовыполнивFactorial(3), но предварительно запомнив, куда возвращаться.

Спускаемся на ступеньку ниже. В соседнем месте стека отводится место для N. Это уже другое N, путать их нельзя. В эту ячейку N посылается 2. Затем выполняется тело функции. Пусть вас не смущает, что Паскаль второй раз выполняет тело функции, не закончив его выполнять в первый раз. Так как 2>1, то Паскаль пытается выполнитьумножение 2* Factonal(2-1) и сталкивается с необходимостью знать значение функции Factonal(1), для чего вызывает ее.

Спускаемся еще на ступеньку. В соседнем месте стека отводится место еще для одного N. В эту ячейку N посылается 1. Затем выполняется тело функции. Так как 1=1, то Паскаль вычисляет Factorial =1. Вот впервые конкретное число. Затем Паскаль пытается выполнить следую щую строку if N>1 then Factorial :=N* Factorial(N-l). Поскольку нельзя сказать, что 1>1, то выполнение тела функции закончено. Значит, можно подниматься.

Поднимаемся на одну ступеньку. Паскаль возвращается внутрь тела функции (той, где N=2) и успешно выполняет умножение Factorial :=2*1=2.

Поднимаюсь еще на ступеньку. Паскаль возвращается внутрь тела функции (той, где N=3) и успешно выполняет умножение - Factorial :=3*2=6. Задача решена.

После выхода из подпрограммы место в стеке освобождается.

Итак, рекурсией в программировании называется вызов подпрограммы из тела самой подпрограммы.

Задание 124

Напишите рекурсивную функцию fib для вычисления чисел Фибоначчи.