今天假如要寫一個求 1 + 2 + … + n 的總和，一般人可能很直覺的就想到說，要用迴圈的方式把所有值都加在一起。

1
2
3
4
5
6
7
8
9
function add(n) {
  let result = 0;
  for (let i = 1; i <= n; i++) {
    result += i;
  }
  return result;
}

console.log(add(5)); // 15

但除了迴圈之外，還有另外一種名為遞迴的技巧也能達成相同的效果。

1
2
3
4
5
6
7
8
9
function add(n) {
  if (n === 1) {
    return 1;
  } else {
    return n + add(n - 1);
  }
}

console.log(sum(5)); //15

我們先來看一下遞迴(recursion)在mdn上面的定義：

The act of a function calling itself, recursion is used to solve problems that contain smaller sub-problems. A recursive function can receive two inputs: a base case (ends recursion) or a recursive case (resumes recursion).

簡單來說，就是一種自己呼叫自己的意思，利用自己呼叫自己來解決問題，通常需要被遞迴的問題是一個可以被分成很多小問題的大問題。

函數在運行時，有時會呼叫很多其他的函數來達到目的，在一些特殊的情況下，甚至會呼叫自己，而這種函數運行時會呼叫自己的技巧，就是遞迴。

而通常可以使用迴圈解決的問題，也可以用遞迴來做解決，原本只會使用迴圈的我，想不通幹嘛要用遞迴，後來想想其實多了一種新的解決問題的方式是一件好事，而且其實遞迴的程式碼通常比迴圈少，

會想要特別寫遞迴是因為一開始看不太懂，但突然看著看著就有了一些概念覺得蠻特別的，所以就來試著講解做個紀錄。

一個基本的遞迴會需要有：

  1. 終止條件
  2. 遞迴條件

第一個是因為假如沒有終止條件，那函式不斷的呼叫自己，最後就會變得沒完沒了，程式將無窮無盡不會結束。

而遞迴條件就是呼叫自已的條件，沒有終止條件就會無限循環然後當掉，但是沒有遞迴條件就沒辦法呼叫自己，程式就不知道怎麼呼叫。

舉個例子:
小白跟他朋友講一個故事，故事裡面是一個人跟他朋友講一個故事，而這個故事裡面是一個人跟他朋友講故事……

而在程式中，遞迴有一個經典的例子。

費氏數列


以費波那契數為邊的正方形拼成的近似的黃金矩形。
圖片來源：https://zh.m.wikipedia.org/zh-tw/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0

在數學上，費波那契數是以遞迴的方法來定義：

  • f0=0 (1)
  • f1=1 (2)
  • Fn = Fn-1+Fn-2 (3)

其中(1)跟(2)就是上述提到的終止條件，而(3)是遞迴的定義。

簡單來說，費式數列是從零開始，之後的數字都是由前面的數字兩者相加而成：

1
1、 1、 2、 3、 5、 8、 13、 21、 34、 55、 89、 144、 233、 377、 610

寫法會像這樣:

1
2
3
4
5
6
function fibonacci(n) {
  if (n < 2) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

總結

可能實際在寫程式時不會使用到遞迴，因為其實沒有非遞迴就不能解決的問題，它比較像是解決問題的另一種思路而已，所以多了解是沒有壞處的。

我個人認為遞迴有兩個優點，第一個是使用後的程式碼會看起來很少，程式碼看起來簡潔舒服，第二個是感覺比較專業，因為大部分人都用迴圈，用遞迴直接變得與眾不同了起來，大家也可以在寫程式中嘗試看看遞迴這個技巧。

reference

[1] mdn - 遞迴
[2] JavaScript 學演算法（二十二）- 遞迴 Recursion
[3] Javascript 的遞迴(Recursive)
[4] JavaScript 演算法之遞迴
[5] 維基百科-費波那契數