我需要编写一个程序来递归检查一个数字是否是斐波那契数;迭代地完成同样的任务很容易;也很容易递归地找到第n个斐波纳契数,但我仍然坚持如何使用递归检查数字是否为斐波那契数.
这是找到第n个fib的代码.数：

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

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

解决方法:

传统的方法是使用Gessel的测试.当且仅当5N2 4或5N2 – 4是平方数时,N是斐波那契数.这在this SO question和this SO question中讨论.您也可以找到示例here,但此页面上有Python代码(尽管它很容易理解).

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

这是一个基本(和丑陋)的例子：

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中所描述的.