前言

在解題時可能會遇到一些問題不是正常的迴圈就可以解決的，可能需要用到前面的答案來運算，像是計算階乘、費氏數列等等，就會使用到遞迴了！

遞迴 Recursion

把一件複雜的工作拆分成很多簡單的小工作來處理，這個方法稱為 Divide and Conquer approach 分治法。

遞迴就是根據這個概念形成的，把一個大問題拆成很多個中問題，再把這些中問題拆分為許多早小問題，這些小問題都用同樣的 function 來解，用這個方式來解決大問題就稱作遞迴 Recursion。

這種呼叫自己的動作，就被認為具有遞迴的性質，為了避免函式無止盡的呼叫自己，形成無窮迴圈，所以需要有終止條件，來明確定義什麼時候該結束。

階乘 Factorial

數學中的階乘符號用 ! 來代表，n! = 1 * 2 * ... * n

以數學方式表示 n 階層的話如下圖

可以看出 n! = n * (n - 1)!，我們就可以用這個概念來寫出遞迴的程式。

0! = 1
1! = 1
n! = n * (n - 1)!, n >= 1 

def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n - 1)

print(factorial(5))

呼叫的為 5! 所以可以拆分為 5 * 4! 再把 4! 拆分為 3!...依此列推，就可以運算出階乘了

今天先介紹到階乘，明天繼續來介紹同樣很有名的費氏數列，還有遞迴的一些限制，明天見

待續...