f(n)，理解方程

Question

我的任务是为以下公式编写MIPS指令代码：

f(n) = 3 f(n-1) + 2 f(n-2)  
f(0) = 1
f(1) = 1

我在理解这个公式的实际含义时遇到了问题。

据我所知，我们正在将一个int传递给这个双重递归程序。

因此，对于f(0)，方程为：

f(n)=3*1(n-1) + 2*(n-2)

如果为n=10，则等式为：

f(10)=3*1(10-1) + 2*(10-2)

我知道我根本没弄对，因为它不是递归的。如果你能对这个方程的实际含义有所了解，那就太好了。一旦我理解了这个等式，我就可以写MIPS代码了。

Answer 1

我认为这是一个差分方程。

您将获得两个起始值：

f(0) = 1
f(1) = 1
f(n) = 3*f(n-1) + 2*f(n-2)

所以现在你可以继续这样做：

f(2) = 3*f(1) + 2*f(0) = 3 + 2 = 5
f(3) = 3*f(2) + 2*f(1) = 15 + 2 = 17

因此，您的递归方法将如下所示(我将编写类似Java的表示法)：

public int f(n) {
    if (n == 0) {
        return 1;
    } else if (n == 1) {
        return 1; 
    } else { 
        return 3*f(n-1) + 2*f(n-2); // see? the recursion happens here.
    }
}

Answer 2

不，我认为你是对的，它是递归的。它似乎是Fibonacci Sequence的变体，这是一个经典的递归问题

请记住，递归算法有两个部分：

1. The base case
3. recursive call

基本情况指定您不能再递归的点。例如，如果您正在递归排序，则基本情况是长度为1的列表(因为单个项是普通排序的)。

因此(假设n不是负的)，你有两种基本情况:n=0和n= 1。如果你的函数收到一个等于0或1的n值，那么它再也没有意义递归了

考虑到这一点，您的代码应该如下所示：

function f(int n):
    #check for base case

    #if not the base case, perform recursion

让我们以斐波纳契数为例。

在斐波那契数列中，每个数都是它前面的两个数之和。因此，给定序列1, 2，下一个数字显然是1 + 2 = 3，后面的数字是2 + 3 = 5，3 + 5 = 8等等。一般而言，第n个斐波纳契数等于第(n -1)个斐波纳契数加上第(n -2)个斐波纳契数，或f(n) = f(n - 1) + f(n - 2)

但是这个序列从哪里开始呢？这就是最基本的情况。费波纳奇将他的序列定义为从1, 1开始。这意味着对于我们来说，f(0) = f(1) = 1。所以..。

function fibonacci(int n):
    if n == 0 or n == 1:
        #for any n less than 2
        return 1

    elif n >= 2:
        #for any n 2 or greater
        return fibonacci(n-1) + fibonacci(n-2)

    else:
        #this must n < 0
        #throw some error

请注意，Fibonacci与递归一起被教授的原因之一是因为它表明有时递归不是一个好主意。我不会在这里深入讨论它，但是对于大的n，这种递归方法是非常低效的，，。另一种选择是有两个全局变量，n1和n2，这样...

n1 = 1
n2 = 1

print n1
print n2

loop:
    n = n1 + n2
    n2 = n1
    n1 = n

    print n

将打印该序列。

Answer 3

您有两种基本情况：

f(0) =1

f(1) =1

其他任何东西都使用递归公式。例如，让我们计算f(4)。这不是基本情况之一，所以我们必须使用完整的方程。插入n=4后，我们会得到：

f(4) =3 f(4-1) +2 f(4-2) =3 f(3) +2 f(2)

嗯，还没做完呢。为了计算f(4)，我们需要知道f(3)和f(2)是什么。这两种情况都不是基本情况，所以我们必须进行一些递归计算。好吧..。

f(3) =3 f(3-1) +2 f(3-2) =3 f(2) +2 f(1)

f(2) =3 f(2-1) +2 f(2-2) =3 f(1) +2 f(0)

这就对了！我们已经到了谷底。f(2)是根据f(1)和f(0)定义的，我们知道这两个值是什么。我们得到了这些，所以我们不需要做更多的递归计算。

f(2) =3 f(1) +2 f(0) = 3×1 + 2×1 =5

现在我们知道f(2)是什么了，我们可以展开递归链并求解f(3)。

f(3) =3 f(2) +2 f(1) = 3×5 + 2×1 = 17

最后，我们再解开一次并求解f(4)。

f(4) =3 f(3) +2 f(2) = 3×17 + 2×5 = 61