Здесь мы рассмотрим рекурсивные функции и технику, называемую батутом, для устранения ограничений стека.
- Возьмем из хвостовой рекурсивной факториальной функции:
const fact = (n, acc = 1) => (n > 1) ? fact(n - 1, n * acc) : acc;
- Дайте определение батуту
const trampoline = fn => { while(fn instanceof Function) { fn = fn(); } return fn; }
Вы можете видеть, что батут будет зацикливаться, пока рекурсивные вызовы заключены в замыкание.
- Использование батута
const fact = (n, acc = 1) => (n > 1) ? () => fact(n - 1, n * acc) : acc; console.log(trampoline(fact(5))); console.log(trampoline(fact(50000)));
Попробуем перенести батут за кулисы. Мы можем повторно использовать наш прокси, см. часть первую, для переноса рекурсивного вызова.
- Представляем прокси
const proxy = fn => (...args) => () => fn(proxy(fn), ...args); const fact = proxy((fact, n, acc = 1) => (n > 1) ? fact(n - 1, n * acc) : acc);
- Переместить батут на прокси
const proxy = fn => (...args) => () => fn(proxy(fn), ...args); const proxyInit = fn => (...args) => trampoline(() => fn(proxy(fn), ...args)); const fact = proxyInit((fact, n, acc = 1) => (n > 1) ? fact(n - 1, n * acc) : acc); console.log(fact(5)); console.log(fact(50000));
ProxyInit выполнит однократные вызовы инициализации.
В целом, батут поможет нам писать рекурсивные функции и обойти ограничения стека.