Comments 10
Конкретно для этой задаче - не проще сделать мэп с [m,n] -> value, и если в мэпе уже есть значение - возвращать его, а если нет - вызываться рекурсивно?
Мемоизация решает другой набор проблем с рекурсией. В данном случае она может ускорить функцию и немного отложить пробитие стека, но глобально проблему не решит.
наивная версия с мемоизацией
let cache = new Map();
let has = (m, n) => cache.get(m).has(n);
let get = (m, n) => cache.get(m).get(n);
let set = (m, n, value) => cache.get(m).set(n, value);
const ackermann1 = (m, n) => {
if (!cache.has(m)) {
cache.set(m, new Map());
}
if (!has(m, n)) {
if (m === 0) {
set(m, n, n + 1);
} else if (n === 0) {
set(m, n, ackermann1(m - 1, 1));
} else {
set(m, n, ackermann1(m - 1, ackermann1(m, n - 1)));
}
}
return get(m, n);
};
В таком виде она будет проваливать стек при m = 3, n = 13.
Глубина стека - всего 16 элементов? Тут же в рекурсии в любой момент времени уменьшается или n, или m - значит, в любой момент времени глубина стека не более n+m.
Такая задача может по времени обламываться, т.к. без кэширования результатов "дерево" получается очень широкое.
Глубина стека - всего 16 элементов? Тут же в рекурсии в любой момент времени уменьшается или n, или m - значит, в любой момент времени глубина стека не более n+m.
Не уменьшается. ackermann(m - 1, ackermann(m, n - 1)) - здесь второй параметр может быть гораздо больше исходного n
Для ackermann(3, n) глубина рекурсии будет 2^(n+3)
Функция Аккермана славна тем, что даёт огромные значения для довольно скромных аргументов и огромную глубину рекурсии, почему удобна для подобных экспериментов.
И, если мне не изменяет память, мемоизация не поможет: пара аргументов в разных вызовах будет разной...
К чему вообще все это? Хвостовая рекурсия решает стековые проблемы, так зачем огород городить?
Решает (но не в js, там нет этого). Однако в общем случае перековка рекурсии в хвостовую точно такая же, как в цикл. И не имеет смысла, если в языке есть цикл.
Хвостовая рекурсия решает стековые проблемы
Хвостовая рекурсия это по сути просто цикл. Соответственно, если что-то сложно написать с помощью цикла, будет сложно и с помощью хвостовой рекурсии (можете сами попробовать).
К чему вообще все это?
Идея показалась интересной, но ничего подобного нагуглить не смог. Про генераторы, имхо, в целом очень мало пишут, поэтому считаю нужным делиться их нестандартными применениями
Таким образом на стандартных настройках стек стал больше в
2792раза.
Почему так скромно получилось?
Не, это, конечно, сильно лучше, чем при стандартном подходе, но всё же скромно.
Отделяем стек от рекурсии