Cách tốt để viết lại hàm không đệ quy này là gì?

Question

Vì một lý do nào đó, tôi đang gặp khó khăn khi nghĩ về cách tốt để viết lại hàm này để nó sử dụng không gian ngăn xếp liên tục. Hầu hết các cuộc thảo luận trực tuyến về cheat đệ quy cây bằng cách sử dụng hàm Fibonacci và khai thác các thuộc tính của vấn đề cụ thể đó. Có ai có bất kỳ ý tưởng cho "thế giới thực" này (tốt hơn thế giới thực hơn dãy Fibonacci) sử dụng đệ quy?

Clojure là một trường hợp thú vị vì nó không có tối ưu hóa cuộc gọi đuôi, nhưng chỉ đệ quy đuôi thông qua biểu mẫu đặc biệt "recur". Nó cũng khuyến khích mạnh mẽ việc sử dụng trạng thái có thể thay đổi. Nó có nhiều cấu trúc lười biếng bao gồm tree-seq, nhưng tôi không thể xem chúng có thể giúp tôi như thế nào cho trường hợp này. Bất cứ ai cũng có thể chia sẻ một số kỹ thuật họ đã chọn từ C, Scheme, Haskell, hoặc các ngôn ngữ lập trình khác?

(defn flatten [x] 
    (let [type (:type x)] 
    (cond (or (= type :NIL) (= type :TEXT)) 
      x 
      (= type :CONCAT) 
      (doc-concat (flatten (:doc1 x)) 
         (flatten (:doc2 x))) 
      (= type :NEST) 
      (doc-nest (:level x) 
        (flatten (:doc x))) 
      (= type :LINE) 
      (doc-text " ") 
      (= type :UNION) 
      (recur (:doc1 x))))) 

chỉnh sửa: Theo yêu cầu trong các ý kiến ​​...

Trình bày lại một cách chung chung và sử dụng Scheme - làm thế nào để tôi viết lại mô hình đệ quy sau vì vậy nó không tiêu thụ không gian ngăn xếp hoặc yêu cầu mòn đuôi tối ưu hóa cuộc gọi không tự gọi?

(define (frob x) 
    (cond ((foo? x) 
     x) 
     ((bar? x) 
     (macerate (f x) (frob (g x)))) 
     ((thud? x) 
     (frobnicate (frob (g x)) 
        (frob (h x)))))) 

tôi đã chọn tên gây phiền nhiễu để lái xe về nhà điểm mà tôi đang tìm kiếm câu trả lời mà không dựa trên tính chất đại số của x, ngâm, frobnicate, f, g, h hay. Tôi chỉ muốn viết lại đệ quy.

CẬP NHẬT:

Giàu Hickey đã vui lòng thêm một rõ ràng trampoline function để Clojure.

Answer 1

Xin đừng downvote điều này bởi vì nó xấu xí. Tôi biết nó xấu xí. Nhưng đó là một cách để làm điều đó trong phong cách trampoline (không có tràn ngăn xếp hệ thống), và không sử dụng gotos.

push x,1 on homemade stack 
while stack length > 1 
    n = pop 
    if (n==1) 
    x = pop 
    if (type(x)==NIL || type(x)==TEXT) 
     push x // this is the "return value" 
    else if (type(x)==CONCAT) 
     push 2 // say call doc-concat 
     push doc2(x), 1 // 2nd recursion 
     push doc1(x), 1 // 1st recursion 
    else if (type(x)==NEST) 
     push 3 // say call doc-nest 
     push level(x) // push level argument to doc-nest 
     push doc(x), 1 // schedule recursion 
    else if (type(x)==LINE) 
     push " " // return a blank 
    else if (type(x)==UNION) 
     push doc1(x), 1 // just recur 
    else if (n==2) 
    push doc-concat(pop, pop) // finish the CONCAT case 
    else if (n==3) 
    push doc-nest(pop, pop) // finish the NEST case 
    endif 
endwhile 
// final value is the only value on the stack 

Answer 2

