猴子吃桃（递归）

递归案例实践分析 猴子偷桃 题目描述：

猴子第一天摘下若干桃子，当即吃了一半，觉得好吃不过瘾，于是又多吃了一个，，第二天又吃了前天剩余桃子数量的一半，觉得好不过瘾，于是又多吃了一个，以后每天都是吃前天剩余桃子数量的一半，觉得不过瘾，又多吃一个，等到第十天的时候，发现桃子只有一个。
需求：请问猴子第一天摘了多少个桃子？

分析：

设x为第x天，已知猴子第10天剩下一个桃子，那么可知第9天剩的桃子是第10天剩下数量+1，再总体×2，设第9天为x，那么第10天剩的桃子数为：f（x+1）有上述可推出 公式为：f(x) = (f(x + 1) + 1) * 2。
下面通过递归算法写出代码：
（代码main方法输出做了扩展，将10天到1天所有结果遍历输出）

代码： 递归方法：

public static int f(int n){
        if (n == 10) {
            return 1;
        } else {
            return (f(n + 1) + 1) * 2;
        }
    }

main方法

public static void main(String[] args) {
        for (int i = 10; i > 0; i--) {
            System.out.println("第"+i+"天剩："+f(i)+"个果子。");
        }
    }

运行结果：

第10天剩：1个果子。
第9天剩：4个果子。
第8天剩：10个果子。
第7天剩：22个果子。
第6天剩：46个果子。
第5天剩：94个果子。
第4天剩：190个果子。
第3天剩：382个果子。
第2天剩：766个果子。
第1天剩：1534个果子。