岔路上的风景 - 递回

在学习JS的路上意外接触到了递回的概念，一开始觉得这是什麽鬼东西，回圈用的好端端的，为什麽需要学习难懂的递回？

虽然学会递回不会让你摇身一变成为JS大师，但却可以让自己在思考问题的解决方式时多了一种叙述方式，不好奇吗？

以下先用轻松的例子认识一下递回。

日常生活举例

举例及图片来源：freeCodeCamp: Recursion in Programming

想像今天要去买珍珠奶茶，结果店家前大排长龙，你想知道还要等多少个人才能轮到你点餐，这时你可能会侧身往前望向柜台前的第一个人然後开始数数，依序数排在前面有多少人，这的确是最直觉的方法，但很累（是有多懒）。

除此之外，其实可以往前拍拍前一位在排队的大叔，问说：你前面还有几位在等啊？可能大叔也不知道自己还要等几位才轮到他，於是也拍拍前面的少女，重复同样的问题，如此重复下去直到站在柜台前点餐的学生不耐地转过头说：没看到我正在点餐吗？下一位就换你了！这时排队人龙里的每个人就可以依序告诉後面的人自己是排在第几位了。这样的懒人方式就是递回的精神（别闹了）

定义与其基本形式

维基百科介绍递回是这麽说的:

在电脑科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法

在程序语言中则是透过一个函式呼叫函式本身也就是所谓的递回函式来实现递回的概念

不过如果函式不断呼叫自己，不是会形成无穷回圈吗？所以必须再加上一个终止条件，综合上述就会形成下列的递回基本形式：

1. A simple base case (or cases) — a terminating scenario that does not use recursion to produce an answer
2. A recursive step — a set of rules that reduces all successive cases toward the base case.

回到一开始买珍珠奶茶的例子，我们来看看真实生活的行为如何对应到递回的形式

1. 终止条件：问到目前正在点餐的客人为止
2. 递回步骤：不断地询问前一位等待的人是第几位是递回步骤

有了基本概念後，来实际看看程序码吧～

递回经典例子

尝试理解递回时，最常看到的范例就是高中数学学过的阶乘啦。
阶乘的定义是所有小於及等於该数的正整数的积，记为n!
例如：3! = 3 * 2 * 1 = 6

运用递回的概念则阶乘的计算可以简化成 n! = n * (n - 1)！
转换成程序码如下：

function factorial(n) {
  if (n <= 1) {
    return 1;
  } else { 
    console.log(`${n} * factorial(${n - 1})`); // 此行程序码只为了观察递回的过程，不是递回的一部份 
    return n * factorial(n - 1);
  }
}

const result = factorial(5);
console.log(result);  

// 5 * factorial(4)
// 4 * factorial(3)
// 3 * factorial(2)
// 2 * factorial(1) --> 终止条件 
//120

至於电脑是如何实现递回的必须再研究call stack，待日後再来好好深入研究啦～

参考资料：
Understanding Recursion in Programming
递回 (电脑科学)
递回的美丽与哀愁