递归学习

Recursive summary

<1>递归概念

函数调用自身，称为递归

<2>递归的条件

• 递归特性一：必须有一个明确的结束条件
• 递归特性二：每次递归都是为了让问题规模变小
• 递归特性三：递归层次过多会导致栈溢出

<3>使用递归求1+11+111+1111+11111的值

public class Recursive01 {
    public static void main(String[] args) {
        int i = functionB(4);
        System.out.println(i);
    }
    public static int functionA(int n){
        if (n==0){
            return 1;
        }
        else {
            return (int) (functionA(n-1)+Math.pow(10,n));
        }
    }
    public static int functionB(int n){
        if (n==0){
            return 1;
        }else {
            return functionB(n-1)+functionA(n);
        }
    }
}

<4>递归求n!

public class Recursive02 {
    public static void main(String[] args) {
        int i = funtionA(4);
        System.out.println(i);
    }
    public static int funtionA(int n){
        if (n==0){
            return 1;
        } else{
            return funtionA(n-1)*n;
        }
    }
}

<5>一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了n个村子后还剩两只鸭子，问他出发时共赶多少只鸭子？经过每个村子卖出多少只鸭子？

思考：

做法：

public class Recursive03 {
    public static int count(int n){//n表示第几个村子
        int sum=2;//鸭子总数剩两只
        if(n==4){
            return 2;//第n+1天没有交易之前还剩两只鸭子
        }
        else{

            sum=(count(n+1)+1)*2;//n+1天之前每天的交易前的鸭子总数为交易后所剩的数目加一乘以二

        }
        return sum;

    }

    public static void main(String []args){

        for (int i=1;i<4;i++){
            System.out.println("第"+i+"天的村子交易前有"+count(i)+"只鸭子,当天村子卖出"+(count(i)/2+1)+"只.");

        }
    }
}

运行结果：

我们来看一下执行步骤：