---

title: 遞迴

---

遞迴

python

概念

簡單來說，遞迴就是一直再重複做某一件事情，直到他等於特定的值，再開始一一回傳，也就是程式中的函式一值在用函示本身。

實作

例如我們想要了解一個費氏數列如何解，我們可以透過讓他從前面的值一值計算到我們的值，而程式就是一值去呼叫某一個特定函式，直到他=特定的值再回傳果去: ``` def fib(n): if n == 0: return 0 elif n == 1: return 1 return fib(n-1) + fib(n-2)

print(fib(10)) ``` 了解費氏數列

leetcode練習

題目 實際上這題應該是要用dp來解的，不然會超時，但是我們可以先透過這題來練習看看他的testcase就好了。 這一題我們可以考慮到如果他小於3的時候有兩種解法:1+1 or 2，另外如果大於3的話就直接計算一次爬1階和2階的數量: class Solution: def climbStairs(self, n: int) -> int: def climb(n): if n<3: return n return climb(n-1) + climb(n-2) return climb(n)