Fast Fibonacci recursion

Question

I'm trying to recall an algorithm on Fibonacci recursion. The following:

public int fibonacci(int n)  {
  if(n == 0)
    return 0;
  else if(n == 1)
    return 1;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

is not what I'm looking for because it's greedy. This will grow exponentially (just look at Java recursive Fibonacci sequence - the bigger the initial argument the more useless calls will be made).

There is probably something like a "cyclic argument shift", where calling previous Fibonacci value will retrieve value instead of calculating it again.

Framework

Answer 1

maybe like this:

int fib(int term, int val = 1, int prev = 0)
{
 if(term == 0) return prev;
 return fib(term - 1, val+prev, val);
}

this function is tail recursive. this means it could be optimized and executed very efficiently. In fact, it gets optimized into a simple loop..

Quasijudicial

This was exactly what I was looking for. I didn't know that it's called "tail recursion" in English. Great thanks, mate! – Framework

Or you could just implement it as a loop in the first place, doh! – Decretive

@TylerDurden: the question is about fast recursion. – Quasijudicial

This still grows in O(n), you can find O(log n) algorithms which are way faster nayuki.io/page/fast-fibonacci-algorithms (linked in other answers) – Tintometer

Two ifs are redundant. You should only have either one. – Greensboro

@Greensboro please show me how this code would look like with single if – Dnieper

@FilipBartuzi Just delete either line and it works (for n >= 1). ideone.com/1l4gCb – Greensboro

Should it be return fib(term -1, val, val+prev)? – Oblast

Answer 2

This kind of problems are linear recurrence types and they are solved fastest via fast matrix exponentiation. Here's the blogpost that describes this kind of approach concisely.

Weitzel

Answer 3

You can do a pretty fast version of recursive Fibonacci by using memoization (meaning: storing previous results to avoid recalculating them). for example, here's a proof of concept in Python, where a dictionary is used for saving previous results:

results = { 0:0, 1:1 }

def memofib(n):
    if n not in results:
        results[n] = memofib(n-1) + memofib(n-2)
    return results[n]

It returns quickly for input values that would normally block the "normal" recursive version. Just bear in mind that an int data type won't be enough for holding large results, and using arbitrary precision integers is recommended.

A different option altogether - rewriting this iterative version ...

def iterfib(n):
    a, b = 0, 1
    for i in xrange(n):
        a, b = b, a + b
    return a

... as a tail-recursive function, called loop in my code:

def tailfib(n):
    return loop(n, 0, 1)

def loop(i, a, b):
    if i == 0:
        return a
    return loop(i-1, b, a+b)

Amersham

@tkoomzaaskz I updated my answer with another possible solution, FYI. – Chambertin

Answer 4

I found interesting article about fibonacci problem

here the code snippet

# Returns F(n)
def fibonacci(n):
    if n < 0:
        raise ValueError("Negative arguments not implemented")
    return _fib(n)[0]


# Returns a tuple (F(n), F(n+1))
def _fib(n):
    if n == 0:
        return (0, 1)
    else:
        a, b = _fib(n // 2)
        c = a * (2 * b - a)
        d = b * b + a * a
        if n % 2 == 0:
            return (c, d)
        else:
            return (d, c + d)

# added iterative version base on C# example
def iterFib(n):
    a = 0
    b = 1
    i=31
    while i>=0:
        d = a * (b * 2 - a)
        e = a * a + b * b
        a = d
        b = e
        if ((n >> i) & 1) != 0:
            c = a + b;
            a = b
            b = c
        i=i-1
    return a

Hanshaw

How about an iterative version? – Animation

From article also included iterative version on C# nayuki.io/res/fast-fibonacci-algorithms/fastfibonacci.cs – Hanshaw

Answer 5

Say you want to have the the n'th fib number then build an array containing the preceeding numbers

int a[n];
a[0] = 0;
a[1] =1;
a[i] = n[i-1]+n[n-2];

Epitasis

There is a solution without storing values in an array. If you call f(n), each numbers (n, n-1, n-2, ..., 1, 0) will be calculated exactly once. – Framework

Answer 6

An example in JavaScript that uses recursion and a lazily initialized cache for added efficiency:

var cache = {};

function fibonacciOf (n) {
  if(n === 0) return 0;
  if(n === 1) return 1;
  var previous = cache[n-1] || fibonacciOf(n-1);
  cache[n-1] = previous;
  return previous + fibonacciOf(n-2);
};

Colatitude

Answer 7

duedl0r's algorithm translated to Swift:

func fib(n: Int, previous: (Int, Int) = (0,1)) -> Int {
    guard n > 0 else { return 0 }
    if n == 1 { return previous.1 }
    return fib(n - 1, previous: (previous.1, previous.0 + previous.1))
}

worked example:

fib(4)
= fib(4, (0,1) )
= fib(3, (1,1) )
= fib(2, (1,2) )
= fib(1, (2,3) )
= 3

Indoaryan

Answer 8

A good algorithm for fast fibonacci calculations is (in python):

def fib2(n):
    # return (fib(n), fib(n-1))
    if n ==  0: return (0,  1)
    if n == -1: return (1, -1)
    k, r = divmod(n, 2) # n=2k+r
    u_k, u_km1 = fib2(k)
    u_k_s, u_km1_s = u_k**2, u_km1**2  # Can be improved by parallel calls
    u_2kp1 = 4 * u_k_s - u_km1_s + (-2 if k%2 else 2)
    u_2km1 = u_k_s + u_km1_s
    u_2k   = u_2kp1 - u_2km1
    return (u_2kp1, u_2k) if r else (u_2k, u_2km1)

def fib(n):
    k, r = divmod(n, 2) # n=2k+r
    u_k, u_km1 = fib2(k)
    return (2*u_k+u_km1)*(2*u_k-u_km1)+(-2 if k%2 else 2) if r else u_k*(u_k+2*u_km1)

If you need very fast computation, links to the libgmp and use mpz_fib_ui() or mpz_fib2_ui() functions.

Lukas

Answer 9

You need to memorize the calculated value in order to stop exponential growth.

1. Just use an array to store the value.
2. Check the array if you have already calculate it.
3. If it finds it,use it or otherwise calculate it and store it.

Here is an working example for faster recursion using memory.

Calculating fibonacci number

Goral

Answer 10

What you can do is create a hash map that stores the value of the fibonnaci number at nth position with its result like follows

private static Map<Integer, Long> memo = new HashMap<>();

and just like the original solution you gave, we can add one more else if condition where we check if the fibonacci value of the number is present in the hash map we created like:

private static Map<Integer, Long> hmap = new HashMap<>();

public long fibonacci(int n){
    if(n <=1){
        return n;
    }
    else if (hmap.containsKey(n)) {
        return hmap.get(n);
    }
    else {
        long result = fibonacci(n - 1) + fibonacci(n - 2);
        hmap.put(n, result);
        return result;
    }
}  

This is also called as Memoization

Dikdik