一、Recursion
1.1 基本觀念介紹
遞迴就是在函式之中呼叫函式自己本身，本質上是將複雜的問題，拆分成具有相同性質的子問題，進而解決問題的方法。
一個基本的遞迴函式一定要有：
終止條件 (基本條件)
遞迴條件 (呼叫自己的條件)
如果沒有終止條件，就會無限循環直到當掉。
範例 1 : 假設輸入一個正整數 n，求 1 + 2 + … + n 的總和
我們可以很直覺的使用迭代 (迴圈) 的方式，將所有數字累加在一起。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function sum(n) { | |
| let result = 0; | |
| for (let i = 1; i <= n; i++) { | |
| result += i; | |
| } | |
| return result; | |
| } |
但因為這個問題能拆成有規律的數個小問題，
如輸入正整數 2 → 1 + 2 = 3
輸入正整數 3 → 1 + 2 + 3 = 6
…
所以這時候就可以使用遞迴來計算。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function sum(n) { | |
| if (n === 1) { | |
| return 1; | |
| } | |
| return n + sum(n - 1); | |
| } |
Time complexity 是 O(n)，Space complexity 是 O(1)。
