William6947 - 6 months ago 76

C++ Question

I am able to write a recursive Fibonacci function for all numbers greater than 0, but the function is completely incorrect for anything negative. Any idea how to implement this in c++?

`int fibonacci(int n){`

if(n == 0)return 0;

if(n == 1)return 1;

return fibonacci(n - 1) + fibonacci(n - 2);

}

Answer

According to wikipedia, http://en.wikipedia.org/wiki/Generalizations_of_Fibonacci_numbers, the recursive function for negative numbers is different than for possitive numbers.

For possitive:
`n_2 = n_1 + n_0`

For negative:
`n_-2 = n_-1 - n_0`

So that the recursivity works "just the other way around" and the same code will not work. You will have to write a new function.

EDIT: Wikipedia provides the generalization: F_-n = (-1)^n F_n so just compute F_n and modify the sign with (-1)^n