Рекурсивные функции - это функции, которые вызывают сами себя. Такие функции довольно часто используются для обхода различных представлений. Например, если нам надо найти определенный файл в папке, то мы сначала смотрим все файлы в этой папке, затем смотрим все ее подпак
Например, определим вычисление факториала в виде рекурсивной функции:
#include <iostream> unsigned long long factorial(unsigned); int main() { unsigned n {5}; auto result { factorial(n)}; std::cout << "Factorial of " << n << " is equal to " << result << std::endl; } unsigned long long factorial(unsigned 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, таким образом, определяют базовые варианты для данной функции:
#include <iostream> unsigned long long fib(unsigned); int main() { for(unsigned i{}; i < 10; i++) { auto n = fib(i); std::cout << n << "\t"; } std::cout << std::endl; } unsigned long long fib(unsigned n) { if (n == 0) return 0; if (n == 1) return 1; return fib(n - 1) + fib(n - 2); }
Результат работы программы - вывод 10 чисел из последовательности Фиббоначчи на консоль:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34
В примерах выше функция напрямую вызывала саму себя. Но рекурсивный вызов функции также может быть косвенным. Например, функция fun1() вызывает другую функцию fun2(), которая, в свою очередь, вызывает fun1(). В этом случае функции fun1() и fun2() также называются взаимно рекурсивными функциями.
Стоит отметить, что нередко рекурсивные функции можно представить в виде циклов. Например, для вычисления факториала вместо рекурсии используем цикл:
#include <iostream> unsigned long long factorial(unsigned); int main() { unsigned n {6}; std::cout << "Factorial of " << n << " : " << factorial(n) << std::endl; } unsigned long long factorial(unsigned n) { unsigned long long result{1}; for(unsigned i{1}; i <= n; i++) { result *= i; } return result; }
И нередко циклические конструкции более эффективны, чем рексурсия. Например, если функция вызывает себя тысячи раз, потребуется большой объем стековой памяти для хранения копий значений аргументов и адреса возврата для каждого вызова, что может привести к тому, что программа быстро исчерпает выделенную для нее память стека, поскольку объем памяти стека обычно фиксирован и ограничен. что может привести к аварийному завершению программы. Поэтому в таких случаях, как правило, лучше использовать альтернативные подходы, например цикл. Однако, несмотря на накладные расходы, использование рекурсии часто может значительно упростить написание программы.