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

Question

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

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

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

Answer 1

传统的方法是使用Gessel检验。当且仅当5N ² + 4或5N ² \xe2\x80\x93 4是平方数时， N才是斐波那契数。这在这个SO问题和这个SO问题中进行了讨论。您还可以在此处找到示例，但此页面有 Python 代码（尽管很容易理解）。

\n\n

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

\n\n

这是一个基本的（而且丑陋的）示例：

\n\n

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

\n\n

使用它就像isFibonacci( the_number_you_want_to_test );

\n\n

请注意，斐波那契数可以及时计算，如本 SO 问题O(log n)中所述。

\n