Hacker News Digest

Хвостовая рекурсия превращает рекурсию в цикл: компилятор заменяет вызов на безусловный jmp, поэтому стек не растёт.

Обычная рекурсия кладёт промежуточные значения в стек, тратит O(n) памяти и вытесняет кэш.
Цикл же держит результат в аккумуляторе, использует O(1) памяти и линейное время.

Ключевое правило хвостовой рекурсии:
вызов должен быть последним выражением функции. Тогда компилятор может выбросить текущий фрейм и передать управление напрямую.

Пример суммы списка

Обычная версия:

(define (sum l)
  (if (empty? l) 0
      (+ (first l) (sum (rest l)))))

Хвостовая версия:

(define (sum l acc)
  (if (empty? l) acc
      (sum (rest l) (+ acc (first l)))))

Аргументы l и acc перезаписываются «на месте», как переменные цикла.

Упражнение 1 — счётчик чётных/нечётных:

(define (even-odd l [e 0] [o 0])
  (if (empty? l) (cons e o)
      (let ([x (first l)])
        (if (even? x)
            (even-odd (rest l) (add1 e) o)
            (even-odd (rest l) e (add1 o))))))

Упражнение 2 — сглаживание дерева:
используйте аккумулятор-список и обход в обратном порядке, чтобы сохранить хвостовой вызов.