計劃中斐波那契尾遞歸的解釋？

我一直在試圖理解Scheme中的尾遞歸，並且我很難理解正在發生的事情，例如使用尾遞歸進行Fibonacci ...計劃中斐波那契尾遞歸的解釋？

如果這是尾遞歸的代碼，或者迭代斐波那契：

(define (fib n) 
    (fib-iter 1 0 n)) 

(define (fib-iter a b count) 
    (if (= count 0) 
    b 
    (fib-iter (+ a b) a (- count 1))))

我基本上可以理解爲在每一行，除了發生在這裏：

(fib-iter 1 0 n))

什麼是該行實際上發生了什麼？我無法在任何地方找到解釋。我是Scheme新手，目前語法很混亂。

或者任何人都可以解釋每一行發生了什麼？這是我的基本瞭解，但我不確定我是否正確：

(define (fib n) ;;define the function fib and variable n 
    (fib-iter 1 0 n)) ;;?? no idea 

(define (fib-iter a b count) ;;define function fib-iter, variables a, b and count 
    (if (= count 0) ;;if the count is equal to 0, 
    b ;;return b 
    (fib-iter (+ a b) a (- count 1)))) ;;recursively calling function fib-iter with 3 parameters (a+b), a and (count - 1)

謝謝！

來源

2014-09-28 Sarah

「（定義（FIB N）;定義函數FIB和變量n」沒有那麼 - 這*定義了函數'fib'，它接受一個名爲'n' *的參數。同樣，'（define（fib-iter ...）定義了函數'fib-iter'，它需要3個參數，第一個名爲'a'，2nd爲了顯示tail-recursion是如何工作的，在形式'（fib-iter ab count）'的上面和下面畫兩條水平線，你得到的是一個* frame * - 一個名字然後每次調用'（fib-iter xyz）'只是將三個值'xyz'放入三個插槽（在這種情況下）框架，並（重新）開始執行。 – 2014-09-29 09:41:53

有一個在fib程序（開口括號丟失）一個錯字，應該定義如下：

(define (fib n) 
    (fib-iter 1 0 n))

話雖如此，迭代fib過程使用執行實際被叫fib-iter幫手迭代。此行：

(fib-iter 1 0 n)

簡單地稱呼助手是第一次。正如您所知，斐波那契數列開頭的值爲0，n=0和1爲n=1，這就是我們作爲參數傳遞的值，開始迭代循環以及作爲迭代次數的值n我們希望在停止之前做。

從這一點上來說，a將包含斐波納契的值n-1和b將包含斐波納契的值n-2，並且在迭代每個連續步驟花費相應地更新a和b變量的護理，直到n是零，在這一點上，我們停止並返回結果。

如果我們用命令式編寫相同的算法，可能會更容易描繪發生的情況。以下是Python中的一個使用顯式循環結構和相同變量名稱的示例。這相當於Scheme的實現：

def fib(n): 
    count = n 
    a, b = 1, 0 
    while count != 0: 
     a, b = a + b, a 
     count = count - 1 
    return b

來源

2014-09-28 21:43:15

我不明白爲什麼它不會（fib-iter 0 1 n） – Sarah 2014-09-28 21:56:41

非常感謝！我終於可以圍繞它環繞我 – Sarah 2014-09-28 22:02:14

@Sarah如果'fib-iter'寫得有點不同，例如'（if（zero？count）a（fib-iter b（+ ab）（ - count 1 ）））'。但在你的情況下，'a'和'b'的作用是從它們的常規意義上交換的。 – 2014-09-28 22:22:24

在代碼中存在錯誤; fib應該是一個過程：

(define (fib n) 
    (fib-iter 1 0 n))

是什麼做的是它調用fib-iter用（= 1），B的初始值（= 0）和count（=你想要的斐波那契數，這是正規參數n至fib）。

添加打印 '說明' fib-iter顯示會發生什麼，在這個例子(fib 7)：

a=1 b=0 count=7 ; initial values as given by `fib` 
a=1 b=1 count=6 
a=2 b=1 count=5 
a=3 b=2 count=4 
a=5 b=3 count=3 
a=8 b=5 count=2 
a=13 b=8 count=1 
a=21 b=13 count=0 
13 ; the returned value for `(fib 7)`

來源

2014-09-28 21:43:29 uselpa

計劃中斐波那契尾遞歸的解釋？

回答

相關問題