Пример рекурсивной функции F# Tail

Question

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

Answer 1

Начните с простой задачи, например, сопоставления элементов из списка "a" с "b" в списке. Мы хотим написать функцию, которая имеет подпись

val map: ('a -> 'b) -> 'a list -> 'b list

куда

map (fun x -> x * 2) [1;2;3;4;5] == [2;4;6;8;10]

Начнем с нехвостовой рекурсивной версии:

let rec map f = function
    | [] -> []
    | x::xs -> f x::map f xs

Это не хвостовая рекурсия, потому что функция все еще должна работать после выполнения рекурсивного вызова. :: является синтаксическим сахаром для List.Cons(f x, map f xs),

Нерекурсивный характер функции может быть немного более очевидным, если я переписываю последнюю строку как | x::xs -> let temp = map f xs; f x::temp - очевидно, что он выполняет работу после рекурсивного вызова.

Используйте переменную аккумулятора, чтобы сделать ее хвостовой рекурсивной:

let map f l =
    let rec loop acc = function
        | [] -> List.rev acc
        | x::xs -> loop (f x::acc) xs
    loop [] l

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

Если вы хотите немного исказить разум, вы можете использовать передачу продолжения, чтобы написать код более кратко:

let map f l =
    let rec loop cont = function
        | [] -> cont []
        | x::xs -> loop ( fun acc -> cont (f x::acc) ) xs
    loop id l

Поскольку призыв к loop а также cont последние функции, вызываемые без дополнительной работы, они хвостовой рекурсии.

Это работает, потому что продолжение cont перехватывается новым продолжением, которое, в свою очередь, перехватывается другим, что приводит к некоторой древовидной структуре данных следующим образом:

(fun acc -> (f 1)::acc)
    ((fun acc -> (f 2)::acc)
        ((fun acc -> (f 3)::acc)
            ((fun acc -> (f 4)::acc)
                ((fun acc -> (f 5)::acc)
                    (id [])))))

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

---

Для чего стоит начинать писать функции нехвостым рекурсивным способом, с ними легче читать и работать.

Если вам нужен большой список, используйте переменную-аккумулятор.

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

Answer 2

Попытка более короткого объяснения, чем в других примерах:

let rec foo n =
    match n with
    | 0 -> 0
    | _ -> 2 + foo (n-1)

let rec bar acc n =
    match n with
    | 0 -> acc
    | _ -> bar (acc+2) (n-1)

foo не является хвостовой рекурсией, потому что foo должен вызывать foo рекурсивно, чтобы вычислить "2+foo(n-1)" и вернуть его.

bar является хвостовой рекурсивной, потому что bar не должна использовать возвращаемое значение рекурсивного вызова для возврата значения. Он может просто позволить рекурсивно вызываемому бару немедленно вернуть свое значение (не возвращая весь путь вверх через вызывающий стек). Компилятор видит это и "обманывает", переписывая рекурсию в цикл.

Изменение последней строки в баре на "| _ -> 2+(bar (acc+2) (n-1))" разрушит рекурсивность хвостовой части.

Answer 3

Вот более очевидный пример, сравните его с тем, что вы обычно делаете для факториала.

let factorial n =
    let rec fact n acc =
        match n with
        | 0 -> acc
        | _ -> fact (n-1) (acc*n)
    fact n 1

Это немного сложно, но идея в том, что у вас есть аккумулятор, который поддерживает подсчет, а не изменяет возвращаемое значение.

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

Answer 4

Я тоже учусь F#. Ниже приведены не хвостовая рекурсивная и хвостовая рекурсивная функция для вычисления чисел Фибоначчи.

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

let rec fib = function
    | n when n < 2 -> 1
    | n -> fib(n-1) + fib(n-2);;

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

let fib n =
    let rec tfib n1 n2 = function
    | 0 -> n1
    | n -> tfib n2 (n2 + n1) (n - 1)
    tfib 0 1 n;;  

Примечание: поскольку число Фибоначчи может расти очень быстро, вы можете заменить последнюю строку tfib 0 1 n в
tfib 0I 1I n воспользоваться структурой Numerics.BigInteger в F#

Answer 5

Кроме того, при тестировании не забывайте, что косвенная хвостовая рекурсия (tailcall) по умолчанию отключена при компиляции в режиме отладки. Это может привести к переполнению стека рекурсивным вызовом в режиме отладки, но не в режиме выпуска.