Cách viết hàm đệ quy (recursive) trong Python?

Hàm đệ quy là hàm tự gọi chính mình. Cần có điều kiện dừng (base case) để tránh vô tận.

Ví dụ 1: Tính giai thừa (Factorial)

def factorial(n):
    if n == 1:          # base case
        return 1
    else:
        return n * factorial(n - 1)

number = 9
print("Giai thừa của", number, "là", factorial(number))

Giai thừa của 9 là 362880

Quy trình: 9 * 8 * 7 * ... * 1. Mỗi lần gọi giảm n xuống 1 cho đến base case.

Ví dụ 2: In dãy số xuôi và ngược

def function(x):
    if x < 1:
        return
    else:
        print(x, end=" ")
        function(x - 1)
        print(x, end=" ")

function(5)

5 4 3 2 1 1 2 3 4 5

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

def recursive_func(params):
    if base_case_condition:
        return base_value
    else:
        # xử lý
        return recursive_func(modified_params)

Lưu ý quan trọng

• Giới hạn đệ quy: Python mặc định giới hạn 1000 lần gọi đệ quy (sys.getrecursionlimit()). Có thể tăng: sys.setrecursionlimit(2000).
• Hiệu năng: Đệ quy tốn bộ nhớ stack. Với bài toán đơn giản (giai thừa, Fibonacci), nên dùng vòng lặp hoặc functools.lru_cache để memoization.
• Tail recursion: Python không tối ưu tail recursion.

Ví dụ Fibonacci với cache

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(i) for i in range(10)])

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]