c++ - 如何递归检查数字是否为斐波那契数？

Question

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

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

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

Answer 1

传统的方法是使用 Gessel 的测试。 N 是斐波那契数当且仅当 5N² + 4 或 5N² – 4 是一个平方数。这在 this SO question 中讨论和 this SO question .您还可以找到示例 here ，但是这个页面有 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) 时间内计算，如 this SO question 中的示例所述.