本文主要介绍递归的特性,结合栈和队列这两种数据结构来讲解其思想和简单用法。

1.1 栈和队列

概念定义

栈(stack)是限定仅在表尾进行插入和删除操作的线性表。

❐ 允许插入和删除数据的一端称为栈顶(top)。
❐ 不允许插入删除数据的一端称为栈底(bottom)。
❐ 不包含任何数据元素的栈称为空栈。
❐ 栈是一种后进先出(Last In First Out)的线性表,简称LIFO结构

队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。

❐ 允许插入数据的一端被称为队尾。
❐ 允许删除数据的一端被称为队头。
❐ 队列是一种先进先出(First In First Out)的线性表,简称FIFO结构

栈的特性及常见操作

栈的操作主要有两种,插入数据我们一般称为压栈或者入栈,删除数据我们一般称为弹栈或者出栈

栈这种数据结构本身是基于线性表(链表)来实现的,所以可以有顺序存储方式(顺序栈)和链式存储方式(链式栈)。如果采用顺序存储方式,可能还会见到两个栈共享空间的情况。


栈这种数据结构的特点是先进去的后出来,那么是否最先存储的元素一定最后出来?需要注意的是,栈对数据的插入和删除位置进行了限制,但是并没有对元素进出的顺序进行限制。

给定a、b、c这三个数字,它们依次进栈,其出栈顺序可能如下:

① a、b、c进,c、b、a出栈。 [c-b-a]
② a进,a出;b进,b出;c进,c出。[a-b-c]
③ a进,b进,b出,a出,c进,c出。[b-a-c]
④ a进,a出;b进,c进,c出,b出。[a-c-b]
⑤ a进,b进,b出,c进,c出,a出。[b-c-a]

注意:不可能出现c-a-b这样的出栈次序。

其实生活中很多地方都用到了栈这样的数据结构,比如手枪的弹夹,比如浏览器页面的前进和回退按钮(压栈和弹栈),撤销操作等等,我们在开发中常常写的函数调用其实也是这种情况。

1.2 栈和递归

栈有一个很重要的应用:就是在程序设计语言中实现了递归。
递归的特征 递归的本质特征是函数自己调用自己,为了不陷入死循环往往递归还需要一个出口。

递归函数的结构

递归条件(recursive case) 函数自己调用自己。
基线条件(base case) 函数不再调用自己的出口条件,避免陷入到死循环中。

递归和循环 如果使用循环,程序的性能可能更好,如果使用递归,程序可能更容易理解,递归并没有性能上的优势。

函数调用栈

计算机在内部会使用一个叫做调用栈的栈,我们可以通过下面贴出的一小段代码来分析其结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function a(arg) {
console.log("当前执行的函数为:a" + "参数为:" + arg);
}
function b() {
console.log("我是函数b的函数体");
}

function fn(name) {
console.log("fn函数体开始" + name);
a("参数T");
console.log("a函数调用完毕");
b();
}

fn("文顶顶");

上述代码的执行结果

分析上面这段代码并试着贴出函数调用栈的示意图

① 当我们执行 fn("文顶顶")这行代码的时候,计算机首先会为该函数的调用分配一块内存。
② 调用函数并分配内存后,函数中的变量name的值被设置为文顶顶,这些变量需要存储到内存中。
③ 打印字符串。

④ 执行代码a("参数T") 此处调用了a函数,计算机同样需要为高函数分配一块内存空间。
⑤ 执行函数a的函数体,变量arg的值被设置为参数T。
⑥ a函数中的打印任务执行完毕,从函数调用返回。

⑦ 打印字符串。
⑧ 执行代码b() ,调用b函数,会在当前函数调用栈的栈顶添加函数b的内存块。
⑨ 函数b执行完毕,从函数调用返回。
⑩ 函数fn执行完毕,返回。

当函数在函数体中调用另外一个函数时,当前函数将暂停并处于未完成状态。

1.3 递归函数演示

示例代码001–斐波那契数列的递归函数

斐波那契数列对应的值:1,1,2,3,5,8,13...

数学表达式

实现代码

1
2
3
4
5
6
7
8
9
function Fibonacci(n) {
/*基线条件*/
if (n < 2) return n === 0 ? 0 : 1;
/*递归条件*/
return Fibonacci( n - 1 ) + Fibonacci( n - 2)
}

//斐波那契数列对应的值:1,1,2,3,5,8,13···
console.log(Fibonacci(7)); //13

示例代码002–计算5!(阶乘)的递归函数

阶乘的计算推演

1
2
3
4
5
6
7
1! = 1                  ==>1
2! = 2 * 1 ==>2 * 1!
3! = 3 * 2 * 1 ==>3 * 2!
4! = 4 * 3 * 2 * 1 ==>4 * 3!
5! = 5 * 4 * 3 * 2 *1 ==>5 * 4!
...
容易得出:n!= n * (n-1)!

代码示例

1
2
3
4
5
6
7
8
9
10
function factorial(n) {
if (n === 1) return 1; //基准条件
return n * factorial(n-1); //递归条件
}

console.log(factorial(5)); //120
console.log(factorial(4)); //24
console.log(factorial(3)); //6
console.log(factorial(2)); //2
console.log(factorial(1)); //1

1.4 RPN表示法

逆波兰(Reverse Polish Notation,RPN)表示法是种不需要括号的后缀表达法,用于数学表达式的求值。

逆波兰后缀表示法非常巧妙的解决了程序实现四则运算的难题,下面给出示例并简单介绍。
后缀表示法的意思是:所有的符号都要在运算数字的后面出现,并且没有了括号。

后缀表示法:542-6*+42/+
中缀表示法:5 + (4-2)x 6 + 4 ÷ 2 [标准四则运算表达式]

后缀表示法运算规则

❐ 从左向右遍历后缀表达式中的每个数字和符号;
❐ 遇见数字就压栈
❐ 遇见符号就将处于栈顶的两个数字弹栈,进行运算;
❐ 运算结果压栈
❐ 重复上面的过程,直到最终获得结果

现在我们已经知道了后缀表达式利用压栈和弹栈操作实现的计算过程,接下来研究下标准的四则运算表达式如何转换为后缀表示法

中缀表达式转换为后缀表达式规则

❐ 从左向右遍历后缀表达式中的每个数字和符号;
❐ 遇见数字就输出;
❐ 遇见符号就判断与当前栈顶符号的优先级,如果是右括号或者优先级不高于栈顶符号,则栈顶元素依次出栈并输出;
❐ 将当前符号压栈;
❐ 重复上面的过程,直到最终输出后缀表达式为止。