Ruby Fibonacci示例

Question

class Fibonacci 
    def calc(n) 
    return n if n < 2 
    return calc(n - 1) + calc(n - 2) 
    end 
end 

puts Fibonacci.new.calc(40) 
>> 102334155 

我想說明這個程序。我知道它遞歸調用calc方法兩次，如果它不是0或1，但我不明白它是如何工作得到序列的正確數字。

我知道這是我的經驗不足，但有人可以向我解釋這是如何正確計算fib序列？這只是不點擊我。

Answer 1

當您無法理解代碼在做什麼時，您可能不得不使用puts語句對其進行醃製。對於遞歸，改變縮進以顯示方法何時調用自身以及方法何時返回也很有幫助。這是你可能爲你的代碼做的一種方法。

INDENT = 4 
@tabs = 0 

def calc(n) 
    pr_indent 
    puts "entered calc(#{n})" 
    if n < 2 
    pr_indent 
    puts "returning n=#{n}" 
    @tabs -= 1 
    return n 
    end 
    pr_indent 
    puts "calling calc(#{n-1})" 
    @tabs += 1 
    m1 = calc(n-1) 
    pr_indent 
    puts "calc(#{n-1}) returned m1=#{m1} to calc(#{n})" 
    pr_indent 
    puts "calling calc(#{n-2})" 
    @tabs += 1 
    m2 = calc(n-2) 
    pr_indent 
    puts "calc(#{n-2}) returned m2=#{m2} to calc(#{n-1})" 
    pr_indent 
    puts "returning m1+m2=#{m1+m2}" 
    @tabs -= 1 
    m1+m2 
end 

def pr_indent 
    print "#{' '*(@tabs*INDENT)}" 
end 

現在執行

calc(4) 

導致以下將要打印。我不會提供正在運行的註釋，當您在逐步執行代碼時閱讀所打印的內容時，應該不言自明。

entered calc(4) 
calling calc(3) 
    entered calc(3) 
    calling calc(2) 
     entered calc(2) 
     calling calc(1) 
      entered calc(1) 
      returning n=1 
     calc(1) returned m1=1 to calc(2) 
     calling calc(0) 
      entered calc(0) 
      returning n=0 
     calc(0) returned m2=0 to calc(1) 
     returning m1+m2=1 
    calc(2) returned m1=1 to calc(3) 
    calling calc(1) 
     entered calc(1) 
     returning n=1 
    calc(1) returned m2=1 to calc(2) 
    returning m1+m2=2 
calc(3) returned m1=2 to calc(4) 
calling calc(2) 
    entered calc(2) 
    calling calc(1) 
     entered calc(1) 
     returning n=1 
    calc(1) returned m1=1 to calc(2) 
    calling calc(0) 
     entered calc(0) 
     returning n=0 
    calc(0) returned m2=0 to calc(1) 
    returning m1+m2=1 
calc(2) returned m2=1 to calc(3) 
returning m1+m2=3 

和calc(4)回報3。

Answer 2

讓我們用n == 3爲例：

第一次迭代：n不是0或1，使保護條款將不會是真的。所以我們計算calc(2) + calc(1)。我們打電話給calc(1) + calc(0)。這兩個都滿足guard條款，因此分別返回1和0。所以這個計算的結果是1。

致電calc(1)：保護子句觸發器並返回1。

我們現在加起來兩個1 s並得到正確的結果，2。

試着對n應用相同的推理，並記住這個實現非常浪費，因爲它會重複計算相同的值。