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

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

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

#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) получится следующая цепь вызовов:

1. 5 * factorial(4)

2. 5 * 4 * factorial(3)

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

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

5. 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;
}

И нередко циклические конструкции более эффективны, чем рексурсия. Например, если функция вызывает себя тысячи раз, потребуется большой объем стековой памяти для хранения копий значений аргументов и адреса возврата для каждого вызова, что может привести к тому, что программа быстро исчерпает выделенную для нее память стека, поскольку объем памяти стека обычно фиксирован и ограничен. что может привести к аварийному завершению программы. Поэтому в таких случаях, как правило, лучше использовать альтернативные подходы, например цикл. Однако, несмотря на накладные расходы, использование рекурсии часто может значительно упростить написание программы.