Паскаль. Основы программирования


Рекурсия


Такой процесс, когда в процедуре происходит обращение к самой себе, называется рекурсией

(рекурсия - возврат). (Происходит от латинского recurreus - возвращающийся).

Теперь нам предстоит более подробно поговорить о рекурсиях.

Рекурсия - это такой способ организации подпрограммы, при котором в ходе выполнения она обращается сама к себе.

Приведем примеры, которые уже стали классическими, использования рекурсий в подпрограммах:

 Пример 10. Вычисление факториала числа.

Ниже приведена программа вычисления факториала числа, в которой используется рекурсивная процедура fac:

   Procedure fac(n : integer; var f : real);

        begin

           if (n = 0) or (n = 1) then f := 1

                                           else

                                             begin

                                                fac(n - 1, f);

                                                f := f*n

                                             end

        end;

Разберемся детально в работе этой процедуры. Для этого снова обратимся к математике.

Для вычисления факториала числа n, т.е. n! надо умножить последовательно n натуральных чисел от 1 до n: 

 

Так, 4! будет равно:           

 

Это прямой путь вычисления или итеративный.

Возможен и другой путь вычисления:

 Этот путь можно назвать возвратным или рекурсивным.

Именно на этом принципе основана работа приведенной процедуры.

Пусть введено в программу значение 4 для вычисления факториала 4! Как будет работать процедура?

После начала ее работы, будет выполнена проверка:

if (n = 0) or (n = 1) then

f := 1

Понятно, что 4 не равно 0 и не равно 1, значит будет выполняться оператор после else, т. е. fac(n - 1, f), а это означает, что снова будет вызвана также процедура, но значение n уменьшится на единицу и станет равным 3; затем снова будет выполнена проверка условия:

        if

(n = 0) or (n = 1) then f  := 1 и переход к вызову процедуры fac(n - 1, f).

Значение n

уменьшится на 1 и станет равным 2 и т.


Начало  Назад  Вперед



Книжный магазин