← 返回学习路线

SYSTEM

递归

Java基础递归system
src/content/notes/system/递归.md

递归

概述

算法:解题方案的准确而完整的描述,是一系列解决问题的清晰指令,代表着用系统的方法解决问题的策略机制

递归:程序调用自身的编程技巧

递归:

  • 直接递归:自己的方法调用自己
  • 间接递归:自己的方法调用别的方法,别的方法又调用自己

递归如果控制的不恰当,会形成递归的死循环,从而导致栈内存溢出错误

参考书籍:https://book.douban.com/subject/35263893/


算法

核心思想

递归的三要素(理论):

  1. 递归的终结点
  2. 递归的公式
  3. 递归的方向:必须走向终结点
// f(x)=f(x-1)+1;   f(1)=1;    f(10)=?
// 1.递归的终结点: f(1)  = 1
// 2.递归的公式:f(x) = f(x - 1) + 1
// 3.递归的方向:必须走向终结点
public static int f(int x){
    if(x == 1){
        return 1;
    }else{
        return f(x-1) + 1;
    }
}

公式转换

// 已知: f(x) = f(x + 1) + 2,  f(1) = 1。求:f(10) = ?
// 公式转换
// f(x-1)=f(x-1+1)+2 => f(x)=f(x-1)+2
//(1)递归的公式:   f(n) = f(n-1)- 2 ;
//(2)递归的终结点:  f(1) = 1
//(3)递归的方向:必须走向终结点。
public static int f(int n){
    if(n == 1){
        return 1;
    }else{
        return f(n-1) - 2;
    }
}

注意事项

以上理论只能针对于规律化递归,如果是非规律化是不能套用以上公式的! 非规律化递归的问题:文件搜索,啤酒问题。


应用

猴子吃桃

猴子第一天摘了若干个桃子,当即吃了一半,觉得好不过瘾,然后又多吃了一个。第二天又吃了前一天剩下的一半,觉得好不过瘾,然后又多吃了一个。以后每天都是如此。等到第十天再吃的时候发现只有1个桃子,问猴子第一天总共摘了多少个桃子?

/*
(1)公式: f(x+1)=f(x)-f(x)/2-1; ==> 2f(x+1) = f(x) - 2 ==> f(x)=2f(x+1)+2
(2)终结点:f(10) = 1
(3)递归的方向:走向了终结点
*/

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

递归求和

//(1)递归的终点接:f(1) = 1
//(2)递归的公式: f(n) = f(n-1) + n
//(3)递归的方向必须走向终结点:
public static int f(int n){
        if(n == 1 ) return 1;
        return f(n-1) + n;
}

汉诺塔

public class Hanoi {
    public static void main(String[] args) {
        hanoi('X', 'Y', 'Z', 3);
    }

    // 将n个块分治的从x移动到z,y为辅助柱
    private static void hanoi(char x, char y, char z, int n) {
        if (n == 1) {
            System.out.println(x + "→" + z);    // 直接将x的块移动到z
        } else {
            hanoi(x, z, y, n - 1);           	// 分治处理n-1个块,先将n-1个块借助z移到y
            System.out.println(x + "→" + z);    // 然后将x最下面的块(最大的)移动到z
            hanoi(y, x, z, n - 1);           	// 最后将n-1个块从y移动到z,x为辅助柱
        }
    }
}

时间复杂度 O(2^n)


啤酒问题

非规律化递归问题,啤酒 2 元 1 瓶,4 个盖子可以换 1 瓶,2 个空瓶可以换 1 瓶

public class BeerDemo{
    // 定义一个静态变量存储可以喝酒的总数
    public static int totalNum;
    public static int lastBottleNum;
    public static int lastCoverNum;
    public static void main(String[] args) {
        buyBeer(10);
        System.out.println("总数:"+totalNum);
        System.out.println("剩余盖子:"+ lastCoverNum);
        System.out.println("剩余瓶子:"+ lastBottleNum);
    }
    public static void buyBeer(int money){
        int number = money / 2;
        totalNum += number;
        // 算出当前剩余的全部盖子和瓶子数,换算成金额继续购买。
        int currentBottleNum = lastBottleNum + number ;
        int currentCoverNum = lastCoverNum + number ;
        // 把他们换算成金额
        int totalMoney = 0 ;
        totalMoney += (currentBottleNum/2)*2; // 除2代表可以换几个瓶子,乘2代表换算成钱,秒!
        lastBottleNum = currentBottleNum % 2 ;// 取余//算出剩余的瓶子
     
        totalMoney += (currentCoverNum / 4) * 2;
        lastCoverNum = currentCoverNum % 4 ;

        // 继续拿钱买酒
        if(totalMoney >= 2){
            buyBeer(totalMoney);
        }
    }
}