Dùng đệ quy để giải bài toán nhỏ dần

Lan xếp 4 hộp quà theo tầng. Để đếm số hộp từ tầng 1 đến tầng 4, bạn nhận ra tổng cần tìm bằng 4 cộng với tổng của 3 tầng đầu. Quy tắc ấy lặp lại cho tới khi không còn tầng nào. Một hàm có thể diễn đạt đúng cách suy nghĩ này bằng cách gọi chính nó.

Bài toán lớn có thể gọi một bài toán nhỏ cùng kiểu

Đệ quy (recursion) là cách mô tả một bài toán bằng một hoặc nhiều bài toán nhỏ hơn cùng loại. Hàm total(n) dưới đây trả tổng các số từ 1 đến n, với n không âm.

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

print(total(4))
print(total(0))

10
0

total(4) cần kết quả total(3). Lời gọi nhỏ dần đến total(0), rồi kết quả được cộng ngược lên. total(0) trả 0 ngay, không gọi thêm.

Trường hợp dừng (base case) là đầu vào có thể trả lời trực tiếp. Bước đệ quy (recursive step) đưa bài toán hiện tại về một bài toán nhỏ hơn. Ngoài hai phần ấy, cần chỉ rõ cách ghép lời giải nhỏ thành lời giải lớn.

Trong total(n), mỗi bước giảm n một đơn vị. Với n không âm, chắc chắn sau n bước sẽ chạm 0. Nếu cho n âm, quy tắc này không chạm 0; phải đổi điều kiện hoặc giới hạn đầu vào.

Lời gọi chờ trên ngăn xếp rồi trả kết quả theo chiều ngược lại

Mỗi lần gọi hàm tạo một khung lời gọi (call frame) chứa tham số, biến cục bộ và vị trí cần tiếp tục. Các khung đang chờ tạo thành ngăn xếp lời gọi (call stack). Khung được gọi sau hoàn thành trước, giống chồng hộp lấy từ trên xuống.

Khung total(1) nhận 0, cộng 1 và trả 1. Khung total(2) nhận 1, cộng 2 và trả 3. Cuối cùng total(3) nhận 3 và trả 6. Mỗi khung có giá trị n riêng, dù cùng chạy một hàm.

Đoạn sau cho thấy lệnh trước lời gọi chạy lúc đi xuống; lệnh sau lời gọi chạy lúc quay lên.

def visit(n):
    if n == 0:
        print("dung")
        return
    print("xuong", n)
    visit(n - 1)
    print("len", n)

visit(3)

xuong 3
xuong 2
xuong 1
dung
len 1
len 2
len 3

Lời gọi visit(1) phải hoàn thành trước khi visit(2) in dòng lúc quay lên. Vì không trả giá trị tường minh ở cuối, mỗi lời gọi visit trả None.

Chứng minh bằng trường hợp dừng và bước ghép

Với n = 0, hàm trả 0, đúng tổng của dãy rỗng. Giả sử total(n - 1) đúng. Tổng từ 1 đến n gồm tổng từ 1 đến n - 1 và thêm n, nên biểu thức trả về cũng đúng. Lập luận này áp dụng lần lượt từ 0 đến n.

Hàm tạo n + 1 khung, mỗi khung làm một lượng việc cố định. Thời gian là O(n) và bộ nhớ ngăn xếp là O(n). Với n = 100, có 101 lời gọi; với n = 100000, độ sâu quá lớn đối với cách đệ quy thông thường trong Python.

def total_loop(n):
    answer = 0
    for x in range(1, n + 1):
        answer += x
    return answer

print(total_loop(4))
print(total_loop(100))

10
5050

Vòng lặp vẫn tốn O(n) phép cộng, nhưng chỉ dùng O(1) biến phụ. Bài toán này cũng có công thức trực tiếp; mục đích ở đây là nhìn rõ sự khác nhau về khung lời gọi.

Giai thừa cần trả 1 ở trường hợp không có thừa số

Giai thừa của n không âm là tích các số từ 1 đến n. Theo quy ước, 0! = 1. Với n > 0, tích này bằng n nhân với giai thừa của n - 1.

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

for n in [0, 1, 4, 6]:
    print(n, factorial(n))

0 1
1 1
4 24
6 720

