Как работает рекурсия при встрече с return null?

Question

[Михаил Оловянников]

Всем привет, учусь JS по учебнику выразительный JS. Встретил непонимание с тем как работает данный пример:

function findSolution(target) {
            function find(current, history) {
                if (current == target) {
                    return history;
                } else if (current > target) {
                    return null;
                } else {
                    return find(current + 5, `(${history} + 5)`) ||
                        find(current * 3, `(${history} * 3)`);
                }
            }
            return find(1, "1");
        }

        console.log(findSolution(24));

Вообще я минут 10 просто тупо смотрел на этот код как баран на новые ворота, но потом суть понял. Потом начал расставлять точки остановки в chrome developer tools чтобы лучше понять как эта конструкция работает и не понял я вот что: первым делом вся эта конструкция в процессе своей работы сталкивается с return null на значении current = 26. Почему после этого значение current становиться предыдущим - то есть 21? Как это работает? Внешняя функция что-ли помнит значения всех предыдущих вызовов функции find и будет так долбиться туда-сюда покуда current не станет равным 24 или покуда return null не выйдет из всех запущенных функций find? Так что ли?

И еще: хочу поделиться личными переживаниями в процессе обучения. Это нормально что я так торможу в таких задачах? Мне первоначально показалось что это надо быть каким-то сверхмозгом чтобы такое написать.)))

Answer 1

[otdameskapizm]

Проще понять так: возьми

return find(current + 5, `(${history} + 5)`) ||
                        find(current * 3, `(${history} * 3)`);

Представь, что левый return - это левая ветка, а правый - правая. Сначала ты будешь проваливаться по левой ветке и дойдешь до 26, после этого у тебя вернется null так как 26 > 24. Предыдущий return, получив null прыгнет в правую часть условия (где у тебя все умножается на 3), но и там будет тоже null, так как 21 * 3 = 63 (что больше 24-х). Функция вернет тебя еще на уровень выше в правую ветку, так как из общей левой у тебя вернулся null. Ты пойдешь так "наверх", пока не встретишь условие, где будет 6 * 3 = 18. У тебя в сумме будет 19. И после этого ты войдешь опять в правую ветку, где будет 19 + 5, что даст тебе желанное 24 и выход из функции

Постарался на пальцах объяснить

А по поводу торможения. Рекурсия просто требует определенного времени, чтобы в нее "въехать".

Comments

[Михаил Оловянников]

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

Answer 2

[Rsa97]

Внешняя функция ничего не помнит. Помнит сам JS. При вызове функции в стеке создаётся новое окружение для вызванной функции. При возврате из функции это окружение снимается со стека и текущим снова становится окружение вызывавшей функции. Таким образом вложенные вызовы функций (в том числе и рекурсивные) создают в стеке последовательность окружений, по которым затем возвращаются назад.

Comments

[Михаил Оловянников]

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