遞歸過程到尾遞歸過程

我想構建一個尾遞歸過程出我已經構建的另一個過程。但我並沒有完全意識到我應該如何思考。我給你兩個例子，其中第一個是我的程序，它不是尾遞歸，第二個是我的「嘗試」做一個尾遞歸過程。是啊...嘗試:)我會很高興的如何構建尾遞歸程序的任何建議，我應該如何開始，思考和什麼。遞歸過程到尾遞歸過程

編輯：第一個完全按照我想要的。 (define square (lambda (x) (* x x)))

(do-to-each square '(1 2 3))應方每一個數字，這是榜上無名(1 4 9)

(define do-to-each 
    (lambda (proc lst) 
    (if (list-empty? lst) 
     (list-create) 
      (list-insert (proc (list-first lst)) (do-to-each proc (list-rest lst)))))) 

(define do-to-each-tail 
    (lambda (proc lst) 
    (define loop 
     (lambda (n result) 
     (if (= n 1) 
      (list result) 
      (if (eq? (length result) 1) 
       (car result) 
       (loop (- n 1) (cons (car result) (do-to-each-tail proc (cdr result)))))))) 
    (loop (length lst) lst)))

來源

2015-10-08 Joel

相關：http://stackoverflow.com/q/27386520/124319 – coredump

啊謝謝，要去看看那個。 :) – Joel

從列表的尾部開始工作的最簡單方法是，結果反過來，然後在基本情況下將結果返回時，再簡單地反轉結果。 – leppie

這是沒有必要跟蹤長度，索引等的，因爲我們可以寫一個尾遞歸解決方案直接迭代輸入列表，累積結果並（僅僅爲了保持順序）反轉結果。

例如，使用您的符號進行列表操作，這是一個可能的解決方案的樣子 - 並注意我們如何將累積結果的初始值稱爲循環輔助程序，之後我們reverse輸出：

(define do-to-each-tail 
    (lambda (proc lst) 
    (define loop 
     (lambda (lst result) 
     (if (list-empty? lst) 
      result 
      (loop (list-rest lst) 
        (list-insert (proc (list-first lst)) result))))) 
    (reverse (loop lst (list-create)))))

它按預期工作：

(do-to-each-tail square '(1 2 3)) 
=> '(1 4 9)

來源

2015-10-08 12:29:50

遞歸過程到尾遞歸過程

回答

相關問題