斐波那契遞歸函數需要永久

Question

我想要得到斐波那契數列的第48個元素 ，我可以存儲在64位整數中。我正在使用一個遞歸子程序，但它會一直持續下去。如果任何人都可以發現我的遞歸子程序有問題，我將非常感激。

Integer (Int8) :: n 
Integer (Int64) :: fib64 
n = Int (48, Int8) 
Call fibonacci_genr (fib64, n) 

這裏是我的遞歸子程序

Recursive     & 
Subroutine fibonacci_genr & 
(      & 
    fb, n     & 
) 

Integer (Int64), Intent (Out) :: fb 
Integer (Int8), Intent (In) :: n 

    Integer (Int64) :: fb1, fb2 
    If (n < 2) Then 
     fb = Int (n, Int64) 
    Else 
     Call fibonacci_genr (fb1, n-1) 
     Call fibonacci_genr (fb2, n-2) 
     fb = fb1 + fb2 
    End If 
End Subroutine fibonacci_genr 

Answer 1

Appologies我不知道的Fortran I會盡我所能告訴你如何加快它的JavaScript和我最好在FORTRAN解決方案

var memo = []; 
function fib(n) { 
    if (memo[n-1]) { //check to see if you already calculated the answer 
     return memo[n-1]; 
    } 
    memo[n-1] = n <= 1 ? 1 : fib(n - 1) + fib(n - 2); 
    return memo[n-1]; 
} 

這裏是memoized FORTRAN

Integer (Int64) :: memo(48) = 0 

Integer (Int64), Intent (Out) :: fb 
Integer (Int8), Intent (In) :: n 

Integer (Int64) :: fb1, fb2 
If (memo(n) > 1) Then ! if its in the array we just use that value 
    fb = memo(n) 
Else If (n <= 2) Then 
    memo(n) = Int (1, Int64) 
    fb = memo(n) 
Else 
    Call fibonacci_genr (fb1, n-1) 
    Call fibonacci_genr (fb2, n-2) 
    memo(n) = fb1 + fb2 
    fb = memo(n) 
End If 
End Subroutine fibonacci_genr 

Answer 2

計算斐波那契數遞歸這樣會導致重複計算Recursion vs. Iteration (Fibonacci sequence)。爲了避免這種情況，請使用迭代算法。

Answer 3

這是用Python編寫的（同樣沒有FORTRAN）。

def f(a): 
    if (a < 2): 
    return a; 
    return _f(a-2, 2, 1) 

def _f(a, n1 , n2) : 
    if(a==0) : 
    return n1+n2 
    return _f(a-1, n1+n2, n1) 

每個數字只計算一次而不是多次。 _f是一個私有函數f是一個你打電話，

注：這仍然是遞歸的，但只會調用自身48倍（N階）

Answer 4

鑑於Int8=1和Int64=8和顯式接口，gfortran4.7.2抱怨這

call fibonacci_genr(fb1, n-1) 
          1 
Error: Type mismatch in argument 'n' at (1); passed INTEGER(4) to INTEGER(1) 

如果實際的參數被轉換爲Int8

Call fibonacci_genr (fb1, int(n-1, Int8)) 

或Int8文字直接使用（感謝@francescalus）

Call fibonacci_genr (fb1, n - 1_Int8) 

該代碼似乎工作正常。但我認爲這是更易於使用integer :: n，而不是integer(Int8) :: n因爲沒有溢出的n ....

BTW我還測量了時間調用這個例程n = 0到48。在Xeon2.6GHz（x86_64）+ gfortran4.7.2 -O2上達到91秒。如果子程序被功能代替，時間縮短到72秒。爲了進行比較，我還嘗試了下面的代碼在茱莉亞

function fibo(n::Int) # Int defaults to Int64 
    if n <= 1 
     return n 
    else 
     return fibo(n-1) + fibo(n-2) 
    end 
end 

for inp = 0:48 
    println(fibo(inp)) 
end 

花了118秒，所以這個遞歸很不錯。另一方面，直接迭代（沒有遞歸調用）當然是超快速的，只需要012秒，時間就是0.001秒。

Answer 5

該解決方案爲您提供斐波那契數字的線性時間（調用次數==斐波那契數字-2，只有1次調用數字1和2）。這是通過使用返回序列的兩位數字的遞歸函數完成的，以便每次調用都可以計算下一位數字並將前一位數字重新用作其返回值。如果你想調用它只接收新數字，這確實需要一個包裝函數，但這對於減少遞歸是一個小犧牲。

這裏的功能是：

integer(kind=int64) pure function fibonacci(n) 
    use iso_fortran_env 
    implicit none 
    integer, intent(in) :: n 
    integer(kind=int64), dimension(2) :: fibo 

    fibo = fib(int(n,int64)) 
    fibonacci = fibo(1) 
    end function fibonacci 

    recursive pure function fib(n) result(ret) 
    use iso_fortran_env 
    implicit none 
    integer(kind=int64), intent(in) :: n 
    integer(kind=int64), dimension(2) :: tmp,ret 

    if (n == 1_int64) then 
     ret = [1_int64, 0_int64] 
    else if (n == 2_int64) then 
     ret = [1_int64, 1_int64] 
    else 
     tmp = fib(n-1) 
     ret = [sum(tmp), tmp(1)] 
    end if 
    end function fib 

使用這些功能的時間來計算fibonacci(48)是可以忽略不計。