J027_递归算法

一、求n的阶乘

n的阶乘：1*2*3*4*...*n

package com.itheima.d01_file;

public class DiguiTest1 {
    public static void main(String[] args) {
        //求n的阶乘
        System.out.println(f(3));
        System.out.println(f(4));
        System.out.println(f(5));
    }

    private static int f(int n) {
        if (n == 1) {
            return 1;
        } else {
            return f(n - 1) * n;
        }
    }
}

二、求1+2+...+n的和

package com.itheima.d01_file;

public class DiguiTest2 {
    public static void main(String[] args) {
        //求1+2+...+n的和
        System.out.println(f(3));
        System.out.println(f(4));
        System.out.println(f(5));
    }

    private static int f(int n) {
        if (n == 1) {
            return 1;
        } else {
            return f(n - 1) + n;
        }
    }
}

三、猴子吃桃

3.1 题目描述

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

请问桃子第一天摘了多少桃子？

3.2 分析

假设第一天摘的桃子数为f(x)，第二天的桃子数为f(x+1)，则有f(x) - f(x)/2 -1 = f(x+1)

变换格式后：f(x) = 2 * f(x+1) + 2

3.3 代码实现

package com.itheima.d01_file;

public class DiguiTest3 {
    public static void main(String[] args) {
        System.out.println(f(1));
        System.out.println(f(2));
        System.out.println(f(3));
    }

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

3.4 运行结果