004—JAVA递归知识精华总结

• 递归：指在当前方法内调用自己的这种现象。

• 递归的分类:递归分为两种，直接递归和间接递归。

  • 直接递归称为方法自身调用自己。

  • 间接递归可以A方法调用B方法，B方法调用C方法，C方法调用A方法。

• 注意事项：

  • 递归一定要有条件限定，保证递归能够停止下来，否则会发生栈内存溢出。(无穷递归，类似死循环)

  • 在递归中虽然有限定条件，但是递归次数不能太多。否则也会发生栈内存

代码写法规律总结

if (填写终止递归的值即哪个值为出口){
    return 1;
}

return  规律；

示例一：计算1-100之间所有自然数的和
分析  求1-100的和   即100 + sum(99) + sum(98)
                   即num + sum(num--);
                     
规律假设该方法就是digui(n) 如果n=5  则digui(5) = 5(对应于n) + digui(4)(5对应于n-1) 
digui(4) = 3 + digui(3)


public static int sum(int num){
        if (num == 1){
            return 1;
        }
        return num + sum(num - 1);
    }

写一个方法用递归求阶乘
public class RecurtionMutiple {
    public static void main(String[] args) {
        int multiple = multiple(5);
        System.out.println("multiple = " + multiple);
    }
    public static int multiple(int n){
        if (n == 1){
            return 1;
        }
        return n * multiple(n - 1);

    }
}

示例三：计算斐波那契数列（Fibonacci）的第n个值

 public static void main(String[] args) {
        int i = feiBo(8);
        System.out.println("i = " + i);
    }


    public static int feiBo(int num){
        if (num == 1){
            return 1;
        }
        if (num == 2){
            return 1;

        }

        return feiBo(num - 1) + feiBo(num - 2);
    }

 描述：猴子吃桃子问题，猴子第一天摘下若干个桃子，当即吃了所有桃子的一半，还不过瘾，又多吃了一个。第二天又将仅剩下的桃子吃掉了一半，又多吃了一个。以后每天都吃了前一天剩下的一半多一个。到第十天，只剩下一个桃子。试求第一天共摘了多少桃子？

public class EatPeach {
    public static void main(String[] args) {
        int i = eatPeach(1);
        System.out.println("i = " + i);
    }

    public static int eatPeach(int day){
        if (day == 10){
            return  1;
        }
        return (eatPeach(day + 1) + 1)*2;
    }
}

 有n级台阶，一次只能上1步或2步，共有多少种走法？

求n级台阶，digui(n) 则之需求digui(4) + digui(3)

digui(1) = 1

digui(2) = 2

public class Step {
    public static void main(String[] args) {
        int digui = digui(4);
        System.out.println("digui = " + digui);

    }
    public static int digui(int n){
        if (n == 1){
            return 1;
        }
        if (n == 2){
            return 2;
        }
        return digui(n - 1) + digui(n - 2);
    }
}

求1+2！+3！+4！+...+20！的和

public class JieCheng {
    public static void main(String[] args) {
        int jiecheng = jiechengSum(4);
        System.out.println("jiecheng = " + jiecheng);
    }

    public static int jiecheng(int n){
            if (n == 1){
                return 1 ;
            }
            return   n * jiecheng(n - 1);
    }
    public static int jiechengSum(int n){
        if (n == 1){
            return 1;
        }
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += jiecheng(i);
        }
          return sum;
    }
}