Rào cản chính để dễ dàng chuyển đổi thuật toán của bạn là nó không dẫn đến một chuỗi các cuộc gọi đến cùng một chức năng; nhưng thay đổi giữa một vài cái, mỗi cái hoạt động trên kết quả của cái kia.

tôi muốn nói rằng bạn có ba lựa chọn:

1. hoàn toàn tái cấu trúc các thuật toán (đó là những gì các ví dụ Fibonacci làm).
   • kết hợp tất cả các chức năng vào một đơn có nhiều dấu (xấu xí, và có thể sẽ không dẫn đến việc đệ quy đuôi thực, ngay cả với một hàm duy nhất).
   • chuyển luồng trong ra ngoài: viết một hàm đệ quy đuôi đơn giản, đơn giản, biến đổi dữ liệu đầu vào thành chuỗi các thao tác phải được thực hiện và sau đó đánh giá nó.

Answer 3

Nếu flatten cuộc gọi riêng của mình hai lần (trong: trường hợp CONCAT) làm thế nào nó có thể được biến thành một vòng lặp? Có lẽ tôi đang thiếu một cái gì đó. Dường như nó vốn là một cây đi bộ. Tôi có nghĩa là, có nhiều cách để làm một cây đi bộ mà không có ngăn xếp, nhưng một cái gì đó phải được unbounded, giống như nếu bạn làm điều đó với một FIFO, hoặc như đã được đề xuất, với sự tiếp tục.

Answer 4

Bạn có thể sử dụng liên tục-qua:

(define (frob0 x k) 
    (cond ((foo? x) 
     (k x)) 
     ((bar? x) 
     (frob0 (g x) 
      (lambda (y) 
      (k (macerate (f x) y)))) 
     ((thud? x) 
     (frob0 (g x) 
      (lambda (y) 
      (frob0 (h x) 
       (lambda (z) 
       (k (frobnicate y z)))))))) 

(define (frob x) 
    (frob0 x (lambda (y) y)) 

này sẽ không làm cho mọi việc dễ dàng hơn để hiểu :-(

Answer 5

Điều tốt nhất tôi có thể đưa ra là một cái gì đó như thế này:

(define (doaction vars action) 
    (cond ((symbol=? action 'frob) 
     (cond ((foo? (first vars)) 
       (first vars)) 
       ((bar? (first vars)) 
       (doaction (list (f (first vars)) (doaction (g x) 'frob)) 'macerate) 
etc... 

Nó không hoàn toàn đuôi đệ quy, nhưng có thể là tốt nhất bạn có thể nhận được.TCO thực sự là con đường để đi. (Tôi hiểu rằng Clojure không thể có nó do JVM)

Answer 6

Kỹ thuật chung chuẩn là chuyển đổi thành trampolined style. Đối với vấn đề cụ thể của bạn (thực hiện combinators prettyprinting) bạn có thể tìm thấy hữu ích Derek Oppen 1980 giấy "Prettyprinting" (không phải trên web AFAIK). Nó trình bày một thuật toán bắt buộc dựa trên ngăn xếp tương tự như thuật toán sau của Wadler.

Answer 7

Sau đây không phải là câu trả lời cụ thể cho câu hỏi của bạn, nhưng hy vọng đây sẽ là một ví dụ hữu ích. Nó thay thế nhiều lần thu thập (nếu không sẽ yêu cầu một ngăn xếp cuộc gọi không bị chặn) với một chồng các nhiệm vụ.

(trong mã Haskellish):

 
data Tree = Null | Node Tree Val Tree
 

-- original, non-tail-recursive function: flatten :: Tree -> Result flatten Null = nullval flatten (Node a v b) = nodefunc (flatten a) v (flatten b)
 

-- modified, tail-recursive code: data Task = A Val Tree | B Result Val
 

eval :: Tree -> [Task] -> Result use :: Result -> [Task] -> Result
 

eval Null tasks = use nullval tasks eval (Node a v b) tasks = eval a ((A v b):tasks)
 

use aval ((A v b):tasks) = eval b ((B aval v):tasks) use bval ((B aval v):tasks) = use (nodefunc aval v bval) tasks use val [] = val
 

-- actual substitute function flatten2 :: Tree -> Result flatten2 tree = eval tree []