Рекурсия - это концепция, которая широко используется в математике и информатике.

Рекурсию также можно рассматривать как акт определения функции в терминах самой себя.

Рекурсивная функция - это функция, которая вызывает себя до тех пор, пока не будет выполнено базовое условие.

СОВЕТ выполняет рекурсивную функцию с помощью ручки и бумаги, чтобы лучше понять, как все работает под капотом.

В приведенных выше определениях я хочу подчеркнуть две важные вещи.

  • Базовый вариант.
  • Определение функции в терминах самой себя (рекурсивный случай).

Также существует структура данных, которая играет жизненно важную роль при использовании рекурсии, она называется СТЕК ВЫЗОВА.

CALL STACK использует LIFO (Last In First Out) в качестве метода обработки данных, так что первый элемент, входящий в него, всегда выходит из него последним. Чтобы понять СТЕКУ ЗВОНКОВ, представьте себе блины, которые уложены друг на друга для подачи.

Чтобы добраться до последнего блина, сначала нужно подать блин наверху. Следовательно, это можно рассматривать как имитацию метода обработки данных LIFO. Блин, который попадется последним, подадут первым.

Рекурсивный регистр:

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

Базовый случай:

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

Рассмотрим следующий пример.

Давайте разберемся, как эта функция обрабатывается механизмом выполнения javascript;

ЗВОНИТЕ 1:

5 * factorial(5–1) which is 5 * factorial(4) ====> push onto the stack (STACK ITEM A);

Звоните 2:

4 * factorial(4 -1); 4 * factorial (3) push onto the stack (STACK ITEM B);

Звоните 3:

3 * factorial(2); push onto the stack (STACK C);

Звоните 4:

2 * factorial(1); pushed onto the stack (STACK D);

Звоните 5:

1 * factorial(0); pushed onto the stack (STACK E);

Но наш базовый случай тщательно обрабатывает случай, когда n === 0; вернув 1;

И помните, что СТЕК ВЫЗОВОВ - это (LIFO), поэтому мы можем сказать

СТЕК E, СТЕК D, СТЕК C… порядок выполнения.

Следовательно, результат вызова функции с заданными аргументами оценивается от последнего элемента, попадающего в стек, до самого первого.

STACK E: 1 * 1;
STACK D: 2 * 1 * 1;
STACK C: 3 * 2 * 1 * 1;
STACK B:  4 * 3 * 2 * 1 * 1;
STACK A:  5 * 4 * 3 * 2 * 1 * 1;

Спасибо за прочтение.