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.

duedl0r · Accepted Answer · 2018-08-29T21:27:33.370

45

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..

edited Aug 29 '18 at 21:27

answered Dec 11 '12 at 19:11

duedl0r

9,289
3
30
45

This was exactly what I was looking for. I didn't know that it's called "tail recursion" in English. Great thanks, mate! – ducin Dec 11 '12 at 20:34
13

Or you could just implement it as a loop in the first place, doh! – Tyler Durden Dec 11 '12 at 20:46
16

@TylerDurden: the question is about fast recursion. – duedl0r Dec 12 '12 at 08:26
2

This still grows in O(n), you can find O(log n) algorithms which are way faster https://www.nayuki.io/page/fast-fibonacci-algorithms (linked in other answers) – Ludovic Migneault May 31 '16 at 17:15
Two `if`s are redundant. You should only have either one. – hakatashi Dec 05 '16 at 01:40
@hakatashi please show me how this code would look like with single if – Filip Bartuzi Jul 07 '17 at 06:53
@FilipBartuzi Just delete either line and it works (for n >= 1). https://ideone.com/1l4gCb – hakatashi Jul 07 '17 at 07:54
Should it be return fib(term -1, val, val+prev)? – CrazyFrog Sep 12 '18 at 16:09

score 11 · Answer 2 · answered Dec 11 '12 at 19:24

11

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.

answered Dec 11 '12 at 19:24

plesiv

6,935
3
26
34

Óscar López · Answer 3 · 2012-12-11T20:48:55.917

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)

@tkoomzaaskz I updated my answer with another possible solution, FYI. — Óscar López, Dec 11 '12 at 20:50

Moch Lutfi · Answer 4 · 2015-04-28T06:20:18.533

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

From article also included iterative version on C# http://www.nayuki.io/res/fast-fibonacci-algorithms/fastfibonacci.cs — Moch Lutfi, Apr 28 '15 at 06:07

score 3 · Answer 5 · answered Dec 11 '12 at 19:11

3

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

answered Dec 11 '12 at 19:11

monkeyking

6,670
24
61
81

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. – ducin Dec 11 '12 at 19:14

Sebastian Sastre · Answer 6 · 2017-05-17T14:59:15.987

1

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

edited May 17 '17 at 14:59

answered Jun 06 '15 at 17:06

Sebastian Sastre

2,034
20
21

score 0 · Answer 7 · answered Jan 02 '16 at 13:55

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

HNoob · Answer 8 · 2018-01-16T16:00:33.633

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.

score 0 · Answer 9 · answered Feb 03 '17 at 16:40

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

Just use an array to store the value.
Check the array if you have already calculate it.
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

Fast Fibonacci recursion

9 Answers9

Linked