1. 遞迴
    1. 概念
    2. 實作
    3. leetcode練習

遞迴

最後更新: 作者: 字数: 281 预计阅读时间: 1min

遞迴

python

概念

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

實作

例如我們想要了解一個費氏數列如何解，我們可以透過讓他從前面的值一值計算到我們的值，而程式就是一值去呼叫某一個特定函式，直到他=特定的值再回傳果去:

1
2
3
4
5
6
7
8
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階的數量:

1
2
3
4
5
6
7
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)