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

Рекурсивные функции - это функции, которые вызывают сами себя.

Например, представим вычисление факториала в виде рекурсивной функции:

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

int factorial(int n)
{
if (n == 1)
{
return 1;
}
else
{
return n * factorial(n - 1);
}
}

int main(void)
{
int result = factorial(6);
printf("%d \n", result); // 720

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

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

И также все рекурсивные вызовы должны обращаться к подфункциям, которые в конце концов сходятся к базовому варианту. Так, при передаче в функцию положительного числа при дальнейших рекурсивных вызовах подфункций в них будет передаваться каждый раз число, меньшее на единицу. И в конце концов мы дойдем до ситуации, когда число будет равно 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
int fibonachi(int n)
{
if (n == 0)
{
return 0;
}
if (n == 1)
{
return 1;
}
else
{
return fibonachi(n - 1) + fibonachi(n - 2);
}
}