Java Recursion Fibonacci Value

Question

Question: How many calls are needed to recursively calculate the 7th Fibonacci value?

So this was a problem given to me and the answer was given to me as 41. Then I went to a professor because I didn't understand it, but I was given another answer. I think it was 25? (don't quote me on that) Then I went to another professor... and he told me the person who gave you this problem should have given you the sample code because there can be multiple ways to write this recursive function which would result in different amounts of calls.

So if this is true can you guys find different recursive functions that would result in a different amount of calls needed to get the 7th value of the sequence?

Answer 1

One way:

static long fibonacciR(int i)
{
    if (i <= 1)
        return i;
    return fibonacciR(i - 1) + fibonacciR(i - 2);
}

Another way:

static final int    f[] = {0,1,1,2,3,5,8,13,21,34,55,89,144};
static long fibonacciR2(int i)
{
    if (i < f.length)
        return f[i];
    return fibonacciR2(i-1)+fibonacciR2(i-2);
}

In fact 'another' way is any number of other ways, depending on how big you make the table. When the table has two elements both methods are equal. When it has three there are 25 calls. When 4, 15. And so on.

Yet another way, to get specifically 25 calls:

static long fibonacciR3(int i)
{
    if (i == 0)
        return 0;
    if (i <= 2)
        return 1;
    return fibonacciR(i - 1) + fibonacciR(i - 2);
}