递归斐波那契函数（带负数） [英] Recursive Fibonacci Function (With Negative Numbers)

问题描述

我可以为大于0的所有数字编写递归的Fibonacci函数，但对于任何负数，该函数都是完全不正确的。任何想法如何在c ++中实现这一点？

  int fibonacci（int n）{
 if（n == 0 ）返回0; 
 if（n == 1）return 1; 
 
 return fibonacci（n  -  1）+ fibonacci（n  -  2）; 
 
 $ / code> 




解决方案

href =http://en.wikipedia.org/wiki/Generalizations_of_Fibonacci_numbers =nofollow> http://en.wikipedia.org/wiki/Generalizations_of_Fibonacci_numbers ，负数的递归函数不同于为正数。

正式：
n_2 = n_1 + n_0

负数：
n_-2 = n_-1 - n_0

为了使递归性正好相反，相同的代码将不起作用。编辑：维基百科提供了泛化：F_-n =（-1）^ n F_n所以只需计算F_n并修改符号与（-1）^ n

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);
}

解决方案

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

这篇关于递归斐波那契函数（带负数）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！