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

Question

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

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

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

Answer 1

这对我来说有点笨拙，但你可以试试：

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 2

Determining whether a number is a Fibonacci number看起来是一样的，但在Java语言中，你可能会在那里得到你想要的东西。

Answer 3

斐波那契数具有数学性质。一个数是斐波那契数当且仅当(5*n^2 + 4)或(5*n^2 - 4)中的一个或两个是完美正方形(来源: Wiki)。

这种方法比递归函数调用方法简单得多。请查看此链接：

http://www.geeksforgeeks.org/check-number-fibonacci-number/

另一种方法：

static bool IsFib(long n)//n is the number to be checked
{
    double root5 = Math.Sqrt(5);
    double phi = (1 + root5) / 2;

    long idx    = (long)Math.Floor( Math.Log(n*root5) / Math.Log(phi) + 0.5 );
    long u = (long)Math.Floor( Math.Pow(phi, idx)/root5 + 0.5);

    return (u == n);
}

此代码适用于大型输入。这是由abelenky在stackoverflow上发布的类似问题。