说起递归,我们很容易就想到了斐波那契数列,这是一道常见的笔试题。可是,为什么面试官都喜欢考察递归的掌握程度呢?这节我们来解开递归的神秘面纱。

一、理解递归

我们先来举个小例子:有一把钥匙在一个盒子里,这个盒子里还有盒子,而盒子里的盒子又有盒子,钥匙就在某个盒子里。那么我们如何找到钥匙呢?

思路很简单,一直开盒子,如果开到盒子继续再打开盒子,直到开出钥匙。

伪代码实现可能如下:

1
2
3
4
5
6
7
8
9
const look_for_key = (box) => {
for (let item in box) {
if (item.is_a_box()) {
look_for_key(item);
} else if (item.is_a_key()) {
console.log('Jartto: you found the key!');
}
}
}

如果使用循环,程序的性能可能更高;如果使用递归,程序可能更容易理解。如何选择要看什么对你来说更重要。

二、基线条件和递归条件

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

编写递归函数时,必须告诉它何时停止递归。正因为如此,每个递归函数都有两部分:

  • 基线条件 (base case)
  • 递归条件 (recursive case)

递归条件指的是函数调用自己,而基线条件则指的是函数不再调用自己,从而避免形成无限循环。
回到我们文章开头说的那个斐波那契函数:1,1,2,3,5,8...

1
2
3
4
5
function fabnc(n){
if(n === 1 || n === 2) return 1;
return fabnc(n-1) + fabnc(n-2);
}
fabnc(5);

像上面这样,if 条件就是基线条件,调用 fabnc(n-1) + fabnc(n-2) 就是递归条件。

三、栈和队列

为了更好的理解递归,我们需要先引入栈(stack)的概念。最早是在数据结构的线性表中接触到队列(Queue)与栈(Stack),我们先来回顾一下:

1.栈的插入和删除操作只允许在表的尾端进行(在栈中成为“栈顶”),满足 FIFO:First In Last Out
2.队列只允许在表尾插入数据元素,在表头删除数据元素,满足 First In First Out

更多细节,可以看之前这篇文章:掌握 JS Stack Trace

我们举个简单的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
function c() {
console.log('c');
console.trace();
}
function b() {
console.log('b');
c();
}
function a() {
console.log('a');
b();
}
a();

对上面的代码做一下简短的分析:
1.当调用 a 的时候,它会被压到栈顶;
2.然后,当 ba 中被调用的时候,它会被继续压入栈顶,当 cb 中被调用的时候,也一样;
3.在运行 c 的时候,栈中包含了 abc,并且其顺序也是 abc
4.当 c 调用完毕时,它会被从栈顶移出,随后控制流回到 b。当 b 执行完毕后也会从栈顶移出,控制流交还到 a。最后,当 a 执行完毕后也会从栈中移出。
5.每当有一个函数调用,就会将其压入栈顶。在调用结束的时候再将其从栈顶移出。

四、递归调用栈

存储详尽的信息可能占用大量的内存。

每个函数调用都要占用一定的内存,如果栈很高,就意味着计算机存储了大量函数调用的信息。在这种情况下,我们有两种选择。
1.重新编写代码,转而使用循环;
2.使用尾递归 。需要注意的是,并非所有的语言都支持尾递归。

编写涉及数组的递归函数时,基线条件通常是数组为空或只包含一个元素。陷入困境时,请检查基线条件是不是这样的。

五、小练习

1.利用递归求和:

1
2
3
4
5
6
7
8
function sum(n) {
if(n===0 || n===1) return n;
return sum(n-1) + n;
}
sum(0) //0
sum(3) //6
sum(100) //5050

2.递归实现数组求和:

1
2
3
4
5
function sum2(arr, n) {
if(n <= 0) return 0;
return sum2(arr, n-1) + arr[n-1];
}
sum2([1,2,3], 3); // 6

3.编写一个递归函数来计算列表包含的元素数:

1
2
3
4
5
6
function arrLength(arr) {
if(JSON.stringify(arr) === '[]') return 0;
arr.splice(0,1);
return 1 + arrLength(arr);
}
arrLength([1,2,3]) // 3

4.找出列表中最大的数字:

1
2
3
4
5
6
function max(arr, n) {
if(n <= 0) return 0;
return arr[n-1] > max(arr, n-1) ? arr[n-1] : max(arr, n-1);
}
max([1,2,3], 3); // 3
max([-4,7,9,11], 4); // 11

5.递归求字符串长度

1
2
3
4
5
function strLength(str) {
if(str.length === 0) return 0;
return 1 + strLength(str.substring(0, str.length - 1));
}
strLength('jartto'); // 6

6.快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function quicksort(arr)
{
if (arr.length == 0) return [];
let left = [];
let right = [];
let pivot = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quicksort(left).concat(pivot, quicksort(right));
}
console.log(quicksort([2,4,5,49,63,4,5,55,2,4,43])); // [2, 2, 4, 4, 4, 5, 5, 43, 49, 55, 63]

六、总结

1.递归指的是调用自己的函数。
2.每个递归函数都有两个条件:基线条件和递归条件。
3.栈有两种操作:压入和弹出。
4.所有函数调用都进入调用栈。
5.调用栈可能很长,这将占用大量的内存。

七、学习目录