Метка «tail recursion»

Если кто-то ещё не знает, что такое хвостовая рекурсия, вот простой пример метода, складывающего в лоб натуральные числа от 1 до n (n≥0):

function add(n,acc) {
  if(n===0) return acc;
  return add(n-1,acc+n);
}

Изначально функция вызывается с параметром acc=0. В случае, если n не равно нулю, метод вызывает сам себя с другими параметрами и возвращает результат. Компилятор (или интерпретатор, или виртуальная машина) могут понять, что текущий вызов функции в стеке уже не нужен, стереть его и заменить следующим вызовом. Таким образом, рекурсия не приводит к разрастанию стека. Строго говоря, хвостовой вызов не обязан обращаться к текущей функции: вызов любой другой тоже может быть хвостовым. Главное условие: вызов функции и возврат её результата должны быть последними действиями в текущей функции. К примеру, в такой реализации метода хвостовой рекурсии нет, так как после вызова происходит ещё сложение:

function add(n) {
  if(n===0) return 0;
  return n+add(n-1);
}

По ряду причин хвостовая рекурсия в JavaScript не поддерживается (обсуждение на эту тему есть на StackOverflow). Поэтому вызов вроде add(100000,0) завершится исключением. На Хабре предпринимались попытки решить эту проблему через setTimeout, но это выглядит не очень честно и не очень красиво. Более изящное решение для языка Python было предложено с использованием «трамплина». Похожий подход для JavaScript рассмотрен здесь. Но мне захотелось, чтобы работало быстро и чтобы функцию можно было записать прямо как в примере выше. Посмотрим, что можно сделать.
Читать полностью »

F# Хвостовая рекурсия. Подводные грабли. Часть 1
Винни Пух: Ой, что это случилось с твоим хвостом?
Иа: А что с ним могло случится?
Винни Пух: Его нет.
Иа: Ты не ошибся?
Винни Пух: Хвост или есть или нет совсем! Тут нельзя ошибиться.
Иа: А что же тогда там есть?
Винни Пух: Ничего!

У нас в проекте, в одном из серверных компонентов, после очередного рефакторинга начала течь память. Казалось бы .NET, F#, менеджед код, сборка мусора, все дела, но память, куда-то утекала. Ценой бессонных ночей и попорченных нервов, источник утечки был найден. Оказалось что проблема вызвана куском кода, который был, чуть ли не один к одному скопирован из учебника по F#.

Все дело было в хвостовой рекурсии, вернее, как оказалось в ее отсутствии в неожиданных местах.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js