Object-c处理简单数列求值问题

已知f(0) = 1，f(1) = 4，f(n+2) = 2*f(n+1) + f(n)，求f(10)的值。

---

看到这样的递推公式就可以考虑使用递归来实现数列的求值问题。当然通过递推公式我们比较容易得到:

• f(n) = 2*f(n-1) + f(n-2);

于是使用递归进行求值：

int f(int n){
    if (n == 0) {
        return 1;
    }else if(n == 1){
        return 4;
    }else{
        return 2*f(n-1) + f(n-2);
    }
}

---

当然，并不是所有人通过递推公式都能得到与上面同样的公式，也许他们得到了下面的公式：

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

当然他们得到的公式并没有错，只不过是从另一个角度进行的推导，但是通过这个公式是无法使用递归得到f(10)的值的。也许有这么一道题：

已知f(20) = 1，f(21) = 4，f(n+2) = 2*f(n+1) + f(n)，求f(10)的值。

这样一来就可以使用这个递推公式通过递归的方法得到f(10)的结果了，可以参考一下程序：

int f(int n){
    if (n == 20) {
        return 1;
    }else if(n == 21){
        return 4;
    }else{
        return f(n+2) - 2*f(n+1);
    }
}