Рекурсия
Функция, которая прямо или косвенно вызывает сама себя, называется рекурсивной. Например:
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 )
