Recursion

Recursion，遞迴，就是在一個 function 裡叫自己的行為

數學上的 Recursion 稱為遞迴關係式，通常探討面向會是把一個遞迴的 function 找出不遞迴的 function 法
例如

f(n) = 1             n=1
f(n) = n + f(n-1)    n>1

這是一個遞迴的 function，第一行稱之為 base case，也就是初始的狀態
這個東西數學上討論時，我們就會很快發現它其實就是 f(n) = 1 + 2 + 3 +……..+ n
於是，就可以寫出不是遞迴的版本：

接著用程式的角度看，這個遞迴關係式就是：

def triangular(i):
    if i <= 1:
        return 1
    else:
        return n + triangular(n - 1)

每一個 Recursive function 都需要有的結構是：

• base case
• recursive call

def recursive_function(perameters):
    if(answer is known):
        provide the answer
    else:
        make a recursive call to solve a smaller version of the same problem

通常會由大到小，由上到下
從第一次進入 function 碰到 recursive call 開始，不斷 recursive call，最後碰到 base case，再不斷 return 直到退回第一次進入 function 的地方，然後整個 function 結束

結合上次提到的 stack 的資料型態，程式記憶體在處理遞迴時也是用 LIFO (last in first out) 的方式

不用 loop 來印出整個 list 的方法

試著寫一個不用 loop 來印出整個 list 的 function 吧，正序或倒序都可以

就像數學探討的遞迴一樣，所有遞迴的 function 都可以改成不是遞迴的寫法（用 loop）
在大部分情況下，遞迴只會讓 debug 變得非常困難，但某些複雜的問題或資料結構如果用遞迴會簡單許多，於是選擇寫法就變成最重要的課題了。

References

https://www.geeksforgeeks.org/introduction-to-recursion-data-structure-and-algorithm-tutorials/

BACK