Sceme遞歸的類型

我正在學習Scheme語言（我自己）。最近我遇到了這個問題：有兩個函數計算相同的值（組合函數f - n次）。Sceme遞歸的類型

(define (repeated f n) 
    (lambda (x) 
    (if (= n 1) 
     (f x) 
     (f ((repeated f (- n 1)) x))))) 

(define (repeated f n) 
    (if (= n 1) 
     f 
     (lambda (x) 
     (f ((repeated f (- n 1)) x)))))

據我瞭解，這兩個不是遞歸過程，但他們返回遞歸過程（lol）。那麼這兩者有什麼區別呢？即使在我給X賦值之前，第一個返回已經計算好的過程有可能嗎？我很困惑...請幫助。

來源

2013-04-03 Aladin

兩者都只是更高階的函數（因爲它們返回一個函數）。從概念上說，他們試圖代表的是 – Ankur

謝謝。然而，奧斯卡洛佩斯確實指出了兩者之間的一些細微差別。 – Aladin

事實上，兩個程序都是遞歸，每個程序在執行期間的某個時刻都會調用它自己。另外，兩者都在某個時候返回lambda--這意味着：它們是返回過程的過程。

第一個程序總是返回lambda，而第二步驟的短路，並返回f當n等於1，也爲比1更大的n值返回lambda。所以他們沒有什麼不同，除了處理基本情況（n等於1）的方式。

來源

2013-04-03 14:05:41

謝謝。 '（n等於1）'的解釋（第二程序）對我有很大的幫助。 – Aladin

哇，比我的簡單得多，雖然我是尾遞歸的並且適用於（重複fn 0）asuuming，在參數上運行函數零次就是這個參數。

(define (repeated fn times) 
(let loop (
    (continuation (lambda (x) x)) 
    (count-down times)) 
    (if (not (> count-down 0)) 
     (lambda (x) (continuation x)) 
     (loop (lambda (x) (continuation (fn x))) (- count-down 1)))))

兩個你之間的差別在於，第一返回過程右遠，然後調用本身作爲程序的一部分。第二個函數只有在它完全計算了該過程的結果後才返回一個過程。

這樣第一次返回一個遞歸過程，而第二次使用遞歸返回一個非遞歸過程。礦井的工作方式與第二種方法相似，但可以計算非常大的數值的重新計算，而上面的兩個值將超過最大遞歸深度。（（重複cdr 1000000）（iota 1000589））

來源

2013-05-10 13:24:53 WorBlux

Sceme遞歸的類型

回答

相關問題