Đệ quy đệ quy so với đệ quy trước

Question

Ai đó có thể cho tôi sự khác biệt giữa hai kiểu tiếp nhận và ví dụ này (cụ thể trong OCaml)?

Answer 1

Chức năng đệ quy đuôi là hàm mà cuộc gọi đệ quy duy nhất là cuộc gọi đệ quy cuối cùng trong hàm. Một hàm đệ quy không đuôi là một hàm mà không phải là trường hợp.

Một đệ quy lùi là đệ quy trong mỗi lần gọi đệ quy giá trị tham số nhỏ hơn bước trước. Một đệ quy về phía trước là một đệ quy nơi nó phát triển lớn hơn với mỗi bước.

Đó là hai khái niệm trực giao, nghĩa là đệ quy chuyển tiếp có thể hoặc không thể đệ quy đuôi và áp dụng tương tự cho các lần thu thập ngược.

Ví dụ chức năng thừa thường được viết như thế này trong ngôn ngữ bắt buộc:

fac = 1 
for i from 1 to n: 
    fac := fac * i 

Phiên bản đệ quy chung của đếm ngược thừa (tức là nó tự gọi mình với n-1 như tham số), tuy nhiên nếu bạn muốn dịch trực tiếp giải pháp bắt buộc ở trên, bạn sẽ đưa ra một phiên bản đệ quy đếm ngược lên. Nó sẽ trông giống như thế này:

let fac n = 
    let rec loop i = 
    if i >= n 
    then i 
    else i * loop (i+1) 
    in 
    loop 1 

Đây là một đệ quy về phía trước và bạn có thể thấy nó hơi cồng kềnh hơn so với biến thể đệ quy lùi vì nó đòi hỏi một hàm trợ giúp. Bây giờ đây không phải là đệ quy đuôi như cuộc gọi cuối cùng trong loop là phép nhân, không phải đệ quy. Vì vậy, để làm cho nó đuôi-đệ quy, bạn muốn làm điều gì đó như thế này:

let fac n = 
    let rec loop acc i = 
    if i >= n 
    then acc 
    else loop (i*acc) (i+1) 
    in 
    loop 1 1 

Bây giờ đây là cả một đệ quy về phía trước và một đệ quy đuôi vì cuộc gọi đệ quy là a) một cái đuôi gọi và b) gọi riêng của mình có giá trị lớn hơn (i+1).

Answer 2

Dưới đây là một ví dụ về một cái đuôi chức năng thừa đệ quy:

let fac n = 
let rec f n a = 
    match n with 
    0 -> a 
    | _ -> f (n-1) (n*a) 
in 
f n 1 

Dưới đây là nó không đuôi đối đệ quy:

let rec non_tail_fac n = 
match n with 
0 -> 1 
| _ -> (non_tail_fac n-1) * n 

Đuôi hàm đệ quy sử dụng một accumulator, một, để lưu trữ các giá trị của kết quả của cuộc gọi trước đó. Điều này cho phép OCaml thực hiện tối ưu hóa cuộc gọi đuôi mà kết quả trong ngăn xếp không tràn. Thông thường một hàm đệ quy đuôi sẽ sử dụng giá trị tích lũy để cho phép tối ưu hóa cuộc gọi đuôi xảy ra.

Answer 3

Ví dụ: hàm đệ quy build_word lấy một số char list và kết hợp chúng thành một chuỗi tức là ['f'; 'o'; 'o'] thành chuỗi "foo". Quá trình cảm ứng có thể được hiển thị theo cách này:

build_word ['f'; 'o'; 'o'] 
"f"^(build_word ['o'; 'o']) 
"f"^("o"^(build_word ['o']) // base case! return "o" and fold back 
"f"^("o"^("o")) 
"f"^("oo") 
"foo" 

Đó là một đệ quy bình thường. Lưu ý rằng mỗi cặp ngoặc đơn là viết tắt của một khung stack mới hoặc gọi đệ quy. Giải pháp cho vấn đề này (tức là "f", "fo" hoặc "foo") không thể được dẫn xuất trước khi kết thúc đệ quy (trong đó trường hợp cơ sở được đáp ứng). Chỉ khi đó khung cuối cùng mới trả về kết quả cuối cùng về kết quả trước đó trước khi "popping", và ngược lại.

Về lý thuyết, mỗi cuộc gọi sẽ tạo khung ngăn xếp mới (hoặc phạm vi, nếu bạn muốn) để giữ "vị trí" cho giải pháp phân mảnh được trả lại và thu thập về đầu.Điều này có thể dẫn đến stackoverflow (liên kết này là một đệ quy btw).

Đuôi phiên bản cuộc gọi sẽ giống như thế này:

build_word ['f'; 'o'; 'o'] "" 
build_word ['o'; 'o'], "f" 
build_word ['o'] ("f"^"o") 
build_word [] ("f"^"o"^"o") 
"foo" 

Ở đây, kết quả tích lũy (thường được lưu trữ trong một biến gọi là accumulator) đang được thông qua về phía trước. Với tối ưu hóa, cuộc gọi đuôi sẽ không phải tạo một khung ngăn xếp mới vì nó không phải duy trì các khung trước đó. Giải pháp đang được giải quyết "chuyển tiếp" thay vì "lạc hậu".

Sau đây là các build_word chức năng trong hai phiên bản:

không đuôi

let build_word chars = 
    match chars with 
    | [] -> None 
    | [c] -> Some Char.to_string c 
    | hd :: tl -> build_word tl 
;; 

đuôi

let build_word ?(acc = "") chars = 
    match chars with 
    | [] -> None 
    | [c] -> Some Char.to_string c 
    | hd::tl -> build_word ~acc:(acc^Char.to_string hd) tl 
;; 

Các đệ quy về phía trước nổi giải thích trong câu trả lời được chấp nhận bởi @ sepp2k.