前言

现在写这篇文章主要记录自己使用递归的经过

说到递归,不得不说起自己大一刚刚开学接触c语言,第1个问题便是一个求阶乘的题目,最终采用了递归策略,记得自己当时测试的时候,足足用了1分钟,最后才发现是一个死循环,从那时开始便开始躲避递归,就怕来个死循环~唧唧!

说实话,在我今天写这个技术博客记录自己递归的使用历程的时候,不得不说自己 真的是 从 厌恶递归 –> 接受递归 –> 欣赏递归


递归的使用

说到递归的使用,二话不说先来一个例子,自己之前看到一本书上,例子如下

当我们打开祖母留给我们的箱子的时候,发现里面依然有一个箱子,然而我们要找的仅仅是一把钥匙,所以每次都会打开一个箱子,直到打开箱子发现钥匙为止!(流程描述如下)

>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class FindKey {

public static final int BOX_KEY = 1;
/**
*
* @param box 一个宝箱
*/
public static void find(Box box) {
for (int i = 0; i < box.listBoxes; i++) {
if(box[i] == BOX_KEY) {
System.out.println("The key is found");
return;
}else {
find(box[i]); /* 递归 */
}
}
}
}

记得之前看过Stack Overflow上的一句话:使用循环 程序性能可能更高,使用递归,程序可能更容易理解


递归中的条件

正如大家都知道,递归都是自己调用自己,如果我们在编写程序的时候,没有进行判断,程序将会出现死循环,这个错误对我们来说是非常严重的,因此我们对递归是否继续进行判断。

递归条件

使得递归程序继续运行的条件

基线条件

使得递归函数不再继续的条件,也就是不满足递归的条件,从而避免死循环


递归中的数据结构

很多题目中都会问到 递归算法执行的过程中,计算机系统一定用到的数据结构是什么?

答案顾名思义肯定是栈,这里我们一般将其称为 调用栈的栈(计算机内部使用)

调用栈的栈

这里举个例子,比如求 3的阶乘

第一步:计算结果为 3 * fact(2),开始调用fact(2)

第二步:计算结果为 2 * fact(1); 当我们调用fact(2)的时候,fact(3)暂停,处于未完成状态

第三步:计算结果为 1; 并返回1 当我们调用fact(1)的时候,fact(2)暂停,处于未完成状态

>

注意事项

  1. 栈虽然很方便,但是当我们存储大量信息的时候会占用大量的内存,每个函数调用都会占用一定内存,就意味着计算机存储了大量函数调用的过程信息。
  2. 遇到上述情况的时候,我们可以尝试使用循环,或者尾递归!
  3. 所有函数调用都会进入调用栈
  4. 调用栈很长的时候,将会占用大量的内存

总结:虽然递归可以极大程度的简化代码,但是我们使用的时候还是需要注意,递归中的函数调用会占用很大的内存,当我们递归次数多的时候可以考虑使用循环或者尾递归