猴子吃桃--递推与递归

题目：猴子第一天摘了若干个桃子，当即吃了一半，还不解馋，又多吃了一个；第二天，吃剩下的桃子的一半，还不过瘾，又多吃了一个；以后每天都吃前一天剩下的一半多一个，到第10天想再吃时，只剩下一个桃子了。问第一天共摘了多少个桃子？

递推实现:
递推关系为
f(t)=f(t-1)/2-1
f(t-1)=2f(t)+2
f(10)=1

public class Monkey {
    public static void main(String[] args) {
        int[] f=new int[11];
        f[10]=1;
        for (int i=10;i>=2;i--){
            f[i-1]=2*f[i]+2;
        }
        System.out.println(f[1]);
    }
}

递归实现

public class Monkey2 {
    public static void main(String[] args) {
        System.out.println(f(1));
    }
    static int f(int t){
        if (t==10){
            return 1;
        }else {
            return  2*f(t+1)+2;
        }
    }
}

递归过程

递归.png

运行结果为:
1534