‘递归’是程序设计中的常用编码技巧
对于新手程序员来说,如何设计和理解递归程序是个难题。
本篇内容将带领读者掌握递归设计的要素。
以 leetcode 24. 两两交换链表中的节点 为例:
常规解法
var swapPairs = function (head) {
if (!head || !head.next) return head;
let ret = new ListNode(0, head),
p = ret,
q = p.next;
while (shouldSwap(q)) {
p.next = reverseTwo(q, 2);
p = q;
q = p.next;
}
p.next = q;
return ret.next;
};
var shouldSwap = function (head) {
let n = 2;
let temp = head;
while (--n && temp) {
temp = temp.next;
}
return temp != null;
};
var reverseTwo = function (head, n) {
if (n == 1) return head;
let tail = head.next;
let p = reverseTwo(head.next, n - 1);
head.next = tail.next;
tail.next = head;
return p;
};
递归解法
var swapPairs = function (head) {
if (!head || !head.next) return head;
let next = head.next;
head.next = swapPairs(next.next);
next.next = head;
return next;
};
递归的‘底层思想’是什么?
递归是程序反复调用自身的过程。如果复杂问题可以划分为相同的小过程依次解决,说明可以用递归。
反之,理解递归要先从‘全局’的角度抽出来,重点观察‘局部’。
因为每一级都相同,所以要重点观察‘单级’的过程是什么样的。
我们总结出递归的三要素:
- 终止条件
- 单级递归的操作
- 返回值
结合上题分析:
- 终止条件:链表只有一个节点,或者没有下一个节点,即链表无法进行节点交换的场景。
- 单级递归的操作:交换head和next,并将交换后的尾(head)指针指向下一级返回的链表。
- 返回值:已经交换好的链表部分 也就是当前级的头(next)。
理解本文中的递归三要素,多写多练,相信读者一定会产生自己的理解。