斐波那契递归函数需要永远

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

像这样递归计算斐波那契会导致重复计算Recursion vs. Iteration (Fibonacci sequence)。为避免这种情况，请使用迭代算法。

Answer 2

Appologies 我不知道 fortran 我会尽力向您展示如何在 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];
}

这是记忆的 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 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 没有溢出......

顺便说一句，我还测量了 n = 0 到 48 调用此例程的时间。在 Xeon2.6GHz(x86_64) + gfortran4.7.2 -O2 上为 91 秒。如果将子程序替换为函数，则时间减少到 72 秒。为了比较，我还在 Julia

中尝试了以下代码

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 秒，非常适合这个递归。另一方面，直接迭代（没有递归调用）当然是超快的，只需要 <0.001 秒。

Answer 5

此解决方案在线性时间内为您提供斐波那契数位（调用次数 == 斐波那契数位 -2，并且只有 1 次调用用于数字 1 和 2）。这是通过使用 return 序列的两个数字的递归函数来实现的，以便每次调用都可以计算下一个数字并重新使用前一个数字作为其 return 值。如果你想调用它来接收新数字，这确实需要一个包装函数，但这是减少递归的一个小牺牲。

函数如下：

  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) 的时间可以忽略不计。

斐波那契递归函数需要永远

Fibonacci Recursive function takes forever

recursion

fortran

fibonacci