William6947 William6947 - 1 month ago 22
C++ Question

Recursive Fibonacci Function (With Negative Numbers)

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