Конспект лекций по программированию для начинающих. Гладков В.П. - 210 стр.

                                         212

    Чтобы понять, как будет выполняться эта программа, вспомним, что на время
выполнения вспомогательного алгоритма основной алгоритм приостанавливается.
При вызове новой копии рекурсивного алгоритма вновь выделяется место для всех
переменных, объявляемых в нем, причем переменные других копий будут
недоступны. При удалении копии рекурсивного алгоритма из памяти удаляются и
все его переменные. Активизируется предыдущая копия рекурсивного алгоритма,
становятся доступными ее переменные. Пусть необходимо вычислить 4! Основной
алгоритм: вводится n=4, вызов fact(4). Основной алгоритм приостанавливается,
вызывается и работает fact(4): 4<>1 и 4<>0, поэтому fact:=fact(3)*4. Работа
функции приостанавливается, вызывается и работает fact(3): 3<>1 и 3<>0, поэтому
fact:=fact(2)*3. Заметьте, что в данный момент в памяти компьютера две копии
функции fact. Вызывается и работает fact(2): 2<>1 и 2<>0, поэтому fact:=fact(1)*2.
В памяти компьютера уже три копии функции fact и вызывается четвертая.
Вызывается и работает fact(1): 1=1, поэтому fact(1)=1. Работа этой функции
завершена, продолжает работу fact(2). fact(2):=fact(1)*2 =1*2=2. Работа этой
функции также завершена, и продолжает работу функция fact(3).
fact(3):=fact(2)*3=2*3=6. Завершается работа и этой функции, и продолжает работу
функция fact(4). fact(4):=fact(3)*4= 6*4=24. Сейчас управление передается в
основную программу и печатается ответ: «Факториал 4 равен 24».
    Приведем еще несколько рекурсивных алгоритмов.
    Пример 13.6. Написать рекурсивную функцию, вычисляющую указанное число
Фибоначчи.
    Решение.       Последовательность           Фибоначчи          задается следующими
соотношениями: a(0)=a(1)=1, a(i)=a(i-1)+a(i-2), где i>1, которые легко записать на
Паскале в виде рекурсивной функции.
    function fib(n:integer):integer;
    begin     if n=0
              then fib := 1
              else if n=1
                      then fib := 1
                      else fib := fib(n-1)+fib(n-2)
    end;
    Пример 13.7. Написать рекурсивную функцию для вычисления квадрата
натурального числа.
    Решение. Известно, что (n+1)2=n2+2*n+1 и 12=1, отсюда
                                  ⎧1, если n = 1,
                        кв(n) = ⎨
                                  ⎩кв(n -1) + 2 ⋅ (n -1) + 1, если n > 1.
    Отсюда
    function kv(i:integer):integer;
    begin     if i=1
              then kv := 1
              else kv := kv(i-1)+2*(i-1)+1
    end;
    Пример 13.8. Написать рекурсивную функцию сложения целых чисел.