斐波那契数列 - 递归求和

Question

好吧,我最初编写了一个简单的代码,根据用户输入从系列中返回斐波纳契数.

n = 5将产生3 ..

static int fibonacci(int n) {
        if (n == 1)
            return 0;
        else if (n == 2)
            return 1;
        else
            return (fibonacci(n - 1) + fibonacci(n - 2));
    }

我正在考虑修改代码以返回系列的总和,而不是仅仅返回系列中的值,并且在尝试执行总和时我不小心将1添加到return语句中,令我惊讶的是,它正确地返回了总和.

对于n = 5,以下代码将返回7.

我不确定这是否是计算总和的正确方法......

如果我加1,我仍然无法弄清楚该系列的总和是如何工作的.有人可以解释一下吗？

static int fibonacci(int n) {
    if (n == 1)
        return 0;
    else if (n == 2)
        return 1;
    else
        return (fibonacci(n - 1) + fibonacci(n - 2)+(1));
}

编辑:

对于斐波那契系列.. 0,1,1,2,3,5,8,13,21,34,55,89,144 ....

我尝试了一些随机的n

N = 13

该函数返回376

0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 + 89 + 144 = 376

N = 10

该函数返回88

0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 = 88

Answer 1

您对fibonacci程序的修改确实可以计算总和.但是,使用递归的方式效率很低.处理此问题的一种方法是使用"动态编程"方法,其中计算值被缓存,以便第二次递归调用可以重用它们.但是,第n个斐波纳契数可以从基数计算出来.递归实现这将是:

public static int fib_r (int a, int b, int n) {
    if (n == 1) return a;
    if (n == 2) return b;
    return fib_r(b, a+b, n-1);
}

public static int fib (int n) {
    return fib_r(0, 1, (n > 0) ? n : 1);
}

总和的相应代码是:

public static int sumfib_r (int a, int b, int n) {
    if (n == 1) return a;
    if (n == 2) return b;
    return sumfib_r(b, a+b+1, n-1);
}

public static int sumfib (int n) {
    return sumfib_r(0, 1, (n > 0) ? n : 1);
}

尾部递归通常会被编译器/解释器更改为一个简单的循环,作为尾部调用删除的一部分.

您询问:

如果我加1,我仍然无法弄清楚该系列的总和是如何工作的.有人可以解释一下吗？

这个问题实际上是关于理解算法,我认为这是SO的主题.但是,需要数学来描述算法的工作原理.所以,这真的是一个数学问题.关于斐波那契数的总和有一个众所周知的定理.如果F[i]是第i个斐波那契数,并且S[n]是第一个n斐波那契数的总和,那么上面的定理指出:

    S[n] = F[n+2] - 1

所以,如果我们根据定义考虑S[n+2],

S[n+2] = S[n+1] + F[n+2]

然后,取代S[n] + 1了F[n+2]:

S[n+2] = S[n+1] + S[n] + 1

你应该认识到的是你的"添加1修改" fibonacci功能.

以下是通过归纳证明您的程序计算我在原始答案中提供的总和.让我们F代表你的fibonacci功能,并S代表你的"添加1修改" fibonacci功能.

F[1] = 0
F[2] = 1
F[i] = F[i-1] + F[i-2] for i > 1

S[1] = 0
S[2] = 1
S[i] = S[i-1] + S[i-2] + 1 for i > 1

然后,您需要一个证明k > 0:

         k
       .---  
S[k] =  >   F[i]
       `---
       i = 1

请注意,当且仅当以下情况时,上述总和为真:

S[1] = F[1]
S[k] = F[k] + S[k-1] for k > 1

证据非常简单.基本案例非常简单.

S[1] = F[1] = 0
S[2] = F[2] + F[1] = 1
S[3] = S[2] + S[1] + 1 = F[3] + F[2] + F[1] = 2

归纳步骤是:鉴于对某些人来说k > 2,S[j+1] = F[j+1] + S[j]为了0 < j < k+1证明等式是正确的,如果j = k+1,那就是:S[k+2] = F[k+2] + S[k+1].

    S[k+2] = S[k+1] + S[k] + 1
=>  S[k+2] = (F[k+1] + S[k]) + (F[k] + S[k-1]) + 1
=>  S[k+2] = (F[k+1] + F[k]) + (S[k] + S[k-1] + 1)
=>  S[k+2] = F[k+2] + S[k+1]

这样就完成了证明.