遞迴(Recursion)

詳細內容
分類：Javascript
發佈：2013-06-12, 週三 21:22
點擊數：2796

遞迴(Recursion)：

遞迴是一種函式在函式本體內呼叫自己的程式設計技巧。遞迴是一種很"直觀"的設計技巧。會這麼說是因為有些特殊例子使用其他演算法，像是迴圈來解釋的話會十分複雜，但使用遞迴的話，演算法就會變得很直觀。最著名的例子大概就是河洛塔( Hanoi tower)了。不過Hanoi tower其實有點複雜。所以就用一個簡單的入門例子吧。求某數值的階乘n!。這例子其實可以用迴圈解，也不太難。不過簡單好理解，所以很常被用來解釋遞迴。迴圈解法就不說了，反正就是一直跑迴圈就是。

而遞迴的解法就是把它想成，n! 等於 n * (n-1)!。看出來了嗎，假設你有一個求階乘的函式，輸入數值可以是n，當然也可以是n-1，所以你這函式其實就是在內部又呼叫了自己一次。把它簡化到極點，看起來會像這樣

f(n){

return n* f(n-1);

}。

當然這樣寫會有問題，一般寫遞迴時都必須要特別注意結束條件，這很重要，個人認為遞迴是最容易不小心造成無窮迴圈的。而這裡的結束條件其實明顯就是當數值等於0時，這時候在呼叫f(0-1)就很不合理了。通常學過數學的也知道0!=1。所以這題的結束條件就是當n=0時，f(n)=1。現在把它加進函式內。

f(n){

if(n==0){

return 1;

}

return n* f(n-1);

}

當然這還是有問題，因為這種解法不允許負數。所以還要再加上一個條件拒絕負數。

最後的程式碼：

<script type="text/javascript">
function f(n){
if (n<0){
return 0;
}
else if(n==0){
return 1;
}
return n* f(n-1);
}
document.writeln(f(5));
</script>

另外要注意的是，過於複雜的遞迴是很耗資源的，因為每一次的函式呼叫都占用一些記憶體來放置函式內的區域變數。而且如果遞迴佔著執行緒太久，可能會造成各種事件的處理延遲。如果結束條件沒設定好還會造成無窮迴圈。以前在DOS寫C時這是會讓系統直接當掉了(學生時代總是會這樣搞 >"<)。

遞迴示意圖，超好玩。來自https://plus.google.com/u/0/108236131842416283132/posts/4nBkdmWBtY6

 

如果你想更了解其他函式觀念，可以參考看看下面這篇文章：函式 Function。

我把許多函式的觀念與用法都收集在這篇文章內。

 
 

  按個讚!~支持本站!~

FB推薦載入中  

你可能會有興趣的文章

返回本頁開頭    返回部落格首頁