javascript 中的遞迴函式（Recursive Function）

遞迴函式（Recursive Function）在JavaScript中是一種常見的程式撰寫技巧，它允許一個函式呼叫自己。這種技術在處理那些可以分解成多個相似或較小問題的任務時特別有用，如走訪樹狀結構、排序演算法等。

遞迴函式主要由兩部分組成：

• Base Case：遞迴終止的條件，防止無限遞迴。
• Recursive Step：函式呼叫自己，通常會將問題分解成更小的問題。

function factorial(n) {
    // Base Case：如果n為0，則直接回傳1
    if (n === 0) {
        return 1;
    }
    // 遞迴步驟：n! = n * (n-1)!
    return n * factorial(n - 1);
}

console.log(factorial(5)); // 輸出：120

原理：

當 n 不等於 0 時，函式會一直呼叫自身，直到 n 減少到 0。
例如，計算 factorial(3) 的過程如下：
    1. factorial(3) 回傳 3 * factorial(2)
    2. factorial(2) 回傳 2 * factorial(1)
    3. factorial(1) 回傳 1 * factorial(0)
    4. factorial(0) 回傳 1 （因為基礎情況的條件被滿足）
然後，這些回傳值會依次計算：
    1. factorial(1) 回傳 1 * 1 = 1
    2. factorial(2) 回傳 2 * 1 = 2
    3. factorial(3) 回傳 3 * 2 = 6 

最終，factorial(3) 返回 6，這也是 3! 的值。

基礎情況處理當 n 為 0 時的情況，而遞迴步驟則通過呼叫自身來計算更小數字的階乘，最終完成整個階乘計算。

注意事項：

• 終止條件：確保每次遞迴呼叫都向終止條件進展，避免無限遞迴。
• 堆疊溢位：JavaScript引擎有限制遞迴深度。如果遞迴調用太深，會導致堆疊溢位錯誤（RangeError: Maximum call stack size exceeded）。
• 效率問題：某些情況下，遞迴可能不是最高效的解決方案，尤其是在處理大量數據時。可以考慮迭代方法或動態規劃等技術。

註：堆疊溢位（英語：stack overflow）在電腦科學中是指使用過多的記憶體時導致呼叫堆疊產生的溢位，也是緩衝區溢位中的一種。堆疊溢位的產生是由於過多的函式呼叫，導致使用的呼叫堆疊大小超過事先規畫的大小，覆蓋其他記憶體內的資料，一般在遞迴中產生。堆疊溢位很可能由無限遞迴（Infinite recursion）產生，但也可能僅僅是過多的堆疊層級。

範例，讀取某元素內所有節點內容：

<div id="root">
  <div class="node">Node 1
	<div class="node">Node 1.1</div>
	<div class="node">Node 1.2
  	<div class="node">Node 1.2.1</div>
  	<div class="node">Node 1.2.2</div>
	</div>
	<div class="node">Node 1.3</div>
  </div>
  <div class="node">Node 2
	<div class="node">Node 2.1</div>
  </div>
</div>

使用遞迴讀取：

function traverseDOM(node) {
	console.log(node.nodeName + (node.id ? ' #' + node.id : '') + (node.className ? ' .' + node.className : ''));
    
	let children = node.children;
	for (let i = 0; i < children.length; i++) {
    	traverseDOM(children[i]);
	}
}

const root = document.getElementById('root');
traverseDOM(root);

這段程式碼實現了一個遞迴函式，用來遍歷 DOM 樹，並在控制台中輸出每個節點的名稱、ID 和 class。

console.log(node.nodeName + (node.id ? ' #' + node.id : '') + (node.className ? ' .' + node.className : ''));

• node.nodeName：獲取節點的名稱（例如 DIV, SPAN）。
• node.id：獲取節點的 ID，如果存在，則輸出 # 加上 ID。
• node.className：獲取節點的類名，如果存在，則輸出 . 加上class名。

這行程式碼會輸出類似於 DIV #myId .myClass 的訊息。 

工作原理

• 從 root 節點開始，traverseDOM 函式會先輸出當前節點的訊息。
• 然後，函式會獲取當前節點的所有子節點，並對每個子節點呼叫自身。
• 這個過程會一直重複，直到遍歷完所有的節點。 

以上就是 javascript 中遞迴函式使用的說明。