Рекурсия

Что такое рекурсия?
Процесс, в котором функция вызывает себя прямо или косвенно, называется рекурсией, а соответствующая функция называется рекурсивной функцией. Используя рекурсивный алгоритм, можно довольно легко решить некоторые проблемы. Примеры таких проблем: Towers of Hanoi (TOH), Inorder / Preorder / Postorder Tree Traversals, DFS of Graph и т. Д.

Математическая интерпретация

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

approach(1) – Simply adding one by one

f(n) = 1 + 2 + 3 +……..+ n

но есть другой математический подход к представлению этого,

approach(2) – Recursive adding 

f(n) = 1                  n=1

f(n) = n + f(n-1)    n>1

Между подходом (1) и подходом (2) есть простая разница, заключающаяся в том, что в подходе (2) сама функция « f () » вызывается внутри функции, поэтому это явление называется рекурсией, а функция, содержащая Рекурсия называется рекурсивной функцией, в конце концов, это отличный инструмент в руках программистов, позволяющий кодировать некоторые проблемы намного проще и эффективнее.

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

 int факт (int n)
{
    if (n <= 1) // базовый случай
        возврат 1;
    еще    
        return n * fact (n-1);    
}

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

Как решается конкретная проблема с помощью рекурсии?
Идея состоит в том, чтобы представить проблему в виде одной или нескольких более мелких проблем и добавить одно или несколько базовых условий, останавливающих рекурсию. Например, мы вычисляем факториал n, если мы знаем факториал (n-1). Базовым случаем для факториала будет n = 0. Мы возвращаем 1, когда n = 0.

Почему при рекурсии возникает ошибка переполнения стека?
Если базовый вариант не достигнут или не определен, может возникнуть проблема переполнения стека. Давайте рассмотрим пример, чтобы понять это.

 int факт (int n)
{
    // неправильный базовый случай (это может вызвать
    // переполнение стека).
    если (n == 100) 
        возврат 1;

    еще
        return n * fact (n-1);
}

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

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

 // Пример прямой рекурсии
void directRecFun ()
{
    // Какой-то код ....

    directRecFun ();

    // Какой-то код ...
}

// Пример косвенной рекурсии
недействительный косвенныйRecFun1 ()
{
    // Какой-то код ...

    IndirectRecFun2 ();

    // Какой-то код ...
}
недействительным косвенныйRecFun2 ()
{
    // Какой-то код ...

    IndirectRecFun1 ();

    // Какой-то код ...
}

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

How memory is allocated to different function calls in recursion? 
When any function is called from main(), the memory is allocated to it on the stack. A recursive function calls itself, the memory for a called function is allocated on top of memory allocated to calling function and different copy of local variables is created for each function call. When the base case is reached, the function returns its value to the function by whom it is called and memory is de-allocated and the process continues.
Let us take the example how recursion works by taking a simple function. 

Выход :

 3 2 1 1 2 3

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

Теперь давайте обсудим несколько практических проблем, которые можно решить с помощью рекурсии, и разберемся с ее основными принципами работы. Для базового понимания прочтите следующие статьи.
Базовое понимание рекурсии.
Проблема 1. Напишите программу и рекуррентное соотношение, чтобы найти ряд Фибоначчи для n, где n> 2.
Математическое уравнение:

 n, если n == 0, n == 1;      
fib (n) = fib (n-1) + fib (n-2) в противном случае;

Отношение повторения:

 Т (п) = Т (п-1) + Т (п-2) + О (1)

Рекурсивная программа:

 Ввод: n = 5 
Выход:
Ряд Фибоначчи из 5 чисел: 0 1 1 2 3

Implementation: 

Fibonacci series of 5 numbers is: 0 1 1 2 3 

Вот рекурсивное дерево для ввода 5, которое показывает четкую картину того, как большую проблему можно решить на более мелкие.
fib (n) - функция Фибоначчи. Временная сложность данной программы может зависеть от вызова функции.

fib(n) -> level CBT (UB) -> 2^n-1 nodes -> 2^n function call -> 2^n*O(1) -> T(n) = O(2^n)  

В лучшем случае.

 Т (п) = θ (2 ^ п  2)

Работающий:

Проблема 2: Напишите программу и рекуррентное отношение, чтобы найти факториал числа n, где n> 2.
Математическое уравнение:

 1, если n == 0 или n == 1;      
f (n) = n * f (n-1), если n> 1;

Отношение повторения:

 T (n) = 1 для n = 0
T (n) = 1 + T (n-1) для n> 0

Recursive Program: 
Input: n = 5 
Output: 
factorial of 5 is: 120
Implementation: