递回函式与回溯法优化

题组回顾与观念统整

前三天的练习我们深入「递回（Recursion）」的方法做了一连串的实作练习，不管是在链结串列或是树结构，还有其他的问题中也都能看到递回的方法。所以递回绝对是你必须掌握的一种重要算法，能够让你的程序写的更精简、更优雅。我们一起回顾这几个有趣的递回应用题：

• LeetCode 双刀流： 24. Swap Nodes in Pairs
• LeetCode 双刀流： 236. Lowest Common Ancestor of a Binary Tree
• LeetCode 双刀流： 90. Subsets II

➤ 24. Swap Nodes in Pairs

这是一个链结串列中的「交换」的问题，实现「两两节点的数值交换」但「两两节点的链结不变」的题目。方法 ① 是很直觉利用迭代两两交换，每次记录两个节点数值交换，之後再将两个节点指标往後移动；方法 ② 利用递回以两个点为一组进行交换，在持续下一组直到全部交换完。

➤236. Lowest Common Ancestor of a Binary Tree

从二元树中寻找两个节点的共同上层（Lowest Common Ancestor（最低共同祖先））。第一种解法直接将此转换成递回的形式，需要找的是「两棵左右子树的根节点」或「这两个节点中最低的那个节点作为最低共同祖先（LCS）」。方法 ② 用回圈的方式进行迭代，采用中序遍历的方式将经历过的点暂存到一个 Stack 中再一层一层回传找到最近的上层；方法 ③ 第三种方法是我们可以分成两个回圈，第一个先找出其中一点的所有祖先，然後第二个回圈去判断是否有跟第一个点收集到的祖先重复。

➤ 90. Subsets II

这是一道类似「排列组合」的练习题。排列组合的基本想法就是把所有的可能穷举出来，重点在於如何让这个过程穷举的过程更有效率。所以在本题里面我们试着用递回的概念来转化原本的问题，试着让过程可以被简化。方法 ① 采用穷举法的方法用两个回圈把所有可能都跑过一次，只是在过程中会将「已经被考虑过元素组合剔除」。方法 ② 的递回法利用排列组合的概念，使用递回的方式来处理，从一个元素开始，每一层多增加一个元素的方式直到全部考虑完毕。

递回（Recursion)

什麽是递回？

根据维基百科的定义：递回在电脑科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。程序语言支援函式的自呼叫，函式可以通过呼叫自身来进行递回 。一个递回函式的设计模式如下：

function foo(parameters) { 
    if (Base Case) 
        return 结果
    else 
        General Case ( foo() )
}

Reference: GeeksforGeeks

How Recursion Works ?

递回执行时需要将「当前函式执行的状况暂存下来，先中断执行下一层」，具体可以分成以下几个步骤：

1. 暂存存当前函式执行的狀况，将必要的资料存到记忆体中的 Stack 区段中。包含：区域/暂存变數值、
   返回位址等等
2. 将控制权转移到下一层呼叫的函式
3. 当下一层呼叫的函式与触发递回终止条件时，要从 Stack 区段中取出资料，然後返回前一个函式

Reference: tutorialspoint

Recursion vs Iteration

回溯（Backtracking）

什麽是回溯？

根据维基百科的定义：回溯法是暴力搜寻法中的一种。 对於某些计算问题而言，回溯法是一种可以找出所有解的一般性演算法，尤其适用於约束补偿问题。回溯法采用试错的思想，它尝试分步的去解决一个问题。

简单来说，回溯其实就是在递回递增地建立所有可能中，筛选掉不可能的组合，最终得到所要的答案。实务上我们也可以搭配深度优先先搜寻法 (DFS) 对每一个节点进行检查，搭配递回或 Stack 计算过程中的暂存资料。

回溯跟真正的暴力法有什麽差？

可以从「排列组合」的例子来看回溯跟真正的暴力法的差别，回溯法即是在暴力法穷举的过程中，只考虑「真的」有可能出现的组合（如下图）。

function recPermute(soFar, rest){
  if(!rest) return soFar; //印出结果, 并回溯
  for(var i = 0; i < rest.length; i++) { // 由所有可选择中依序取一
    var next = soFar + rest.charAt(i); // 由可选择取一,与目前所选择组合(串接)
    var remaining = rest.substr(0,i) + rest.substr(i+1);  // 移去已取出的 rest[i]
    recPermute(next, remaining); // 由剩余的来取出下个位置的字元(递回建立所有可能的组合)　
  }       
}

function listPermutation(listString){
  recPermute("", listString);
}

listPermutation("ABC");

嗨，大家好！我是维元，一名擅长网站开发与资料科学的双栖工程师，斜杠於程序社群【JSDC】核心成员及【资料科学家的工作日常】粉专经营。目前在 ALPHACamp 担任资料工程师，同时也在中华电信、工研院与多所学校等单位持续开课。拥有多次大型技术会议讲者与竞赛获奖经验，持续在不同的平台发表对 #资料科学、 #网页开发 或 #软件职涯 相关的分享，邀请你加入 订阅 接收最新资讯。