算法图解第三章笔记：递归(java版)

3.1 递归

案例：寻找祖母的钥匙。

钥匙在祖母的盒子里，一个大盒子中有很多小盒子，小盒子中也可能还有盒子。钥匙就在某个盒子中。如何找到钥匙？

方法一：

1. 创建一个要查找的盒子堆
2. 从盒子中取出一个盒子，在里面找
3. 如果找到的是盒子，就将其加入到盒子堆中，以便以后再查找。
4. 如果找到钥匙，则大功告成
5. 回到第二步

方法二

1. 检查盒子中的每样东西
2. 如果是盒子，就回到第一步
3. 如果是钥匙，则大功告成

第一种方法使用while循环：只要盒子堆不空，就从中取一个盒子，并在其中仔细查找。

第二种方法使用递归—函数调用自己。

两种方法作用相同。递归只是让解决方案更加清晰，并没有性能上的优势。有一句是这样说的：“如果使用循环，程序的性能可能更高；如果使用递归。程序可能更容易理解。如何选择要看什么对你来说更重要”。

3.2 基线条件和递归条件

由于递归函数自己调用自己，因此编写这样的函数时很容易出错，进而导致无限循环。

例如：假设你要编写一个像下面这样的倒计时函数：

>3…..2…..1

可以编写的递归函数如下：

public class Code_02_BaseCase {
	public static void main(String[] args) {
		countDown(3);
	}
	/*
	 * 未添加基线条件，所以程序会一直运行下去
	 */
	public static void coutDown(int i){
		System.out.println(i);
		coutDown(i-1);
	}
 }

当你运行时，这个函数会一直运行下去。。。。

所以编写递归函数时，必须告诉它何时停止递归。正因为如此，每个递归函数都有两部分：基线条件（base case）和递归条件（recursive case）

给函数countDown添加基线条件：

/*
 * 	设计一个倒计时3、2、1的计时器
 * 
 * 	基线条件：
 * 
 */
public class Code_02_BaselineCondition {
	public static void main(String[] args) {
		countDown(3);
	}
	
	/*
	 * 添加基线条件
	 */
	public static void countDown(int i){
		System.out.println(i);
            //基线条件  
		if(i <= 1 ){
			return;
		}else{
              //递归条件
              countDown_1(i-1);
		}
	}	
	
}

打印输出为：

3.3 栈

​ 调用栈 call stack

​ 有两种操作：压入（插入）和 弹出（删除并读取）

1.调用栈：

​ 一个简单的函数，来看看计算机是如何调用栈的。

/*
 * 	演示计算机是如何调用栈的
 * 
 */
public class Code_03_CallStack {
	public static void main(String[] args) {
		greet("John");
	}
	
	public static void greet(String name){
		System.out.println("hello,"+ name + "!");
		greet2(name);
		System.out.println("getting ready to say bye....");
		bye();
	}
	
	public static void greet2(String name){
		System.out.println("how are you, "+ name + "?");
	}
	
	public static void bye(){
		System.out.println("ok bye");
	}
}

打印输出为：

一个重要的概念：调用另一个函数时，当前函数暂停并处于未完成的状态。

2.递归调用栈：

递归函数也使用调用栈。下面是一个例子：

factorial(5)写作5！其定义如下：5！= 5 * 4 * 3 * 2 * 1

/*
 * 	递归调用栈：
 * 		递归函数求解
 * 			5！= 5*4*3*2*1
 * 
 */
public class Code_04_RecursionCallStack {
	
	public static void main(String[] args) {
		System.out.println(factorical(5));
	}
	/*
	 * 递归函数
	 */
	public static int factorical(int x){
		//基线条件
		if(x == 1){
			return 1;
		}else{
			//递归条件
			return x*factorical(x - 1);
		}
	} 
}

打印输出为：