F # Рекурсивная функция хвоста Пример

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 является хвостовым рекурсивным, потому что для возврата значения бар не требуется использовать возвращаемое значение рекурсивного вызова. Он может просто позволить рекурсивно называемому бару возвращать свое значение сразу (не возвращаясь полностью, хотя вызывающий стек). Компилятор видит это и «обманывает», переписывая рекурсию в цикл.

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

Answer 3

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

Answer 4

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

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

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

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

Answer 5

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

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

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

Tail рекурсивная версия

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

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