Fibonacci Recursive function takes forever

Question

I want to get the 48th element of the Fibonacci sequence which I can store in a 64 bit integer. I am using a recursive subroutine, but it is taking forever to finish. If anyone can find a problem with my recursive subroutine, I would be very grateful.

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

Here is my recursive subroutine

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 I don't know fortran I'll try my best to show you how to speed it up in javascript and my best at a fortran solution

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];
}

Here is the 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

Given that Int8=1 and Int64=8 and explicit interface, gfortran4.7.2 complains that

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

If the actual arguments are cast to Int8

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

or Int8 literals are used directly (thanks to @francescalus)

Call fibonacci_genr (fb1, n - 1_Int8 )

the code seems to work fine. But I think it is much simpler to use integer :: n rather than integer(Int8) :: n because there is no overflow for n....

BTW I also measured the time for calling this routine for n = 0 to 48. It was 91 sec on Xeon2.6GHz(x86_64) + gfortran4.7.2 -O2. The time reduced to 72 sec if the subroutine is replaced by a function. For comparison, I also tried the following code in 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

took 118 sec and so pretty good for this recursion. On the other hand, direct iteration (without recursive calls) is of course superfast and takes only <0.001 sec.

Answer 3

This solution gives you a fibonacci digit in linear time (# of calls == fibonacci digit -2, and only 1 call for digits 1 and 2). This is accomplished by using a recursive function that returns two digits of the sequence so that each call can calculate the next digit and re-use the previous digit as its return values. This does require a wrapper function if you want to call it to receive only the new digit, but this is a small sacrifice for reduced recursion.

Here are the functions:

  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

Using these functions the time to calculate fibonacci(48) is negligible.

Answer 4

Calculating Fibonacci recursively like this leads to repeated calculations Recursion vs. Iteration (Fibonacci sequence) . To avoid this, use an iterative algorithm.

Answer 5

This is written in Python (again no 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)

Each number is only calculated once instead of multiple times. _f is a private function f is the one you call,

Note: this is still recursive but will only call itself 48 times (order N)