Рекурсия и хвостовая рекурсия

В функциональном стиле рекурсия заменяет циклы — но важно писать её так, чтобы не переполнить стек.

Хвостовая рекурсия — рекурсия, в которой рекурсивный вызов является последним действием функции; компилятор превращает её в цикл без роста стека.

Рекурсивные функции: rec

Чтобы функция могла вызывать себя, её помечают rec.

let rec factorial n =
    if n <= 1 then 1
    else n * factorial (n - 1)
printfn "%d" (factorial 5)

Вывод:

120

Это естественная, «учебниковая» рекурсия. Но обратите внимание: после возврата factorial (n - 1) ещё нужно умножить на n — значит, вызов не последний.

Проблема: рост стека

Каждый незавершённый вызов держит кадр на стеке. Для factorial 100000 накопится 100000 кадров — стек переполнится (StackOverflow). Обычная (нехвостовая) рекурсия опасна на больших входах.

// нехвостовой sum: умножение/сложение ПОСЛЕ вызова -> кадры копятся
let rec sumBad n =
    if n = 0 then 0
    else n + sumBad (n - 1)
// sumBad 1000000 рискует переполнить стек

Решение: аккумулятор и хвостовой вызов

Перепишем так, чтобы рекурсивный вызов был последним действием. Для этого вводят параметр-аккумулятор, в котором копится результат.

let sum n =
    let rec loop acc i =
        if i = 0 then acc
        else loop (acc + i) (i - 1)   // последний шаг — сам вызов
    loop 0 n
printfn "%d" (sum 100)

Вывод:

5050

Теперь после loop ... ничего не делается — это хвостовой вызов. Компилятор F# заменяет его на цикл, и стек не растёт даже для миллионов итераций.

Как работает под капотом

Когда рекурсивный вызов хвостовой, компилятору не нужно сохранять текущий кадр — возвращать в него нечего, результат вложенного вызова и есть результат текущего. F# превращает такую рекурсию в обычный цикл (while) на уровне IL: переиспользует один кадр, обновляя параметры. Поэтому хвостовая рекурсия работает в константной памяти стека — как императивный цикл, но без мутаций в вашем коде.

Частые ошибки

• Забыть rec — компилятор не найдёт имя функции внутри неё самой.
• Считать вызов хвостовым, когда после него есть операция (n + f(...) — нехвостовой).
• Писать глубокую нехвостовую рекурсию для больших входов — переполнение стека.

Итоги

• Рекурсивные функции помечают rec; рекурсия заменяет циклы.
• Нехвостовая рекурсия копит кадры и рискует переполнить стек на больших входах.
• Хвостовая рекурсия (рекурсивный вызов — последнее действие) выполняется как цикл.
• Приём «аккумулятор + внутренняя функция loop» делает рекурсию хвостовой.