Cách tạo hàm đệ quy (recursive function) trong Python

Recursion: Hàm gọi chính mình. Cần base case để tránh vô hạn.

Ví dụ: Tổng n số tự nhiên đầu tiên

def sum_n(n):
    if n == 0:
        return 0
    else:
        return n + sum_n(n - 1)

print(sum_n(100))  # 5050
print(sum_n(500))  # 125250

Đầu ra

5050
125250

Cấu trúc hàm đệ quy

1. Base case: Điều kiện dừng (n == 0).
2. Recursive case: Gọi lại với problem nhỏ hơn (n + sum_n(n-1)).
3. Progress: Mỗi gọi phải tiến gần base case.

Lưu ý

• Giới hạn đệ quy mặc định ~1000 (sys.setrecursionlimit() có thể tăng nhưng risk stack overflow).
• Tail recursion không được tối ưu trong CPython.
• Dùng loop hoặc functools.lru_cache cho performance.

Ví dụ Fibonacci với memoization

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

print(fib(100))  # 354224848179261915075 (nhanh nhờ cache)