Recursion,中文翻譯「遞迴」
在演算法實際操作就變成:
在函示之中呼叫函示自己本身
至於怎麼呼叫呢?以兩個數學案例來實作
把自己叫出來相加:Fibonacci


var fib = function(N) {
if(N<=1) return N
return fib(N-1)+fib(N-2)
};
* 當N>1 回傳fib(N-1)+fib(N-2)
* 當N<=1 回傳 N (終止條件)
* IF fib(4) = ?
fib(4)
/ \
fib(3) fib(2)
/ \ / \
fib(2) fib(1) fib(1) fib(0)
/ \
fib(1) fib(0)函式有後進先出的特性,因為函式堆疊在執行時需等候裡面的函式執行完,才執行自己的內容,如上當fib(4)時,因為N>1,所以回傳fib(3)+fib(2),惟按函式會一次次解構至終止條件,再回傳函式結果,因此遞回函式的終止條件也很重要。
這個演算法的時間複雜度為:O(2^n);空間複雜度:O(n)
把自己叫出來相乘:Factorial 階乘

var factorial = function(N) {
if (N === 1) return N
return N * factorial(N - 1)
}
* 邏輯與與上相似,只是將函示回傳結果相乘
* 這個演算法的時間複雜度為:O(n)
But 在現實程式世界…
遞迴只應天上有,凡人應當用迴圈
函式利用呼叫自身來運行,看數列遞增的速率就知道,佔記憶體且效率很差,而且遞迴能完成的事,迴圈似乎也都能完成,但遞迴還是有一些優點和解決效率問題:
- 程式碼簡潔優美
- 適合用來解決樹狀(tree traversal)的邏輯問題
- 利用「空間換取時間」的方法提升效率,亦即將函式的結果打包儲存,再重複使用時直接呼叫結果
Leetcode
針對這類型練習,請參考我的Github
