[Solved] Why Fibonacci recursive algorithm working too slow ? [closed]

by


The classic recursive implementation of fib is this:

int fib(int n) {
    if (n < 2)
        return n;
    else
        return fib(n - 1) + fib(n - 2);
}

This function recurses so many times, it is used as an easy benchmark to measure function call efficiency in various languages, with a time complexity of O(φn).

You want an iterative implementation that will perform like a charm:

int fib(int n) {
    int a = 0, b = 1, c = n;
    while (n --> 1) {  // (n --> 1) is parsed as (n-- > 1)
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

0

solved Why Fibonacci recursive algorithm working too slow ? [closed]