Рекурсивные функции

Рекурсивные функции - это функции, которые вызывают сами себя. Например, определим вычисление факториала в виде рекурсивной функции:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>

int factorial(int);

int main()
{
int n = 5;
int result = factorial(n);
std::cout << "Factorial of " << n << " is equal to " << result << std::endl;
return 0;
}

int factorial(int n)
{
if(n>1)
return n * factorial(n-1);
return 1;
}
В функции factorial задано условие, что если число n больше 1, то это число умножается на результат этой же функции, в которую в качестве параметра передается число n-1. То есть происходит рекурсивный спуск. И так далее, пока не дойдем того момента, когда значение параметра не будет равно 1. В этом случае функция возвратит 1.

Рекурсивная функция обязательно должна иметь некоторый базовый вариант, который использует оператор return и к которому сходится выполнение остальных вызовов этой функции. В случае с факториалом базовый вариант представлен ситуацией, при которой n = 1. В этом случае сработает инструкция return 1;.

Например, при вызове factorial(5) получится следующая цепь вызовов:

5 * factorial(4)

5 * 4 * factorial(3)

5 * 4 * 3 * factorial(2)

5 * 4 * 3 * 2 * factorial(1)

5 * 4 * 3 * 2 * 1

Другим распространенным показательным примером рекурсивной функции служит функция, вычисляющая числа Фиббоначчи. n-й член последовательности чисел Фибоначчи определяется по формуле: f(n)=f(n-1) + f(n-2), причем f(0)=0, а f(1)=1. Значения f(0)=0 и f(1)=1, таким образом, определяют базовые варианты для данной функции:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>

int fibonachi(int);

int main()
{
int n;
for(int i = 0; i < 10; i++)
{
n = fibonachi(i);
std::cout << n << "\t";
}
std::cout << std::endl;
return 0;
}
int fibonachi(int n)
{
if (n == 0)
return 0;
if (n == 1)
return 1;
return fibonachi(n - 1) + fibonachi(n - 2);
}
Результат работы программы - вывод 10 чисел из последовательности Фиббоначчи на консоль:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34