递归专题

递归的表象：自己调用自己

递归的思想内核：自欺欺人，假装自己已经完成了这道题，反复调用结论。

难点：如何寻找/构造递归函数。

重点推荐看：第 24 题，详细写出了递归的思考过程。

# 344. 反转字符串 (opens new window)

题解：

知识点：双指针
除了传统的双指针法，当然也可以通过递归得到方式完成。
参考代码中，给出了两种递归函数的写法，一个是需要在函数体内部return出去，一个则是对公共变量s做出操作，最后return的是s

伪代码：

// 模板写法：第1步构造方便调用的结论(函数)
function convert(i){
    if(递归首先写截至条件){return}
    // 代码主体功能编写
    convert(...) //自调,若返回的不是答案
    return convert(...) // 若返回的是答案，需要return一下
}

//
return convert(...)

1
2
3
4
5
6
7
8
9
10

点击查看

参考代码：

var reverseString = function(s) {
    //  构造一个新的函数，方便完成递归的操作
    convert = (left, right) => {
        if (left >= right) return;
        [s[left], s[right]] = [s[right], s[left]];
        convert(left + 1, right - 1);
    };
    convert(0, s.length - 1);
    return s;
};

1
2
3
4
5
6
7
8
9
10

第二种构造稍微复杂一些

var reverseString = function(s) {
    // 这里输入的i是只s的索引，直到中部截止
    convert = i => {
        //  截止条件
        if (i === half + 1) {
            return;
        }
        let left = i;
        let right = s.length - i - 1;
        [s[left], s[right]] = [s[right], s[left]];
        //  需要将结果return出去[实际上这里有问题，这里只做演示]
        return convert(i + 1);
    };
    let half = Math.floor((s.length - 1) / 2);
    return convert(0);
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 24. 两两交换链表中的节点 (opens new window)

图解题解：

伪代码：

function reverse(){
    1. 编写截止条件
    2. 编写1,2皆存在时的连接操作
    3. return 结果
}

1
2
3
4
5

点击查看

参考代码：

var swapPairs = function(head) {
    if (head === null || (head !== null && head.next === null)) {
        return head;
    }
    const newHead = head.next;
    head.next = swapPairs(newHead.next);
    newHead.next = head;
    return newHead;
};