С++ для начинающих

       

Рекурсия


Функция, которая прямо или косвенно вызывает сама себя, называется рекурсивной. Например:

int rgcd( int vl, int v2 )

{

    if ( v2 != 0 )

        return rgcd( v2, vl%v2 );

    return vl;

}

Такая функция обязательно должна определять условие окончания, в противном случае рекурсия будет продолжаться бесконечно. Подобную ошибку так иногда и называют– бесконечная рекурсия. Для rgcd() условием окончания является равенство нулю остатка.

Вызов

rgcd( 15, 123 );

возвращает 3 (см. табл. 7.1).

Таблица 7.1. Трассировка вызова rgcd (15,123)



vl

v2

return

15

123

rgcd(123,15)

123

15

rgcd(15,3)

15

3

rgcd(3,0)

3

0

3

Последний вызов,

rgcd(3,0);

удовлетворяет условию окончания. Функция возвращает наибольший общий делитель, он же возвращается и каждым предшествующим вызовом. Говорят, что значение всплывает

(percolates) вверх, пока управление не вернется в функцию, вызвавшую rgcd() в первый раз.

Рекурсивные функции обычно выполняются медленнее, чем их нерекурсивные (итеративные) аналоги. Это связано с затратами времени на вызов функции. Однако, как правило, они компактнее и понятнее.

Приведем пример. Факториалом числа n является произведение натуральных чисел от 1 до n. Так, факториал 5 равен 120: 1 ´ 2 ´ 3 ´ 4 ´ 5 = 120.

Вычислять факториал удобно с помощью рекурсивной функции:

unsigned long

factorial( int val ) {

    if ( val > 1 )

        return val * factorial( val-1 );

    return 1;

}

Рекурсия обрывается по достижении val значения 1.

Упражнение 7.12

Перепишите factorial() как итеративную функцию.

Упражнение 7.13

Что произойдет, если условием окончания factorial() будет следующее:

if ( val != 0 )



Содержание раздела