如何递归检查一个数是否为斐波那契数？

Question

我需要编写一个程序，递归检查一个数是否是斐波那契数；重复完成同样的任务很容易；同样，递归地找到第n个斐波那契数也很容易，但我陷入了如何使用递归检查一个数是否是斐波那契数的困境。以下是查找第n个fib的代码。编号：

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

我不知道怎么做的是如何修改上面的代码来检查给定的数字是否是斐波那契？

Answer 1

确定一个数字是否是斐波那契数看起来是一样的，但在Java中，你可能会得到你想要的东西。

Answer 2

这让我觉得有点笨拙，但你可以试试：

bool isFib(int numToCheck int twoPrev = 0, int prev = 1) {
    if (numToCheck == twoPrev || numToCheck == prev)
        return true;

    int currentFibNumber = twoPrev + prev;
    if (currentFibNumber == numToCheck)
        return true;
    else if (currentFibNumber > numToCheck)
        return false;

    return isFib(numToCheck, prev, currentFibNumber);
}

这基本上是使用递归迭代斐波那契数，直到生成的数超过正在检查的值或找到匹配项。

正如其他人所指出的，有一些不需要递归的解决方案。

Answer 3

传统的方法是使用格塞尔测试。N是斐波那契数当且仅当5N^{24或5N2-4是平方数。这是在这个问题和这个问题中讨论的。您也可以在这里找到示例，但本页有Python代码（尽管很容易理解）。}

现在，如果你被要求专门使用递归。。。一种方法就是开始生成斐波那契数，直到生成的数大于或等于您要测试的数。如果存在匹配，则测试的数字属于斐波那契序列。如果没有匹配，并且生成的数字大于被测试的数字，则被测试的数字不是斐波那契数。

下面是一个基本的（丑陋的）例子：

bool isFibonacci( int testedNumber, int a = 1, int b = 1 )
{
    if( testedNumber == 0 || testedNumber == 1 )
        return true;//returning true for 0 and 1 right away.
    int nextFib = a + b;//getting the next number in the sequence
    if( nextFib > testedNumber )
        return false;//if we have passed the tested number, it's not in the sequence
    else if( nextFib == testedNumber )
        return true;//if we have a perfect match, the tested number is in the sequence
    else
        isFibonacci( testedNumber, b, nextFib );//otherwise, get the next fibonacci number and repeat.
}

使用它就像isFibonacci（the_number_you_want_to_test）；

请注意，斐波那契数可以在O（log n）时间内计算，例如在这个SO问题中所述。