方案尾遞歸/迭代

我已經在方案中構建了遞歸函數，它將在某些輸入上重複給定函數f，n次。方案尾遞歸/迭代

(define (recursive-repeated f n) 
    (cond ((zero? n) identity) 
     ((= n 1) f) 
     (else (compose f (recursive-repeated f (- n 1))))))

我需要建立與尾遞歸，我想我已經做了正確的，如果我沒有理解錯的尾遞歸這個函數的迭代版本。

(define (iter-repeated f n) 
    (define (iter count total) 
    (if (= count 0) 
     total 
     (iter (- count 1) (compose f total)))) 
    (iter n identity))

我的問題是，這實際上是迭代？我相信我已經使用尾遞歸正確地構建了它，但是它仍然在技術上推遲了一系列操作，直到count = 0，然後執行堆疊的許多組合。

來源

2016-02-01 Eddie V

爲什麼會「推遲了一堆作業，直到N = 0」？在'count = 0'時，你只能返回'total'，這可能是最簡單的工作，幾乎沒有任何成本。 –

對，但我想說的是，當你返回總數時，它返回一堆操作，如 '（撰寫方（撰寫方（撰寫方（身份x））））' 它評估當返回總數而不是發生尾部呼叫時。或者我只是過度這樣過度？ –

@EddieV在函數被調用之前，函數的所有參數都被評估。 – molbdnilo

你提出了一個很好的問題。你從一個遞歸過程（recursive-repeated）開始，它建立一個遞歸過程（(f (f (f ...)))）到一個迭代過程（iter-repeated），它建立了相同的遞歸過程。

你說得對，因爲最終的結果是一樣的，所以你基本上做了同樣的事情。你只是用兩種不同的方式構建了同一條鏈。這是在您的實施中使用compose的「後果」。

考慮使用此方法

(define (repeat n f) 
    (λ (x) 
    (define (iter n x) 
     (if (zero? n) 
      x 
      (iter (- n 1) (f x)))) 
    (iter n x)))

在這裏，而不是建立的功能的整個鏈條調用時間提前，我們將返回等待輸入參數單一的λ。當輸入參數被指定時，我們將以迭代方式在lambda表達式中循環n次。

讓我們來看看它的工作

(define (add1 x) (+ x 1)) 

;; apply add1 5 times to 3 
(print ((repeat 5 add1) 3)) ;; → 8

來源

2016-02-01 17:54:52 naomik

是的，一個很好的方法使它恆定空間迭代。 – WorBlux

方案尾遞歸/迭代

回答

相關問題