Write codes for the Nth Fibonacci number.

Question

Anoniem · Accepted Answer

You were actually asked to write two versions, one is the recursive one, and the other non-recursive. Then explain why the recursive one is very bad.

Anoniem · Answer

The recursive solution is terrible, because it takes exponential time. The iterative solution isn't bad - this takes O(n) time. It's possible to do O(log n) time using Binet's formula.

AlexB · Answer

int fib_rec(int n)
{
    switch(n)
    {
        case 0:
            return 0;
        case 1:
            return 1;
    }
    return fib_rec(n-2) + fib_rec(n-1);
}

int fib_iter(int n)
{
    switch(n)
    {
        case 0:
            return 0;
        case 1:
            return 1;
    }
    
    int f0=0;
    int f1=1;
    
    for(int i=2;i<=n;++i)
    {
        int f2=f0+f1;
        f0=f1;
        f1=f2;
    }
    return f1;
}

Jump Trading

Sollicitatievraag bij Jump Trading

Antwoorden op sollicitatievragen

Gevolgde bedrijven

Vacatures