Giá trị 1 ở điểm dừng giữ nguyên tích khi nhân; trả 0 sẽ làm mọi kết quả bằng 0. Với n = 6, chương trình tạo 7 khung và thực hiện 6 phép nhân. Thời gian đếm theo số phép nhân là O(n); bộ nhớ ngăn xếp là O(n). Số nguyên lớn dần nên chi phí từng phép nhân thực tế không cố định khi n rất lớn.

Chia nguyên giúp tổng chữ số ngắn đi nhanh chóng

Với số không âm n, n % 10 lấy chữ số cuối. Phần n // 10 bỏ chữ số cuối. Hàm dưới đây dừng ở 0 và cộng dần khi các lời gọi trở về.

def digit_sum(n):
    if n == 0:
        return 0
    return n % 10 + digit_sum(n // 10)

for value in [0, 8, 4072, 999]:
    print(value, digit_sum(value))

0 0
8 8
4072 13
999 27

Với 4072, các phần còn lại lần lượt là 407, 40, 4 và 0. Mỗi bước bỏ một chữ số, nên với d chữ số có O(d) lời gọi và dùng O(d) khung. Đầu vào âm cần một quy ước riêng; không đưa số âm trực tiếp vào hàm này.

Chỉ số mô tả phần danh sách còn phải xử lý

Đặt suffix_sum(a, i) là tổng từ chỉ số i đến hết danh sách. Khi i == len(a), phần còn lại rỗng và tổng bằng 0. Nếu còn phần tử, cộng a[i] với tổng từ vị trí kế tiếp.

def suffix_sum(a, i):
    if i == len(a):
        return 0
    return a[i] + suffix_sum(a, i + 1)

values = [4, -2, 7, 0]
print(suffix_sum(values, 0))
print(suffix_sum(values, 2))
print(suffix_sum([], 0))

9
7
0

Mỗi lời gọi tiến i thêm 1, không tạo bản sao của danh sách. Với n phần tử, hàm tốn O(n) thời gian và O(n) khung. Dùng lát cắt a[1:] mỗi lần còn phải sao chép nhiều phần tử; tổng số phần tử bị sao chép có thể lên tới O(n²).

Euclid làm phần dư nhỏ dần

Với hai số không âm a, b, không đồng thời bằng 0, ước chung lớn nhất (greatest common divisor) không đổi khi thay cặp (a, b) bằng (b, a % b). Khi b bằng 0, đáp án là a.

def gcd(a, b):
    print(a, b)
    if b == 0:
        return a
    return gcd(b, a % b)

print("uoc chung lon nhat:", gcd(48, 18))

48 18
18 12
12 6
6 0
uoc chung lon nhat: 6

Một số chia hết cả a và b cũng chia hết a - (a // b) * b, tức phần dư. Chiều ngược lại cũng đúng, nên tập ước chung không đổi. Phần dư luôn nhỏ hơn b dương, vì vậy quá trình dừng. Số bước là O(log(max(a, b))); bộ nhớ bằng số khung đang chờ.

Hai nhánh đệ quy có thể tính lại cùng một việc

Dãy Fibonacci bắt đầu bằng F(0) = 0, F(1) = 1; mỗi số tiếp theo là tổng hai số trước. Ví dụ sau đếm cả số lần gọi để quan sát chi phí.

calls = 0
def fib(n):
    global calls
    calls += 1
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print("gia tri:", fib(6))
print("so loi goi:", calls)

gia tri: 8
so loi goi: 25

fib(4) được tính từ cả nhánh fib(5) lẫn nhánh còn lại của fib(6). Số lời gọi tăng theo cấp số nhân, nên cách tính theo đúng định nghĩa không dùng được với n lớn. Tính tuần tự sau đây giữ hai kết quả gần nhất và tránh tính lại.

def fib_loop(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

for n in [0, 1, 6, 20]:
    print(n, fib_loop(n))

0 0
1 1
6 8
20 6765

Mỗi vòng tạo giá trị Fibonacci kế tiếp. Với n = 20, có 20 vòng, tức O(n) phép cộng; hai biến giữ O(1) số nguyên. Với n rất lớn, bản thân các số nguyên cũng cần nhiều bit hơn.

Tính hai số Fibonacci cùng lúc giúp bài toán nhỏ đi một nửa

Để tìm một số Fibonacci ở chỉ số lớn hơn, ta có thể cho một lời gọi trả về cả hai giá trị liên tiếp. Đặt pair(n) là cặp (F(n), F(n + 1)). Ở điểm dừng, pair(0) là (0, 1).

Giả sử đã biết a = F(k) và b = F(k + 1). Khi đó F(2k) = a * (2 * b - a) và F(2k + 1) = a * a + b * b. Hai công thức này cho phép tìm cặp ở chỉ số gấp đôi từ một cặp nhỏ hơn.

Với n chẵn, đặt k = n // 2 và trả (F(2k), F(2k + 1)). Với n lẻ, cần trả (F(2k + 1), F(2k + 2)). Số sau cùng bằng tổng hai số vừa tính.

def pair(n):
    if n == 0:
        return 0, 1
    a, b = pair(n // 2)
    c = a * (2 * b - a)
    d = a * a + b * b
    if n % 2 == 0:
        return c, d
    return d, c + d

for n in [0, 1, 2, 5, 6, 10]:
    print(n, pair(n))

0 (0, 1)
1 (1, 1)
2 (1, 2)
5 (5, 8)
6 (8, 13)
10 (55, 89)

Chẳng hạn, từ cặp (1, 2) ứng với k = 2, ta tính c = 3 và d = 5. Vì 5 lẻ, pair(5) trả (5, 8). Bạn có thể kiểm tra hai công thức qua đẳng thức cộng chỉ số F(u + v) = F(u - 1) * F(v) + F(u) * F(v + 1) khi u > 0.

Thay u = v = k cho công thức chỉ số chẵn. Ta dùng F(k - 1) = F(k + 1) - F(k). Thay u = k + 1, v = k cho công thức chỉ số lẻ. Trường hợp k = 0 cho trực tiếp cùng hai kết quả 0 và 1.

Mỗi lời gọi chỉ gọi một lần với n // 2, nên có O(log(n + 1)) mức. Với n = 1000, chỉ cần khoảng 11 khung, kể cả khung pair(0). Đây là số phép toán trên số nguyên; chi phí nhân thực tế tăng theo số chữ số của các giá trị.

Chọn tham số và kiểm tra các trường hợp biên trước khi chạy

Một hàm đệ quy cần mô tả rõ giá trị trả về. Ví dụ, suffix_sum(a, i) trả tổng từ chỉ số i đến hết, chứ không phải tổng i phần tử đầu. Ý nghĩa ấy quyết định kết quả khi i == len(a).

Với đầu vào rỗng, không được đọc a[0] trước khi kiểm tra điểm dừng. Với một phần tử, cần kiểm tra cả trường hợp chọn phần tử đó và trường hợp bắt đầu ngay sau nó. Số âm cũng cần có trong ví dụ để tránh nhầm tổng với số lượng phần tử.

def suffix_sum(a, i):
    if i == len(a):
        return 0
    return a[i] + suffix_sum(a, i + 1)

for values, start in [([], 0), ([-4], 0), ([-4], 1), ([3, -5, 2], 1)]:
    print(values, start, suffix_sum(values, start))

[] 0 0
[-4] 0 -4
[-4] 1 0
[3, -5, 2] 1 -3

Nếu kết quả sai ở dãy một phần tử, hãy kiểm tra lệnh cộng và điều kiện dừng. Nếu lỗi chỉ xuất hiện ở dãy rỗng, hãy kiểm tra thứ tự đọc phần tử. Với dãy quá dài, đổi sang vòng lặp thay vì chỉ thử tăng giới hạn.

Theo dõi từng khung giúp phát hiện lỗi thiếu trả kết quả

Xét một hàm đếm số chữ số của số không âm. Với số từ 0 đến 9, đáp án là 1. Với số có ít nhất hai chữ số, bỏ chữ số cuối rồi cộng thêm 1 cho chữ số đã bỏ.

def digits(n):
    if n < 10:
        return 1
    return 1 + digits(n // 10)

for number in [0, 7, 10, 2004]:
    print(number, digits(number))

0 1
7 1
10 2
2004 4

Với 2004, các lời gọi lần lượt nhận 2004, 200, 20 và 2. Khung cuối trả 1, rồi ba khung đang chờ lần lượt cộng thêm 1. Số 0 được tính là một chữ số, dù biểu diễn không có chữ số khác 0.

Mỗi lần chia bỏ một chữ số nên hàm có d khung với số có d chữ số. Nếu coi phép chia trên các số của đề là phép toán cơ bản, thời gian và bộ nhớ đều là O(d). Với số nguyên cực lớn, phép chia cũng phụ thuộc độ dài biểu diễn của số.

Một lỗi khác là gọi hàm con nhưng không trả kết quả cho khung đang chờ. Ví dụ sau cố tình thiếu return ở nhánh chưa dừng. Hãy so sánh kết quả của hai lời gọi với lời giải đếm chữ số ở trên.

def broken(n):
    if n < 10:
        return 1
    1 + broken(n // 10)

print(broken(7))
print(broken(42))

1
None

Điểm dừng trả 1 cho 7. Với 42, biểu thức được tính nhưng không được trả, nên khung ngoài trả None. Sửa bằng cách đặt return trước biểu thức cộng. Việc chỉ kiểm tra một chữ số sẽ không phát hiện lỗi này.

Viết lại chuỗi lời gọi bằng vòng lặp khi độ sâu quá lớn

Một quy trình có đúng một bước tiếp theo thường dễ chuyển thành vòng lặp. Với tổng chữ số, giữ tổng đã xử lý trong biến answer. Phần n còn lại lưu những chữ số chưa xử lý.

def digit_sum_loop(n):
    answer = 0
    while n > 0:
        answer += n % 10
        n //= 10
    return answer

for number in [0, 4072, 99999]:
    print(number, digit_sum_loop(number))

0 0
4072 13
99999 45

Trước mỗi vòng, tổng ban đầu bằng answer cộng tổng chữ số còn lại của n. Mỗi bước chuyển đúng chữ số cuối sang answer nên quan hệ ấy vẫn đúng. Khi n bằng 0, không còn chữ số đóng góp và answer là kết quả.

Với số 4072, có bốn vòng; với số 0, không cần vòng nào. Cách này dùng O(d) bước với d chữ số và O(1) biến phụ. Nó tránh tạo một khung cho mỗi chữ số, nhưng vẫn cần thời gian cho các phép chia số nguyên.

Giới hạn độ sâu ngăn đệ quy đi quá xa

Python giới hạn độ sâu đệ quy. Ví dụ chủ động đặt giới hạn nhỏ để tái hiện lỗi, sau đó khôi phục giới hạn ban đầu.

import sys
old_limit = sys.getrecursionlimit()
try:
    sys.setrecursionlimit(80)
    def count_down(n):
        if n == 0:
            return 0
        return 1 + count_down(n - 1)
    print(count_down(200))
finally:
    sys.setrecursionlimit(old_limit)

RecursionError: maximum recursion depth exceeded

Tăng giới hạn không làm thuật toán nhanh hơn hoặc giảm số khung. Đặt giới hạn quá cao có thể làm tiến trình gặp sự cố. Với một chuỗi 100000 bước tuyến tính, vòng lặp thường là lựa chọn an toàn hơn.

def count_down_loop(n):
    count = 0
    while n > 0:
        n -= 1
        count += 1
    return count

print(count_down_loop(200))
print(count_down_loop(100000))

200
100000

Không phải mọi đệ quy đều chỉ có một nhánh. Khi chuyển thuật toán nhiều nhánh sang vòng lặp, có thể cần tự lưu trạng thái chờ trong một danh sách dùng như ngăn xếp. Bài tiếp theo dùng đệ quy để thử và hoàn tác các lựa chọn.

Lỗi thường gặp

Tóm tắt

• Xác định ý nghĩa hàm, trường hợp dừng, bước thu nhỏ và cách ghép kết quả.
• Khung gọi mới chạy trước; khi nó trả về, khung đang chờ tiếp tục.
• Chuỗi n lời gọi thường tốn O(n) bộ nhớ ngăn xếp; nhiều nhánh có thể lặp lại cùng bài toán.
• Giới hạn đệ quy là một ràng buộc thực tế; vòng lặp tránh tạo chuỗi khung cho bài toán tuyến tính.

Kiểm tra nhanh

Đọc thêm

• Tài liệu Python về giới hạn đệ quy.
• MIT OpenCourseWare 6.006: Introduction to Algorithms, khóa thuật toán có phần đệ quy và chia để trị.