如何理解‘递归’？

‘递归’是程序设计中的常用编码技巧

对于新手程序员来说，如何设计和理解递归程序是个难题。

本篇内容将带领读者掌握递归设计的要素。

以 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;
};

递归的‘底层思想’是什么？

递归是程序反复调用自身的过程。如果复杂问题可以划分为相同的小过程依次解决，说明可以用递归。

反之，理解递归要先从‘全局’的角度抽出来，重点观察‘局部’。

因为每一级都相同，所以要重点观察‘单级’的过程是什么样的。

我们总结出递归的三要素：

• 终止条件
• 单级递归的操作
• 返回值

结合上题分析：

1. 终止条件：链表只有一个节点，或者没有下一个节点，即链表无法进行节点交换的场景。
2. 单级递归的操作：交换head和next，并将交换后的尾（head）指针指向下一级返回的链表。
3. 返回值：已经交换好的链表部分 也就是当前级的头（next）。

理解本文中的递归三要素，多写多练，相信读者一定会产生自己的理解。