Пример рекурсивной функции 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) по умолчанию отключена при компиляции в режиме отладки. Это может привести к переполнению стека рекурсивным вызовом в режиме отладки, но не в режиме выпуска.