Основанная на merriam-webster.com, рекурсия – это техника компьютерного программирования, включающая использование процедуры, подпрограммы, функции или алгоритма, которыевызывают сами себя один или несколько раз, пока выполняется указанное условие. Функция, которая делает предложение, выделенное жирным шрифтом, называется рекурсивной функцией.

Существует множество визуальных представлений о том, как работает рекурсия, например треугольник Серпинского и рекурсивное дерево, показанные ниже.

Рекурсия — отличный пример методов решения задач в компьютерном программировании. Декомпозиция действительно играет свою роль в этом алгоритме. Что такое разложение? Вы можете прочитать это здесь" ;)

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

Существует два вида функций рекурсии: прямые и косвенные.

Этот блок кода называется прямой функцией, так как он вызывает ту же функцию Fun.

void dirFun()
{
 // some code..
 dirFun();
 // some code..
}

Эта функция называется косвенной, если она вызывает другую функцию (скажем, Fun_1), а Fun_1 прямо или косвенно вызывает функцию Fun.

void indirFun1()
{
 // some code..
 indirFun2();
 // some code..
}
void indirFun2()
{
 // some code..
 indirFun1();
 //

Что имеется в виду под "особым состоянием" в определении, которое я дал в первый раз?

Конкретное условие обычно также называют базовым условием. Мы должны правильно сделать базовое условие, чтобы ограничить нашу программу, чтобы она не была бесконечным циклом.

Как определить, является ли это правильным базовым условием?

int fact(int n)
{
 if (n == 100) // <- wrong base case!
 return 1;
else
 return n*fact(n-1);
}

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

Привет, я собираюсь написать функцию для нахождения факториала n. Это требования. Если n равно 100, пожалуйста, дайте мне 1. Что бы там ни было, просто дайте мне n*factorial(n-1), пожалуйста!

Чего ждать? факториал равен единице, только если он равен 0 или 1, а не 100. Вот почему это неправильный базовый случай.

Что произойдет, если вы запустите функцию с неправильным базовым условием?

Переполнение стека! Возможно, вы знакомы с этим. Переполнение стека — это ошибка в компьютерной программе из-за чрезмерного использования памяти. Эта ошибка возникает в стеке вызовов. Мы можем представить стек как контейнер наших кодов. Стек имеет ограниченный объем доступной памяти. Его размер определяется языком программирования, архитектурой, наличием многопоточности на ЦП и объемом доступной памяти. Когда происходит переполнение стека, оно обычно зависает или закрывает программу.

Говоря о бесконечном цикле, связана ли функция рекурсии с итерацией?

ДА! Рекурсия обычно используется как альтернатива для того, чтобы код выглядел чище и проще. Это сравнение с использованием итерации и рекурсии для нахождения общей суммы от числа a до числа b.

// using iteration
int main()
{
 int a,b;
 cout << “a= “;
 cin >> a;
 cout << “b= “;
 cin >> b;
int sum = 0;
 for (int i=a; i<=b; i++)
 {
 sum += i;
 }
 
 cout << “total sum from “ << a << “ to “ << b << “ is “ << sum;
 return 0;
}
// using recursion
int recursion101(int a , int b)
{
 if (a == b)
 {
 return a;
 }
return a +recursion(a+1, b);
}
int main()
{
 int a,b;
 cout << “a= “;
 cin >> a;
 cout << “b= “;
 cin >> b;
cout << “total sum from “ << a << “ to “ << b << “ is “ << sum;
 return 0;
}

Обратите внимание, что i‹=b in for (int i=a; i‹=b; i++) и if (a == b) имеют одинаковую функциональность! Они работают как базовое условие!

Несмотря на то, что рекурсия имеет более чистый код, чем итерация, не всегда необходимо использовать рекурсию. Лучше решать Фибоначчи с помощью итерации, чем рекурсии. Избыточность произойдет, если мы откажемся от использования итерации. На этом рисунке Тиа хочет найти 5-е число Фибоначчи с помощью итерации, а Рози хочет найти с помощью рекурсии. Когда вы используете итерацию, она сохраняет каждое предыдущее значение, а затем подсчитывает следующее, не устанавливая их в качестве вывода. Когда вы используете рекурсивную функцию, каждый раз, когда вы выполняете итерацию, она будет устанавливаться как новое значение. Со стороны Тии у каждого F(n) есть только одно значение. Но на стороне Рози есть два значения F(3) и F(0), три значения F(2) и пять значений F(1).

На самом деле реализация рекурсии не так проста и легка, как эта, но я надеюсь, что этот пост поможет вам уловить общую концепцию и понять рекурсивный алгоритм. Большая удача!