F# Хвостовая рекурсия. Подводные грабли. Часть 1

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

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

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

Хвостовая рекурсия

Рекурсия, это наверно один из самых важных инструментов в арсенале функционального программирования. А так как при рекурсивных вызовах используется стек, который, как известно, не безграничен, то может показаться, что применение рекурсии ограничено, и глубина рекурсии конечна.

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

Хвостовая рекурсия это частный случай рекурсии, когда рекурсивный вызов может быть заменен итерацией. С одной стороны на совести программиста остается написание логики в «хвостовом» стиле, с другой стороны компилятор тоже должен «обнаружить» хвостовую рекурсию и раскрутить рекурсию в итерацию.

Обычно начинающий «функциональщик» быстро набивает глаз и руку и использует везде хвостовую рекурсию. Но есть несколько особых случаев, когда функция, которая, казалось бы, является железно «хвостовой» на самом деле не является таковой. Эти особые случаи могут привести к очень неприятным последствиям, и могут убить массу времени и нервов.

Давайте рассмотрим первый такой случай и сформулируем правило, с помощью которого можно избежать «неприятностей».

Давайте, для начала возьмем простую функцию, которая суммирует числа все числа от одного до N:

let rec sum i =
    if i <= 0L then 0L
    else i + sum (i - 1L) 

> sum 10L;;
val it : int64 = 55L

Все хорошо, за исключением одной момента. Если мы попробуем посчитать сумму хотя бы для 100000, то получим в лоб StackOverflowException. Т.е. у нас банально не хватило стека для вычислений:

> sum 100000L;;

Process is terminated due to StackOverflowException.

Ответ на эту проблему, использование аккумулятора, как аргумента рекурсивной функции:

let sumTailRec i =
    let rec loop acc i =
        if i <= 0L then acc
        else loop (acc + i) (i - 1L) 
    loop 0L i

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

Проиллюстрировать порядок вычисления (для аргумента 5) можно так. Без хвостовой рекурсии:

sum: 5 + (4 + (3 + (2 + (1 + (0))))) – тут мы идем сначала в одну сторону, а потом, дойдя до нуля возвращаемся и суммируем. Как раз для того чтобы возвращаться и нужен стек.

С хвостовой рекурсией:

sumTailRec: (((0 + 5) + 4) + 3) + 2) + 1) – здесь, мы идем только в одну сторону, и ответ у нас накапливается в аккумуляторе, поэтому собственно стек нам и не нужен.

Новая функция уже может переварить сколь угодно большое число (пока хватит разрядности int64).

> sumTailRec 10000000L;;
val it : int64 = 50000005000000L

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

let sumFTailRec f i =
    let rec loop acc i =
        if i <= 0L then acc
        else loop (acc + f i) (i - 1L) 
    loop 0L i

В новой версии у нас появился еще один параметр – функция, результат вычисления которой нужно суммировать. Вот вариант, который суммирует сами числа:

> sumFTailRec (fun i -> i) 10000000L

val it : int64 = 50000005000000L

А вот, который суммирует квадраты:

> sumFTailRec (fun i -> i*i) 10000000L

val it : int64 = 1291990006563070912L

Пока все хорошо. Но есть небольшой нюанс, функция которая передается, может «кинуть» исключение. Вот пример:

> let someProblemFun i = i/((i+1L) % 1000L)

> sumFTailRec someProblemFun 10000000L

System.DivideByZeroException: Attempted to divide by zero.
Stopped due to error

Проблема

При значении i = 999, у нас возникает деление на ноль. Предположим, что мы хотим при исключении, не аварийно завершать вычисление, а просто игнорировать проблемный элемент. Нам понадобится обработка исключения. Само собой напрашивается вполне логичное и ожидаемое решение:

let sumFTailRecWithTry f i =
    let rec loop acc i =
        if i <= 0L then acc
        else
            try 
                loop (acc + f i) (i - 1L) 
            with 
                exc -> 
                    printfn "exn raised:%s" exc.Message
                    loop acc (i - 1L) 
    loop 0L i

Итак пробуем:

> sumFTailRecWithTry someProblemFun     10000L

exn raised:Attempted to divide by zero.
...
exn raised:Attempted to divide by zero.
val it : int64 = 351405L

Результат получили, исключения отловили, вроде все нормально. Теперь пробуем скормить более серьезное число:

> sumFTailRecWithTry someProblemFun 10000000L

exn raised:Attempted to divide by zero.
...
exn raised:Attempted to divide by zero.

Process is terminated due to StackOverflowException.

Упс… В чем же дело? На первый взгляд у нас функция с хвостовой рекурсией, почему вдруг закончился стек?

Как можно догадаться, проблема в конструкции try … with. Дело в том, что если рекурсивный вызов выполняется в блоке try, то у хвостовой рекурсии «отваливается» хвост, и она становится обычной рекурсией. Почему? Потому что в любом из последующих рекурсивных вызовов loop, теоретически может выпасть исключение, а т.к. нам надо его будет обработать, то нужно запомнить в стеке место, куда нужно вернуться при «выпадении» исключения.

Решение

Какой из такой неприятной ситуации выход? Очень простой, не нужно оборачивать рекурсивный вызов блоком try… with, ведь исключение мы ожидаем только при вызове «внешней» функции f, значит оборачивать нужно только этот вызов:

let sumFReallyTailRecWithTry f i =
    let rec loop acc i =
        if i <= 0L then acc
        else
            let fRes = 
                try f i
                with exc ->
                    //printfn "exn raised:%s" exc.Message
                    0L
            loop (acc + fRes) (i - 1L) 
    loop 0L i

Пробуем:

> sumFReallyTailRecWithTry someProblemFun 10000000L
val it : int64 = 374200932236L

Вуаля! Стека на этот раз хватило, вернее он остался не тронутый.

Итак, правило: никогда не помещайте хвостовой вызов в блок try… with.

Во второй серии будут шокирующие разоблачения касающиеся хвостовой рекурсии для async { … } и MailboxProcessor.

Автор: temaHT