What does this recursive function do?

Question

I got this question in an interview. So, this seems to me a messed up Fibonacci seq. sum generator and this gives a stackoverflow. Because if(n==0) should be if(n<3) (exit condition is wrong). What should be the precise answer to this question? What was expected as an answer?

foo (int n) {
if (n == 0) return 1;
return foo(n-1) + foo(n-2);
}

UPDATE

What does this recursive function do?

What do you infer when you see these 3 lines of code. No debugging.

Answer 1

Yes, it's just a recursive Fibonacci method with an incorrect base case (although I don't think I'd use n < 3 either... it depends on how you define it).

As for "what was expected as an answer" - that would depend on the question. Were you asked exactly the question in the title of your post? If so, the answer is "it recurses forever until it blows up the stack when you pass it any value other than 0" - with an explanation, of course. (It will never end because either n-1 isn't 0, or n-2 isn't 0, or both.)

EDIT: The above answers the first question. To answer "What do you infer when you see these 3 lines of code" - I would infer that the developer in question has never run the code with a value other than 0, or doesn't care about whether or not the code works.

Answer 2

The problem with the code posted is that if we evaluate foo(1) we need to find foo(0) and foo (-1), foo(-1) then needs to find foo(-2) and foo(-3) and so on. This will keep putting more calls to foo() until there is no more space in the memory resulting in a stack overflow. How many calls to foo are made will depend on the size of the call stack, which will be implementation specific.

When I see these lines of code I immediately get the impression that whoever wrote it hasn't thought about all the possible inputs that could be fed to the function.

To make a recursive Fibonacci function that doesn't fail for foo(1) or a negative input we get:

foo (int n) {
  if( n < 0 ) return 0;
  if (n == 0) return 1;
  return foo(n-1) + foo(n-2);
}

Edit: perhaps the return for a negative number should be something else, as the fibonacci sequence isn't implicitly defined for negative indexes.

However if we use the extension that fib(-n) = (-1)^(n+1) fib(n) we could get the following code:

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

Answer 3

suppose, you call foo ( 1 ), it will have two sub calls of foo(0) and foo(-1). As you can see, once you get to foo(-1), n will decrease indefinitely and will never reach a terminating condition.

The precise answer would be:

foo (int n) {
 if (n <= 1) return 1; // assuming 0th and 1st fib is 1
 return foo(n-1) + foo(n-2);
}

Answer 4

    int fib (int n)
    {
      cout << "Processing fib(" << n << ")... ";

      if (n < 3 )
      {
         cout << "Return 1!\n";
         return (1);
      }
      else
      {
        cout << "Call fib(" << n-2 << ") and fib(" << n-1 << ").\n";
        return( fib(n-2) + fib(n-1));
      } 
 }

Answer 5

Its a recursive fibonacci function with 0th element being 1.

Answer 6

Ignoring the incorrect termination condition, the code is the "naive" recursive implementation of the Fibonacci function. It has very poor big-O time complexity. It would work fine for small n, but if n is greater than say 50 (I'm just guessing that number), then it would take "forever" to run.