Chức năng đệ quy F # Tail Ví dụ

Question

Tôi mới dùng F # và đang đọc về các hàm đệ qui đuôi và hy vọng ai đó có thể cho tôi hai cách triển khai khác nhau của hàm foo - một hàm đệ quy đuôi và cái không phải để tôi có thể hiểu rõ hơn về nguyên tắc.

Answer 1

Bắt đầu bằng một tác vụ đơn giản, như ánh xạ các mục từ 'a đến' b trong danh sách. Chúng tôi muốn viết một hàm trong đó có chữ ký

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

đâu

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

Bắt đầu với không đệ quy đuôi phiên bản:

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

Đây không phải là đệ quy đuôi vì chức năng vẫn còn có việc phải làm sau khi thực hiện cuộc gọi đệ quy. :: là cú pháp đường cho List.Cons(f x, map f xs).

Tính chất không đệ quy của hàm có thể rõ ràng hơn một chút nếu tôi viết lại dòng cuối cùng là | x::xs -> let temp = map f xs; f x::temp - rõ ràng là công việc của nó sau khi thực hiện cuộc gọi đệ quy.

Sử dụng một ắc biến để làm cho nó đuôi đệ quy:

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

Dưới đây là chúng ta đang xây dựng một danh sách mới trong một biến acc. Vì danh sách được xây dựng ngược lại, chúng ta cần đảo ngược danh sách đầu ra trước khi đưa nó trở lại cho người dùng.

Nếu bạn đang ở trong một tâm warp chút, bạn có thể sử dụng tiếp tục đi qua để viết mã ngắn gọn hơn:

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

Kể từ khi cuộc gọi đến loop và cont là chức năng cuối cùng được gọi là không có công việc bổ sung, chúng đệ quy đuôi.

này hoạt động vì sự tiếp tục cont được chụp bởi một sự tiếp nối mới, mà lần lượt được chụp bởi người khác, kết quả là một loại cây giống như cấu trúc dữ liệu như sau:

(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 []))))) 

mà xây dựng một danh sách theo thứ tự mà không yêu cầu bạn đảo ngược nó.

---

Vì giá trị của nó, hãy bắt đầu viết hàm theo cách đệ quy không đuôi, chúng dễ đọc và làm việc hơn.

Nếu bạn có danh sách lớn cần thực hiện, hãy sử dụng biến tích lũy.

Nếu bạn không thể tìm cách sử dụng bộ tích lũy một cách thuận tiện và bạn không có bất kỳ tùy chọn nào khác theo ý của mình, hãy sử dụng tính năng tiếp tục. Cá nhân tôi xem xét việc sử dụng không liên tục, nặng nề của việc tiếp tục khó đọc.

Answer 2

Một cố gắng về một lời giải thích ngắn hơn trong các ví dụ khác:

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 là không đệ quy đuôi, bởi vì foo có gọi foo đệ quy để đánh giá "2 + foo (n-1)" và trả lại.

thanh có đuôi đệ quy, vì thanh không phải sử dụng giá trị trả về của cuộc gọi đệ quy để trả về giá trị. Nó có thể chỉ cho phép thanh được gọi đệ quy trả về giá trị của nó ngay lập tức (mà không trả về tất cả các con đường lên mặc dù ngăn xếp gọi). Trình biên dịch thấy điều này và 'cheats' bằng cách viết lại đệ quy vào một vòng lặp.

Thay đổi dòng cuối cùng trong thanh thành "| _ -> 2+ (thanh (acc + 2) (n-1))" sẽ hủy kết thúc đệ quy đuôi.

Answer 3

Ngoài ra, khi thử nghiệm, đừng quên rằng đệ quy đuôi gián tiếp (tailcall) được tắt theo mặc định khi biên dịch trong chế độ gỡ lỗi. Điều này có thể gây ra đệ quy tailcall để tràn ngăn xếp trong chế độ gỡ lỗi nhưng không ở chế độ phát hành.

Answer 4

Dưới đây là một ví dụ rõ ràng hơn, so sánh nó với những gì bạn thường làm cho giai thừa.

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

Đây là một chút phức tạp, nhưng ý tưởng là bạn có bộ phận tích lũy giữ giá trị trả lại, thay vì sửa đổi giá trị trả lại.

Bên cạnh đó, phong cách này của gói thường là một ý tưởng tốt, như vậy gọi của bạn không cần phải lo lắng về seeding ắc (lưu ý thực tế đó là cục bộ của hàm)

Answer 5

tôi đang học F # quá . Sau đây là các hàm đệ quy không đuôi và đệ quy để tính số mã số.

Non-đuôi phiên bản đệ quy

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

Tail phiên bản đệ quy

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

Lưu ý: kể từ khi số fibanacci có thể phát triển thực sự nhanh chóng, bạn có thể thay thế dòng cuối cùng tfib 0 1 n-
tfib 0I 1I n để tận dụng cấu trúc Numerics.BigInteger trong F #