‹= РЕКУРСИЯ =›
Рекурсия — это один из способов решения проблем, требующих многократных итераций. При использовании рекурсии по мере выполнения итераций они сохраняются в стеке. После завершения всех итераций стек возвращает значения, которые можно добавить или обработать, создавая правильный возвращаемый результат функции. Создание базового варианта — это первое, что нужно сделать. Поскольку данные будут храниться в стеке, нам нужен выход, базовый вариант позаботится об этом.
Примечания:
* Важно начать процесс, думая о базовом случае, чтобы не переполнить стек и не сломать наш код!
* При рекурсивном мышлении убедитесь, что интерпретатор сохранит частичные результаты в стеке и начнет возвращаться с самого внутреннего вызова рекурсивной функции.
* Существует 2 основных способа создания рекурсивной функции: один — когда рекурсия является основной функцией, а второй — когда у вас есть внешняя функция, а рекурсия происходит как внутренняя функция.
*Полезно начать процесс понимания рекурсии, зная немного о замыкании и о том, как работает стек.
Чтобы упростить понимание и лучше объяснить это, я решил подойти к этому объяснению, используя игрушечную задачу, и работать над ее решением.
Задача называется makeChange, и ее идея состоит в том, что, учитывая множество монет и конечную стоимость, сколькими способами можно расположить любое количество монет, чтобы найти окончательную стоимость.
Вот код:
const makeChange = function(total) {
const coins = [1, 2, 5, 10, 20, 50, 100, 200];
let count = 0;
const createChange = (target, tracking) => {
if (target === total) {
count++;
} else if (target < total) {
for (let i = 0; i < coins.length; i++) {
if (i >= tracking) {
createChange(coins[i] + target, i);
}
}
}
}
createChange(0, 0);
return count;
};
makeChange(200);
Поскольку здесь речь идет о объяснении рекурсии, а не этой проблемы в частности, мы изменим значения массива так, чтобы они заканчивались на индексе 2, а общее значение равнялось 10 вместо 200.
Теперь давайте разберем код и поймем, что делает рекурсивная внутренняя функция…
›› Начнем с создания внешней функции:
const makeChange = function(total) {
const coins = [1, 2, 5];
let count = 0; . . . }
Создание внешней функции полезно, потому что она содержит рекурсивную функцию, а код остается чистым и простым в использовании, а также мы можем использовать замыкание для доступа ко всем данным, необходимым между функциями.
›› Время рекурсии
. . .
const createChange = (target, tracking) => {
if (target === total) {
count++;
}
. . .
Самое первое, что нужно сделать при работе с рекурсией, — это создать базовый случай. Рекурсивные функции повторяются снова и снова, пока не дойдут до базового случая.
Примечание: давайте посмотрим на аргументы нашей рекурсивной функции. У нас есть два аргумента: target и tracking. Идея здесь в том, что target будет накапливать значения монет, а tracking будет отслеживать индекс в массиве монет.
Мы пытаемся подсчитать, сколькими различными способами мы можем добавить монеты, чтобы получить 10. Итак, для нашего базового случая мы хотим добавлять единицу к count каждый раз, когда наша переменная target суммируется. до 10.
. . .
else if (target < total) {
for (let i = 0; i < coins.length; i++) {
if (i >= tracking) {
createChange(coins[i] + target, i);
}
}
} } createChange(0, 0);
. . .
В этой части кода происходит рекурсия. Мы учитываем случаи, когда наша цель имеет значение ниже, чем наша общая сумма. В данном случае total = 10. Мы также вызываем createChange в первый раз и начинаем его аргументы со значениями 0.
Теперь давайте рассмотрим, как makeChange отслеживает значения в стеке. Происходит первый вызов createChange, и мы начинаем с нашими аргументами значений: target = 0 | tracking = 0.На данный момент наша целевая не равна нашей общей сумме,поэтому мы не достигли базового случая. Итак, мы переходим к нашему оператору else if, который начинает проверку, меньше ли target ( = 0), чем total ( = 10). Войдите в наш цикл for, где i = 0иtracking = 0,мы переходим в наш оператор if, который содержит новый вызов createChange, давайте проверим аргументы, переданные во второй вызов createChange:
coin = [1, 2, 5]; цель = 0; я = 0
цель =› монеты[i] + цель = 1
отслеживание =›я = 0
ВАЖНО: наш первый вызов createChange не завершен, но он сохранен в стеке.
Мы только что сделали новый вызов createChange, что означает сброс нашего цикла, поскольку это новая область действия. В этой итерации есть одно значение, отличное от первого вызова createChange, target = 1.Но этого все еще недостаточно для достижения нашего базового случая, поэтому мы переходим к else if заявление снова. Когда значение target (1) еще меньше total (10), цикл for начинает свою итерацию. Переменные i и tracking по-прежнему равны 0, мы делаем новый вызов createChange, это будет наш третий вызов, поэтому, прежде чем мы начнем Если мы сохраним второй вызов в стеке, в этом случае значение, сохраненное для target, равно 1. Этот процесс будет повторяться, пока мы не достигнем нашего базового случая (target = total).
Вот как выглядит наш стек, когда мы достигаем нашего базового случая:
Scope:
Local
target: 0
this: Window
tracking: 0
Closure (makeChange)
Script
makeChancge: f (total)
values: (3) [1, 2, 5]
Global Window
Scope:
Local
target: 1
this: Window
tracking: 0
Closure (makeChange)
Script
makeChancge: f (total)
values: (3) [1, 2, 5]
Global Window
Scope:
Local
target: 2
this: Window
tracking: 0
Closure (makeChange)
Script
makeChancge: f (total)
values: (3) [1, 2, 5]
Global Window
.
.
.
.
Scope:
Local
target: 9
this: Window
tracking: 0
Closure (makeChange)
Script
makeChancge: f (total)
values: (3) [1, 2, 5]
Global Window
Scope:
Local
target: 10
this: Window
tracking: 0
Closure (makeChange)
Script
makeChancge: f (total)
values: (3) [1, 2, 5]
Global Window
Как только target наконец становится равным total, мы достигаем нашего базового случая, и эта итерация рекурсивной функции выполнена. Таким образом, наш стек поднимается на один шаг вверх до случая, когда цель равна 9, и в этот момент цикл for переходит во вторую итерацию, так что теперь i = 1.
Одна из самых важных вещей, которые нужно понять о рекурсии, это то, как стек хранит рекурсивные функции незавершенным образом, пока самый внутренний вызов рекурсивной функции не достигнет своего базового случая.
