我們先看JasonValue的type定義，JasonValue型別可以是string, number, boolean和null基礎型別，也可以是內含JsonValue的陣列型別或物件型別，因此我們可以如此定義JsonValue型別。
type JsonValue =
| string
| number
| boolean
| null
| JsonValue[]
| { [key: string]: JsonValue };
// 使用範例
const data: JsonValue = {
name: "Alice",
age: 20,
tags: ["dev", "ts"],
nested: { active: true }
};
許多的資料結構本身便是遞迴定義，便可以用下面的方法定義List的型別建構：
type List<A> = Nil | Cons<A>;
interface Nil {
_tag: 'Nil';
}
interface Cons<A> {
_tag: 'Cons';
head: A;
tail: List<A>;
}
另外，許多的utility type也是使用遞迴型別設計所想要的型別。我們舉一個type-fest中的例子，目的是取出元組中的第一和最後元素的型別。
type FirstArrayElement<ValueType extends readonly unknown[]> =
ValueType extends [infer ElementType, ...infer _] //是否有第一個元素型別
? ElementType // 是，取它的型別
: never; // 不是，取never
type LastArrayElement<ValueType extends readonly unknown[]> =
ValueType extends [infer ElementType] // 是否只有一個元素
? ElementType //是，取它的型別
: ValueType extends [infer _, ...infer Tail] // 是否二個元素以上
? LastArrayElement<Tail> //
: never; // 不是一個元素，也不是二個元素以上，所以是空陣列，取never
我們也能遞迴定義Typescript的utility type，如果我們想要設計一個utility type Range可以產生字面值聯集型別 0 | 1 | 2 | ... | N，下面的設計方法便使用了遞迴的utility type。
type Range<
N extends number,
Acc extends number[] = []
> = Acc['length'] extends N ? Acc[number] : Range<N, [...Acc, Acc['length']]>;
type ZeroToThree = Range<4>;
// 執行過程：
// 1. Range<4, []> → length=0 ≠ 4 → 遞迴 Range<4, [0]>
// 2. Range<4, [0]> → length=1 ≠ 4 → 遞迴 Range<4, [0, 1]>
// 3. Range<4, [0,1]> → length=2 ≠ 4 → 遞迴 Range<4, [0, 1, 2]>
// 4. Range<4, [0,1,2]> → length=3 ≠ 4 → 遞迴 Range<4, [0, 1, 2, 3]>
// 5. Range<4, [0,1,2,3]> → length=4 = 4 → 返回 0 | 1 | 2 | 3
1 Acc["length"] extends N其實是判斷Acc["length"]是否等於N，我們常利用這個技巧判斷兩個單元素型別是否相等。
2 Acc[number]是陣列的Index Access Type，因為除了Acc[0], Acc[1], Acc[2], Acc[3]的type不是never，Acc[其它index]都是never，所以聯集的結果就是Acc[0] | Acc[1] | Acc[2] | Acc[3] = 0 | 1 | 2 | 3，如此可以設計出Range。
遞迴在許多較為複雜的型別設計佔有非常的地位，在後面的內容我們會有更多的時候使用型別的遞迴定義。
遞迴函數可以說是函數式程式設計的核心概念之一，一些純綷的函數式程式設計的語言沒有迴圈，必須依賴遞迴函數來完成迴圈的工作，事實上，所有迴圈能完成的工作，都可由遞迴函數來替。遞迴函數允許函數直接呼叫自身來解決題，而設計遞迴函數時，主要分成兩個步驟：1是釐清基礎情況；2是建立遞迴關係。寫出起始狀態通常非常簡單，無需繁複的計算；而建立遞迴關係則是應用所謂的分治法(Divide and Conquer)，將原有的問題切割成較小的問題，並將它們組合成所求問題的答案。
我們先用幾個數學例子來說明建立遞迴函數的過程
1 費波那契數列
費波那契數列源自於一個兔子繁殖的問題，問題描述如下:
初始條件：
第 1 個月：1 對（新生兔子，尚未成熟），F(0) = 1。
第 2 個月：1 對（已成熟，但尚未生育）。
遞迴關係（n ≥ 3）：
因為下個月兔子數 = 這個月兔子數 + 新出生兔子數，而新出生的兔子數等於上個月的兔子數，所以
第 n 個月的兔子數 = 第 (n-1) 個月的兔子數 + 第 (n-2) 個月的兔子數
費波那契數列的定義是：F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)。我們可以用遞迴函數來實現：
const fibonacci = (n: number): number => {
if (n <= 1) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
};
高中常考的爬樓梯問題也是費氏數列的應用，問題描述如下：
眼前有五階樓梯，一次只能踏一階或踏兩階，那麼爬到五階總共有哪幾種踏法？
我們把所有的答案分成二類，第一類是第一次踏一階，那所有的踏法便是所有四階樓梯的踏法搭配第一次的一階；第二類是第一次踏兩階，所有的踏法則為所有三階的踏再搭配第一次的二階，所以F(5) = F(4) + F(3)，所以我們可以得到n階樓的遞迴公式F(n) = F(n - 1) + F(n - 2)
const steps = (n: number): Array<Array<number>> => {
if (n <= 0) return [];
if (n === 1) return [[1]];
if (n === 2) return [[1, 1], [2]];
const firstIsOne = steps(n - 1).map((step) => [1, ...step]);
const firstIsTwo = steps(n - 2).map((step) => [2, ...step]);
return [...firstIsOne, ...firstIsTwo];
};
console.log(steps(7));
2 巴斯卡三角形組合公式
我們先考慮下列組合問題：從甲、乙、丙、丁、戊5個人中選取3個人的所有選取方法有多少種？
我們先把方法數記為C(5, 3)，此時我們並不知道答案，我們可以把所有的選法分為兩大類，一類是甲被選到的，另一類則是甲未被選到。甲被選到的這一類就是從乙、丙、丁和戊4個人中選取2人，再搭配甲，所以它的方法數共有C(4, 2)；而甲未被選中情形則必須從乙、丙、丁和戊4個人中選取3人，它的選取方法數為C(4, 3)，所以總選取數C(5, 3)就等於C(4, 3) + C(4, 2)，將這個公式推廣至任意數m, n可以得到下列的組合公式
C(m, n) = C(m - 1, n) + C(m - 1, n - 1)
用遞迴函數實作這個組合公式，基礎情形為n=0和m=n，其選取數為1，其餘m, n則使用組合公式遞迴，我們的程式碼如下：
const combination = (m: number, n: number): number =>
n === 0 || n === m ? 1 : combination(m - 1, n) + combination(m - 1, n - 1);
console.log(combination(7, 3)); // 35
用遞迴思考
從上面的二個例子可以看出來，用遞迴的觀念來解決我們手上的問題時，第一步先找出最簡單的情況，通常是n=0或n=1的時候，它們的答案幾乎不用任何的計算與思考便可以獲得；接下來我們計算一個稍大的數字，譬如n=4，嘗試是否可能由n=3的結果，或是n=2, n=1的結果來獲得。 遞迴思考的精神和數學歸納法等價，像是推骰牌一樣，n=1, 2, ..., k-1知道答案，n=k便自然得到答案。
至於如何排列骰牌，這便是第二步的工作，你必須把原來n=k的問題拆解或分類，可以利用n=k-1, ..., 2, 1的值經過簡單的加減乘除得到答案。像兔子繁殖問題，我們把下個月的兔子分成二大類，一類目前的兔子，也就是這個月的兔子數，另一類則是新出生的兔子，它答案就是上個月的兔子數，這樣我們就可以輕鬆得到費氏數列的公式。組合公式也是類似的邏輯，我們把所有選取的方法分成包含甲和不包含甲的情形。
數學上遞迴的應用非常多，像是快速傅立葉計算、錯排問題，捷徑問題都可以遞迴來快速得到答案。
在陣列的處理演算法中，許多函數都可以遞迴設計。
1 求取陣列中的和
const sum = (arr: number[]): number =>
arr.length === 0 ? 0 : arr[0] + sum(arr.slice(1));
console.log(sum([1, 2, 3, 6])); // 12
這邊slice(1)等同於陣列解構[head, ...tail] = arr中rest的部分
1 求取陣列中的最大值
const maximize = (arr: number[]): number => {
if (arr.length === 0) {
throw new Error('Array must not be empty');
}
if (arr.length === 1) {
return arr[0]; // base case
}
const [head, ...tail] = arr;
const maxTail = maximize(tail);
return head > maxTail ? head : maxTail;
};
console.log(maximize([2, 3, 5, 19, 8])); // 19
排序演算法也常常可以使用遞迴函數來完成，這邊我們將介紹快速排序法和合併排序法。
2 快速排序法(Quick Sort)
[圖片來源：https://miro.medium.com/v2/resize:fit:1200/format:webp/1*-SvbPjyoV0NyGyfF5uZbEA.gif]
const quickSort = (arr: number[]): number[] => {
if (arr.length <= 1) {
return arr; // 基礎情形：只有一個元素，直接回傳原陣列
}
const pivot = arr[0]; // 選第一個陣列元素為比較基準
const left = arr.slice(1).filter(x => x < pivot); // 小於比較基準的元素得到一陣列
const right = arr.slice(1).filter(x => x >= pivot); // 不小於比較基準的元素得到一陣列
return [...quickSort(left), pivot, ...quickSort(right)]; //運用遞迴得到答案
}
console.log(quickSort([2, 17, 7, 19, 38, 24, 55, 27])); // [2, 7, 17, 19, 24, 27, 38, 55]
3 合併排序法(Merge Sort)
[圖片來源：https://miro.medium.com/v2/resize:fit:1200/format:webp/1*X-o4Ng1YsdZg13We3J4q9Q.gif]
const merge = (left: number[], right: number[]): number[] => {
if (left.length === 0) return right;
if (right.length === 0) return left;
return left[0] < right[0]
? [left[0], ...merge(left.slice(1), right)]
: [right[0], ...merge(left, right.slice(1))];
};
const mergeSort = (arr: number[]): number[] => {
if (arr.length <= 1) {
return arr; // base case: a single element is already sorted
}
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
合併排序先將原陣列分成前面一半和後面一半兩個陣列，這兩個陣列再分別遞迴進行合併排序，而合併排序完成後，再將它們合併起來。因此這個演算法會一直將陣列分成兩半，直到這兩陣列成為空陣列或只有一個元素(此為基礎情形)。兩個陣列的合併函數也是使用遞迴設計，如果其中一個是空陣列，便回傳另一個陣列，如果兩個陣列都不是空陣列，則比較兩個陣列的第一個元素，將比較小的元素拿出來，放在輸出陣列的第一個位置，再將剩餘的二個陣列進行合併。
使用遞迴來設計函數可以使得程式簡潔而優雅，大大地提升可讀性並且滿足宣告式程式設計風格，讓程式設計師專注於做什麼而非怎麼做，不必太費心於一些迴圈的細節，進而減少程式的錯錯。然而遞迴函數也有它的缺點，用遞迴函數設計函數最大的痛點在於堆疊溢位(Stack Overflow)。每次遞迴呼叫時，系統都必須在記憶體的「呼叫堆疊（Call Stack）」中分配一塊記憶體空間，用來儲存區域變數、參數和返回地址。如果遞迴層次過深，便會發生堆疊預設分配空間不足，進而導致堆疊溢位錯誤，使程式崩潰。
以下是函數式程式設計經常使用的技巧。
如果我們的遞迴函數的遞迴呼叫是在函數的最後一步執行，並立即返回，此時編(直)譯器不需要重新建立新的堆疊框架(Stack Frame)，可以使用目前的堆疊框架來進行優化，如此便可避免堆疊溢位的問題。可惜並不是所有語言都有支援尾呼叫優化(TCO)，大部分的瀏覽器實作Javascript都沒有支援。
延續傳遞風格(CPS)是非同步函數設計的基礎，也就是在函數的最後步驟將函數執行結果成為回呼函數(callback)的引數(argument)，直接執行回呼函數，而這個callback也稱為延續函數(continuation)，我們用下面非常簡單的程式例來說明CPS：
// 非CPS風格程式
const add = (a: number, b: number): number => a + b;
console.log(add(2, 3)); // 5
// 非CPS風格程式，不回傳兩數相加的結果，而是直接將執行結果丟給cont接續執行，所以這個程式的回傳值會是undefined。
const addCsp = (a: number, b: number, cont: Function) => {
cont(a + b);
};
addCsp(3, 5, console.log);
接下來，我們看看如何利用Contiunation-Passing Style將一個非尾呼叫的遞迴函數修改為尾呼叫遞迴函數，我們先檢視一個最簡單的遞迴函數-階乘函數。
const factorial = (n: number): number => {
if (n <= 1) return 1;
return n * factorial(n - 1);
};
console.log('factorial 5', factorial(5));
注意，這並非是尾呼叫遞迴，因為在計算factorial(n -1)之後，我們仍需將計算的結果乘以 n 然後才回傳。因此，我們的遞迴函數是設計便是使用identity函數(即x=>x)作為我們的延續函數cont，如果是基礎情況(n<=1)，直接回傳cont(n);如果 n> 1，我們將遞迴結果乘以n-1丟給延續函數cont，然後回傳，程式如下。
type Cont = (n: number) => number;
const factorialCsp = (n: number, cont: Cont) => {
if (n <= 1) return cont(n);
return factorialCsp(n - 1, (result) => cont(n * result));
};
console.log(
'factorialCsp 5: ',
factorialCsp(5, (x) => x)
);
當遞迴函數需要兩個以上遞迴才能計算目前的值，則延續函數的嵌套情形會變得嚴重，我們來看看費氏數列的CPS風格。
const fibonacciCps = (n: number, cont: Cont) => {
if (n <= 2) return cont(1);
return fibonacciCps(n - 2, (p) => fibonacciCps(n - 1, (q) => cont(p + q)));
};
console.log(
'fibonacciCps 7: ',
fibonacciCps(7, (x) => x)
);
很明顯，當遞迴函數中呼中超過二個(包含二個)的遞迴函數本身，延續傳遞函數便會形成嵌套，過多的嵌套便會有回呼地獄(callback hell)的恐怖情形。另外，雖然Continuation-Passint Style雖然可以完成尾呼叫優化(TCO)，但是仍無法避免堆疊溢位，接下來我們會提出可以解決堆疊溢位的技巧。
延續傳遞風格是非同步設計的底層技巧，我們顯然也可以使用非同步遞迴來解決堆疊溢位的問題。
所謂的Thunk便是無參數函數，我們定義Thunk型別建構子如下：
// Thunk 是一個無參函數，它返回另一個 Thunk 或最終結果 T
type Thunk<T> = () => Thunk<T> | T;
而我們的trampoline函數則是一個迴圈，它會一直執行我們的Thunk型別的函數直到這個Thunk型別不是函數而是一個值。
// Trampoline 函數：它接受一個初始 Thunk，並循環執行直到得到一個值
const trampoline = <T>(fn: Thunk<T>): T => {
let result: Thunk<T> | T = fn;
// 只要結果是一個函數（Thunk），就繼續執行它
while (typeof result === 'function') {
result = (result as Thunk<T>)(); // 執行 Thunk
}
// 當結果不是函數時，返回最終值
return result;
};
現在用Thunk和Trampoline來重新設計我們的factorialThunk和factorialSafe。
// Thunk 風格 (安全，免於堆疊溢位)
const factorialThunk = (n: number, acc: number = 1): Thunk<number> => {
if (n <= 1) {
// 基礎情況：返回傳值的Thunk
return () => acc; // 注意：仍然返回一個Thunk，但這個Thunk傳回 number
} else {
// 遞迴步驟：返回一個回傳Thunk的Thunk
return () => factorialThunk(n - 1, n * acc);
}
};
// 使用方式：結合 trampoline
const factorialSafe = (n: number): number => {
const initialThunk = factorialThunk(n);
return trampoline(initialThunk);
};
console.log(factorialSafe(5)); // 120
console.log(factorialSafe(100)); // 不會堆疊溢位！(雖然結果可能是 Infinity)
遞迴不僅用於函數本身，也可以用在型別的設計，尤其是一些資料結構本身便是由遞迴定義。
函數式程式設計中不使用迴圈(for loop)，也不使用while語法，許多函數必須用遞迴函數來完成迴圈和while語法的功能，而數學上已經證明迴圈能完成的工作必能由遞迴函數完成，因此遞迴函數在函數式程式計中扮演非常重要的角色。資訊科學上也有許多重要的演算法是用遞迴關係取得，例如訊號或影像處理著名的快速傅立葉轉換的演算法，便是以遞迴函數定義。學習遞迴函數必須經常的練習，找到遞迴的關鍵關係式，以完成函數的設計。
遞迴函數最主要的問題是堆疊溢位的問題，我們也介紹了TCO、CPS和Thunk&Trampoline的解決方法，由於瀏覽器和Nodejs目前都尚未支援TCO，因此要安全執行typescript遞迴函數，只能用Trampoline的技巧。今日的分享就到這邊告一段落，明天再見。
iThome鐵人賽
看影片追技術