Что такое рекурсия?

Процесс, в котором функция вызывает себя прямо или косвенно, называется рекурсией. Эта функция называется рекурсивной функцией. Используя рекурсивный алгоритм, некоторые задачи могут быть решены довольно легко.

Что такое рекурсия- основное условие в рекурсии

В рекурсивной программе предлагается решение основного случая, а решение более крупной задачи выражается в условиях меньших задач:

int fact(int n)
{
    if (n < = 1) // основной случай
        return 1;
    else
        return n*fact(n-1);
}

В приведенном выше примере основной случай для n <= 1 определен и большее значение числа может быть решено путем преобразования в меньшее по размеру до получения основного варианта.

Почему ошибка переполнения стека происходит в рекурсии?

В рекурсивной процедуре и функции если основной случай не достигнут или не определен, может возникнуть проблема с переполнением стека. Давайте посмотрим на примере, чтобы понять:

int fact(int n)
{
    // неправильный основной случай (это может вызвать
    // переполнение стека).
    if (n == 100) 
        return 1;
    else
        return n*fact(n-1);
}

Если вызывается рекурсивная функция C fact (10), она будет вызывать fact (9), fact (8), fact (7) и т. д. Но переменная никогда не достигнет значения 100. Таким образом, конечный вариант не достигается. Если память исчерпана функциями в стеке, это вызовет ошибку переполнения стека.

В чем разница между прямой и косвенной рекурсиями?

Функция fun называется прямой рекурсивной, если она вызывает ту же функцию fun. Функция fun называется косвенной рекурсивной, если она вызывает другую функцию. Разница между прямой и косвенной рекурсией проиллюстрирована в коде ниже:

// Пример прямой рекурсии
void directRecFun()
{
    // Какой-то код....
    directRecFun();
    // Какой-то код...
}
// Пример косвенной рекурсии
void indirectRecFun1()
{
    // Some code...
    indirectRecFun2();
    // Some code...
}
void indirectRecFun2()
{
    // Какой-то код...
    indirectRecFun1();
    // Какой-то код...
}

В чем разница между хвостовой и не хвостовой рекурсиями?

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

Как распределена память для разных вызовов функций в рекурсии?

Когда функция вызывается из main(), ей выделяется память в стеке. Рекурсивная функция вызывает себя. Память для вызываемой функции выделяется поверх памяти, выделенной для функции вызова. Для каждого вызова функции создается отдельная копия локальных переменных. Когда конечный вариант достигнут, функция возвращает свое значение функции, которой она вызвана, память освобождается, и процесс продолжается.

Приведем пример, когда рекурсия работает, выполняя простую функцию:

// в программе на C++ показывается работа
// рекурсии
#include<bits/stdc++.h>
using namespace std;
 void printFun(int test)
{
    if (test < 1)
        return;
    else
    {
        cout << test << " ";
        printFun(test-1);    // выражение 2
        cout << test << " ";
        return;
    }
}
 int main()
{
    int test = 3;
    printFun(test);
}

Посмотреть демо

Вывод:

3 2 1 1 2 3

Когда printFun(3) вызывается из main(), память присваивается printFun(3), а локальная переменная test инициализируется значением 3. При этом выражения 1 - 4 помещаются в стек, как показано на диаграмме, представленной ниже. Сначала выводится «3». Во втором выражении вызывается printFun(2) и память присваивается printFun(2), а локальная переменная test инициализируется значением 2, а выражения 1 - 4 помещаются в стек. Аналогично, printFun(2) вызывает printFun(1) и printFun(1) вызывает printFun(0). printFun(0) переходит в fact if, и возвращается к printFun(1). Остальные выражения printFun(1) выполняются и возвращаются к printFun(2) и так далее. Выводятся значения от 3 до 1, а затем печатаются от 1 до 3. Стек памяти рекурсивной функции показан на диаграмме, приведенной ниже:

Каковы недостатки рекурсивного программирования по сравнению с итеративным программированием?

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

Рекурсия также занимает больше времени из-за вызовов функций и издержек на возврат.

Каковы преимущества рекурсивного программирования над итерационным программированием?

Рекурсия обеспечивает простой и понятный способ написания кода. Некоторые задачи являются неотъемлемо рекурсивными. Для них предпочтительнее использовать рекурсивный код. Подобный код можно писать итеративно с помощью структуры данных «стек».

КККонстантин Кондрусинавтор статьи «Recursion»