Рекурсия

Дата публикации

Здравствуйте. Сегодня мы разберемся с рекурсией. Начнем с определения.

Определение рекурсии (в программировании).

Рекурсия – способ организации программы, при котором функция или процедура вызывает сама себя. Другими словами это вызов процедуры (функции) из неё же самой – простая рекурсия или же через другие процедуры (функции) – сложная (косвенная) рекурсия.
Чаще всего всю силу рекурсии демонстрируют с помощью вычисления факториала. Я же приведу пример возведения числа в любую степень.

Функция будет следующая:

function power (x,y:integer):integer;
begin
    if y=0 then 
    Result:=1
    else 
    Result:=x*power(x,y-1);
end;

Параметр «х» - число, которое возводим, «y» - степень. Давайте на примере посмотрим, как это работает.
Допустим, что нам нужно возвести 2 в 3 степень, для этого запишем:

power(2,3);


Попробуем словами воспроизвести поведение нашей функции. 

Итак? мы попадаем в тело функции, значение x = 2, y = 3. Так как «y» не равен 0, по условию мы переходим в блок else. Это значит, что должен выполниться код:
Result:=x*power(x,y-1); //что равносильно 2*power(2,2)
Получается, что мы снова попадаем в функцию power, но уже с параметрами: x=2, y=2(н уменьшился на 1). По условию (if y=0 then) мы снова попадаем в блок else, где в итоге выполняем power(x,y-1), что эквивалентно, в нашем случае, 2*power(2,1).
И ещё разок. Выполняем power(2,1). По условию 1 не равно 0 и мы получаем 2*power(2,0). Вот тут и происходит кульминация. В процедуре мы попадаем под условие (if y=0 then) и в результате функция возвращает 1. Это значит, что мы больше не будем обращаться к функции power.

В результате мы получили следующее выражение:

Power(2,3) =2 * power(2,2)= 2 * 2 * power(2,1)=2*2*2* power(2,0)=2 * 2 *2 *1= 8

Для того чтобы все окончательно осознать, я бы порекомендовал разобрать какой-либо пример самостоятельно. Допустим уже упомянутый факториал. Если будут вопросы – пиши, будем разбирать вместе.

Добавить комментарий



Обновить

Thursday the 14th. icq 486350790
Copyright 2012

©