Тема 3.3. Рекурсивные функции

Рекурсивные функции – это особый тип функций, знание которых является обязательным для любого программиста. На практике рекурсия используется, если рекурсивная программа не теряет эффективности, но позволяет написать более простой код, нежели итеративная. Вопросы, касающиеся эффективности рекурсивных функций в настоящем курсе не затрагиваются. Например, вычисление чисел Фибоначчи с применением рекурсии неэффективно, и рассматривается здесь исключительно в учебных целях.

3.3.1Понятие рекурсивной функции

Рекурсивная функция – это функция, вызывающая сама себя. К наиболее простым математическим рекурсивным объектам можно отнести числа Фибоначчи и факториал числа. Рекурсивная функция должна разбиваться на две части. Первая часть должна содержать вызов самой себя, а вторая – нет. Наличие второй части гарантирует тот факт, что рекурсия остановится.

Рассмотрим функцию, вычисляющую факториал. Факториал числа N обозначается через N! и равен произведению 1*2*3*…*N; по определению также полагается, что 0!=1. Итеративная реализация такой функции следующая:

int factorial(int n) {

int result = 1;

for (int i=1; i<=n; i++) {

result *= i;

}

return result;

}

Заметим теперь, что факториал можно задать двумя формулами: 0!=1 и N!=N*(N-1)! В данном случае значение задается только для минимального N, т.е. для 0, а для остальных значения функция определяется через предыдущее значение N. Например, 6!=6*5! Используя данные соотношения, создадим рекурсивную функцию вычисления факториала. Начнем с псевдокода.

Функция Факториал(Число)

Начало

Если Число=0, То Вернуть 1;

Иначе Вернуть Число*Факториал(Число-1);

Конец

Переведем этот псевдокод на язык C++:

int factorial(int n) {

if (n==0) {

return 1;

} else {

return n*factorial(n-1);

}

}

Можно также воспользоваться оператором ?: и сократить код:

int factorial(int n) {

return n==0 ? 1 : n*factorial(n-1);

}

Обратите внимание на то, что такая реализация не использует цикл, зато она вызывает сама себя: n*factorial(n-1). В созданной рекурсивной функции присутствует рекурсивная часть:

return n*factorial(n-1);

и нерекурсивная часть:

return 1;

Протестируем созданную функцию:

#include <iostream>

using namespace std;

int factorial(int n) {

return n==0 ? 1 : n*factorial(n-1);

}

int main() {

cout << factorial(0) << endl;

cout << factorial(3) << endl;

cout << factorial(5) << endl;

cout << factorial(7) << endl;

cout << factorial(10) << endl;

system("pause");

return 0;

}

Рассмотрим еще один пример рекурсивной функции. В случае вычисления факториала нерекурсивно определяется только одно значение, а остальные вычисляются рекурсивно. Это связано с тем, что для вычисления очередного значения достаточно знать только ему предшествующее. Для вычисления 5! достаточно знать только 4!, для вычисления 10! достаточно знать только 9! и т.д.

Сейчас мы рассмотрим пример, когда для вычисления очередного значения необходимо знать два предыдущих. Широко известная последовательность Фибоначчи определяется следующими тремя соотношениями: f₀=0, f₁=1 и f_n=f_n-1+f_n-2. Здесь представлено рекурсивное определения данной последовательности. Для наглядности вычислим несколько первых значений этой последовательности:

f₂=f₁+f₀=0+1=1, f₃=f₂+f₁=1+1=2,

f₄=f₃+f₂=1+2=3, f₅=f₄+f₃=2+3=5.

Напишем псевдокод функции, которая принимает в качестве аргумента номер числа Фибоначчи, а возвращает значение этого числа.

Функция ЧислоФиб(Номер)

Начало

Если Номер=0, То Вернуть 0;

Если Номер=1, То Вернуть 1;

Если Номер>1, То Вернуть

ЧислоФиб(Номер-1)+ЧислоФиб(Номер-2);

Конец

Перенесем этот псевдокод на язык С++:

int fib(int n) {

if (n==0) {

return 0;

}

if (n==1) {

return 1;

}

if (n>1) {

return fib(n-1)+fib(n-2);

}

}

Этот код можно сократить:

int fib(int n) {

return n<2 ? n : fib(n-1)+fib(n-2);

}

Наконец, протестируем программу целиком:

#include <iostream>

using namespace std;

int fib(int n) {

return n<2 ? n : fib(n-1)+fib(n-2);

}

int main() {

cout << fib(1) << endl;

cout << fib(3) << endl;

cout << fib(7) << endl;

cout << fib(20) << endl;

cout << fib(30) << endl;

system("pause");

return 0;

}