[演算法]Recursion

Vivian Lo
Vivian Lo
Nov 4 · 3 min read
Photo by Mario Mesaglio on Unsplash

Recursion,中文翻譯「遞迴」

在演算法實際操作就變成:

在函示之中呼叫函示自己本身

至於怎麼呼叫呢?以兩個數學案例來實作

把自己叫出來相加:Fibonacci

視覺化Fibonacci(前2000項Fibonacci可參考http://oeis.org/A000045/b000045.txt)
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 階乘

Factorial遞迴方式定義
var factorial = function(N) {
if (N === 1) return N
return N * factorial(N - 1)
}
* 邏輯與與上相似,只是將函示回傳結果相乘
* 這個演算法的時間複雜度為:O(n)
表列0~26階乘(前100項可參考http://oeis.org/A000142/b000142.txt)

But 在現實程式世界…

遞迴只應天上有,凡人應當用迴圈

函式利用呼叫自身來運行,看數列遞增的速率就知道,佔記憶體且效率很差,而且遞迴能完成的事,迴圈似乎也都能完成,但遞迴還是有一些優點和解決效率問題:

  1. 程式碼簡潔優美
  2. 適合用來解決樹狀(tree traversal)的邏輯問題
  3. 利用「空間換取時間」的方法提升效率,亦即將函式的結果打包儲存,再重複使用時直接呼叫結果

Leetcode

資料來源

初學者學演算法|從費氏數列認識何謂遞迴

    Vivian Lo

    Written by

    Vivian Lo

    Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
    Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
    Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade