斐波納契哈斯克爾

Question

所以這裏有一個斐波那契項，計算功能（在Ruby中）：

def fibfast(n) 
    xs = [0,1] 
    (n-1).times do |i| 
    next_term = xs.sum 
    xs[0]=xs[1] 
    xs[1]=next_term 
    end 
    return xs[1] 
end 

我敢肯定它具有恆定的空間複雜度（其只存儲數據是XS），和線性時間複雜度（它使用一個循環來計算序列的第n項）。

我的問題是，函數是遞歸的嗎？它使用它計算的值來執行更多計算，但從未自行調用。我的另一個問題是，我如何在Haskell中獲得同樣的時空緊湊性？我發現Haskell函數的空間複雜度大於O（1），返回一個完整的術語列表，並且/或者它們的時間複雜度大於O（n），因爲它們使用了典型的遞歸定義。

任何想法感激，謝謝！

Answer 1

我的問題是，函數是遞歸的嗎？它使用它計算的值來執行更多計算，但從未自行調用。

沒有：遞歸意味着東西本身來定義。 fibfast函數本身沒有定義。

我的另一個問題是，我如何在Haskell中獲得相同的時空緊湊性？我發現Haskell函數的空間複雜度大於O（1），返回一個完整的術語列表，並且/或者它們的時間複雜度大於O（n），因爲它們使用了典型的遞歸定義。

您可以使用以下功能：

fibfast :: Int -> Int 
fibfast n = fib' 0 1 n 
    where fib' a b n | n <= 1 = b 
        | otherwise = fib' b (a+b) (n-1) 

所以在這裏我們定義了一個遞歸函數fib'和使用兩個累加器a和最後兩個值存儲在序列中b。每次迭代，兩個更新，我們減少我們必須做的迭代次數，直到它遇到一個小於或等於1的數字n，在這種情況下，我們返回第二個累加器。

一個問題可能是Haskell通常不會熱切地評估表達式，而是懶洋洋地。所以它存儲a+b而不是計算a+b。因此，表達樹很快就會像a+b+a+b+a+b...一樣快速增長。我們可以例如使用爆炸模式：

{-# LANGUAGE BangPatterns #-} 

fibfast :: Int -> Int 
fibfast n = fib' 0 1 n 
    where fib' a !b !n | n <= 1 = b 
         | otherwise = fib' b (a+b) (n-1)