斐波那契函数问题

Fibonacci(4)
= Fibonacci(3) + Fibonacci(2)
= (Fibonacci(2) + Fibonacci(1)) + (Fibonacci(1) + Fibonacci(0))
= ((Fibonacci(1) + Fibonacci(0)) + 1) + (1 + 1)
= ((1 + 1) + 1) + 2
= (2 + 1) + 2
= 3 + 2
= 5

注意Fibonacci函数在这里被调用了9次。一般来说,nave递归fibonacci函数 exponential running time ,这通常是件坏事。

这是一个典型的例子 recursive function

如果你仔细阅读,你会发现它会自称, 递归 基本情况 x <= 1 在这一点上,它将开始“回溯”,并总结计算值。

public class Test {

    static String indent = "";

    public static int fibonacci(int x) {

        indent += "    ";
        System.out.println(indent + "invoked with " + x);

        if (x <= 1) {

            System.out.println(indent + "x = " + x + ", base case reached.");
            indent = indent.substring(4);

            return 1;
        }

        System.out.println(indent + "Recursing on " + (x-1) + " and " + (x-2));
        int retVal = fibonacci(x-1) + fibonacci(x-2);
        System.out.println(indent + "returning " + retVal);
        indent = indent.substring(4);
        return retVal; 

    }


    public static void main(String... args) {
        System.out.println("Fibonacci of 3: " + fibonacci(3));
    }
}

输出如下:

invoked with 3
Recursing on 2 and 1
    invoked with 2
    Recursing on 1 and 0
        invoked with 1
        x = 1, base case reached.
        invoked with 0
        x = 0, base case reached.
    returning 2
    invoked with 1
    x = 1, base case reached.
returning 3

Fibonacci of 3: 3

                               fib 4
               fib 3             +           fib 2
    fib 2        +    fib 1              fib 1 + fib 0
fib 1 + fib 0           1                  1       1
  1       1

编写递归函数时需要考虑的重要部分是:

如果我们忘记了会发生什么 if (x<=1) return 1; 在上面的例子中?

2.确保递归调用以某种方式减少到基本情况

fibonacci(x)+fibonacci(x-1);

返回Fibonacci(x-1)+Fibonacci(x-2);

unsigned fibonacci(unsigned n, unsigned a, unsigned b, unsigned c)
{
    return (n == 2) ? c : fibonacci(n - 1, b, c, b + c);
}

unsigned fibonacci(unsigned n)
{
    return (n < 2) ? n : fibonacci(n, 0, 1, 1);
}

fibonacci序列可以用函数语言更简洁地表达。

fibonacci = 0 : 1 : zipWith (+) fibonacci (tail fibonacci)

> take 12 fibonacci
[0,1,1,2,3,5,8,13,21,34,55,89]

这是经典的函数递归。 http://en.wikipedia.org/wiki/Recursive_function 你该开始了。基本上,如果x小于或等于1,它返回1。否则,它在每一步都减少x。

当你的问题被标记为C++时,我不得不指出,这个函数也可以在编译时作为模板来实现,如果你有一个编译时变量来使用它。

template<int N> struct Fibonacci {
    const static int value = Fibonacci<N - 1>::value + Fibonacci<N - 2>::value;
};
template<> struct Fibonacci<1> {
    const static int value = 1;
}
template<> struct Fibonacci<0> {
    const static int value = 1;
}

我已经有一段时间没写了,所以可能有点不对劲,但应该是这样。

是的,斐波那契函数被再次调用,这叫做递归。

就像你可以调用另一个函数一样,你也可以再次调用同一个函数。由于函数上下文是堆叠的,因此可以调用相同的函数,而不会干扰当前执行的函数。

在C和大多数其他语言中,函数可以像其他函数一样调用自己。这叫做递归。

如果它看起来很奇怪,因为它与您将要编写的循环不同,那么您是对的。这不是一个很好的递归应用程序,因为查找 n 斐波那契数需要两倍于求 n -1th,导致运行时间呈指数增长 .

迭代Fibonacci序列,在继续下一个Fibonacci数之前记住上一个Fibonacci数,可以提高运行时的线性度 ,应该是这样的。

递归本身并不可怕。实际上,我刚才描述的循环(以及任何循环)都可以实现为递归函数:

int Fibonacci (int x, int a = 1, int p = 0) {
    if ( x == 0 ) return a;
    return Fibonacci( x-1, a+p, a );
} // recursive, but with ideal computational properties

int *fib,n;
void fibonaci(int n) //find firs n number fibonaci
{
 fib= new int[n+1];
 fib[1] = fib[2] = 1;
 for(int i = 3;i<=n-2;i++)
     fib[i] = fib[i-1] + fib[i-2];
}

对于n=10,例如: fib[1]fib[2]fib[3]fib[4]fib[5]fib[6]fib[7]fib[8]fib[9]fib[10]