Ôn thi HSG Tin học THPT – Bài 10: Đệ quy (Recursion)

1. Mục tiêu

Hiểu và định nghĩa được khái niệm đệ quy, bao gồm các thành phần cốt lõi là trường hợp cơ sở (điểm dừng) và bước đệ quy (lời gọi đệ quy).
Phân tích và cài đặt được các thuật toán đệ quy kinh điển như tính giai thừa và số Fibonacci.
Sử dụng được cửa sổ “Call Stack” trong môi trường Thonny để trực quan hóa quá trình thực thi của một hàm đệ quy, qua đó hiểu sâu hơn về cơ chế hoạt động của nó.

2. Bài toán dẫn nhập

Xét bài toán tính tổng các số nguyên dương từ 1 đến n, ký hiệu là S(n).
S(n) = 1 + 2 + 3 + ... + n

Một cách tiếp cận thông thường là sử dụng vòng lặp:

def tinh_tong_lap(n):
    """
    Tính tổng các số từ 1 đến n bằng phương pháp lặp.
    """
    tong = 0
    for i in range(1, n + 1):
        tong += i
    return tong

# Ví dụ:
print(tinh_tong_lap(5)) # Kết quả: 15

Tuy nhiên, ta có thể nhận thấy một quy luật khác:

S(n) = 1 + 2 + ... + (n-1) + n
S(n) = S(n-1) + n

Như vậy, để tính tổng đến n, ta có thể tính tổng đến n-1 rồi cộng thêm n. Đây là ý tưởng cốt lõi của đệ quy: giải quyết một bài toán bằng cách quy nó về một bài toán tương tự nhưng có quy mô nhỏ hơn.

3. Nguyên lý thuật toán

Đệ quy là một kỹ thuật lập trình trong đó một hàm tự gọi lại chính nó. Một thuật toán đệ quy phải bao gồm hai thành phần chính:

Trường hợp cơ sở (Base Case): Đây là điều kiện dừng của đệ quy. Nó là một hoặc nhiều trường hợp mà bài toán có thể được giải quyết trực tiếp mà không cần gọi đệ quy nữa. Nếu thiếu trường hợp cơ sở, hàm sẽ tự gọi chính nó một cách vô hạn, dẫn đến lỗi tràn bộ nhớ stack (Stack Overflow).
Bước đệ quy (Recursive Step): Đây là phần của hàm thực hiện việc phân rã bài toán lớn thành các bài toán con có quy mô nhỏ hơn và sau đó gọi lại chính nó để giải quyết các bài toán con đó.

3.1. Ý tưởng cốt lõi

Ý tưởng chính của đệ quy là một bài toán lớn có thể được định nghĩa thông qua một hoặc nhiều bài toán tương tự nhưng nhỏ hơn.

Với bài toán tính S(n):
- Trường hợp cơ sở: S(1) = 1. Đây là trường hợp đơn giản nhất, có thể trả về kết quả ngay lập tức.
- Bước đệ quy: S(n) = n + S(n-1) với n > 1.

3.2. Minh họa các bước thực thi

Xét ví dụ tính giai thừa của 4 (ký hiệu 4!), với định nghĩa:

n! = n * (n-1) * (n-2) * ... * 1
0! = 1 (quy ước)

Ta có thể định nghĩa đệ quy như sau:

Trường hợp cơ sở: giai_thua(0) = 1 hoặc giai_thua(1) = 1.
Bước đệ quy: giai_thua(n) = n * giai_thua(n-1).

Quá trình thực thi của giai_thua(4) diễn ra như sau:

giai_thua(4) được gọi. Vì 4 > 1, nó trả về 4 * giai_thua(3).
Để tính giai_thua(3), hàm được gọi lại. Vì 3 > 1, nó trả về 3 * giai_thua(2).
Để tính giai_thua(2), hàm được gọi lại. Vì 2 > 1, nó trả về 2 * giai_thua(1).
Để tính giai_thua(1), hàm được gọi lại. Lúc này, điều kiện cơ sở được thỏa mãn. Hàm trả về 1.
Kết quả 1 được trả về cho lời gọi ở bước 3. giai_thua(2) bây giờ có thể tính 2 * 1 = 2.
Kết quả 2 được trả về cho lời gọi ở bước 2. giai_thua(3) bây giờ có thể tính 3 * 2 = 6.
Kết quả 6 được trả về cho lời gọi ở bước 1. giai_thua(4) bây giờ có thể tính 4 * 6 = 24.
Kết quả cuối cùng là 24.

4. Cài đặt thuật toán

Dưới đây là cài đặt cho hai ví dụ kinh điển: Giai thừa và Dãy số Fibonacci.

4.1. Tính Giai thừa

def tinh_giai_thua(n):
    """
    Tính giai thừa của một số nguyên không âm n bằng đệ quy.
    """
    # Trường hợp cơ sở: Nếu n là 0 hoặc 1, giai thừa là 1.
    if n == 0 or n == 1:
        return 1
    # Bước đệ quy: n! = n * (n-1)!
    else:
        return n * tinh_giai_thua(n - 1)

# Ví dụ
ket_qua = tinh_giai_thua(5)
print(f"Giai thừa của 5 là: {ket_qua}") # Kết quả: 120

4.2. Dãy số Fibonacci

Dãy Fibonacci được định nghĩa: F(0) = 0, F(1) = 1, và F(n) = F(n-1) + F(n-2) với n > 1.

def fibonacci(n):
    """
    Tìm số Fibonacci thứ n bằng đệ quy.
    """
    # Trường hợp cơ sở: F(0) = 0 và F(1) = 1.
    if n <= 1:
        return n
    # Bước đệ quy: F(n) = F(n-1) + F(n-2)
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

# Ví dụ
ket_qua = fibonacci(7)
print(f"Số Fibonacci thứ 7 là: {ket_qua}") # Kết quả: 13

5. Trực quan hóa và gỡ lỗi với Thonny

Môi trường lập trình Thonny cung cấp một công cụ trực quan hóa mạnh mẽ là cửa sổ “Call Stack” (Ngăn xếp lời gọi). Công cụ này cho phép theo dõi các lời gọi hàm được xếp chồng lên nhau như thế nào trong quá trình thực thi đệ quy.

Cách thực hiện:

Mở Thonny và dán đoạn mã nguồn của hàm tinh_giai_thua.
Đi đến menu View và đảm bảo rằng Stack đã được chọn.
Chạy chương trình ở chế độ gỡ lỗi (debugger) bằng cách nhấn phím Ctrl + F5 hoặc vào menu Run -> Debug current script.
Sử dụng các nút Step into (F7) để đi qua từng bước thực thi.
Quan sát cửa sổ “Stack”. Mỗi khi hàm tinh_giai_thua tự gọi lại chính nó, một khung (frame) mới cho lời gọi đó sẽ được đẩy vào đỉnh của ngăn xếp. Khi một lời gọi hàm hoàn thành và trả về giá trị, khung tương ứng sẽ được lấy ra khỏi ngăn xếp.

Việc trực quan hóa này giúp làm rõ cơ chế “Last-In, First-Out” (Vào sau, Ra trước) của ngăn xếp lời gọi và giải thích tại sao các trường hợp cơ sở lại được giải quyết trước tiên.

6. Bài tập vận dụng

6.1. Đề bài

Viết một hàm đệ quy có tên tinh_tong_chu_so(n) để tính tổng các chữ số của một số nguyên dương n. Ví dụ: tinh_tong_chu_so(123) sẽ trả về 1 + 2 + 3 = 6.

6.2. Lời giải và phân tích

Phân tích thuật toán:
- Ý tưởng: Ta có thể tách số n thành hai phần: chữ số cuối cùng (n % 10) và phần còn lại của số (n // 10). Tổng các chữ số của n sẽ bằng chữ số cuối cùng cộng với tổng các chữ số của phần còn lại.
- Trường hợp cơ sở: Nếu n là một số có một chữ số (tức là n < 10), tổng các chữ số của nó chính là n.
- Bước đệ quy: tinh_tong_chu_so(n) = (n % 10) + tinh_tong_chu_so(n // 10).

Cài đặt:

def tinh_tong_chu_so(n):
    """
    Tính tổng các chữ số của một số nguyên dương n bằng đệ quy.
    """
    # Đảm bảo n là số không âm
    n = abs(n)
    
    # Trường hợp cơ sở: nếu n chỉ có một chữ số.
    if n < 10:
        return n
    # Bước đệ quy: tách chữ số cuối cùng và gọi đệ quy với phần còn lại.
    else:
        chu_so_cuoi = n % 10
        phan_con_lai = n // 10
        return chu_so_cuoi + tinh_tong_chu_so(phan_con_lai)

# Ví dụ
n = 12345
ket_qua = tinh_tong_chu_so(n)
print(f"Tổng các chữ số của {n} là: {ket_qua}") # Kết quả: 15

7. Đánh giá thuật toán và mở rộng

7.1. Phân tích độ phức tạp

Hàm tinh_giai_thua(n):
- Độ phức tạp thời gian: O(n). Hàm thực hiện n lời gọi đệ quy để đi từ n xuống 1.
- Độ phức tạp không gian: O(n). Mỗi lời gọi đệ quy chiếm một khoảng không gian trên ngăn xếp bộ nhớ. Độ sâu tối đa của ngăn xếp là n.
Hàm fibonacci(n) (cài đặt đệ quy thông thường):
- Độ phức tạp thời gian: O(2^n). Đây là một độ phức tạp rất lớn vì nhiều giá trị fibonacci(k) được tính toán lặp đi lặp lại nhiều lần.
- Độ phức tạp không gian: O(n). Độ sâu tối đa của chuỗi lời gọi đệ quy là n.

7.2. Các trường hợp đặc biệt và biến thể

Lỗi tràn bộ nhớ đệm (Stack Overflow): Nếu một hàm đệ quy có độ sâu quá lớn (ví dụ tinh_giai_thua(10000)), nó có thể làm đầy ngăn xếp lời gọi và gây ra lỗi. Trong những trường hợp này, giải pháp lặp (sử dụng vòng lặp) thường ưu việt hơn.
Đệ quy đuôi (Tail Recursion): Là một dạng đệ quy đặc biệt trong đó lời gọi đệ quy là hành động cuối cùng được thực hiện trong hàm. Một số ngôn ngữ lập trình có thể tối ưu hóa đệ quy đuôi để không làm tăng kích thước của stack, hiệu quả tương đương vòng lặp. Python hiện tại không hỗ trợ tối ưu hóa này.

8. Tổng kết

Đệ quy là một công cụ tư duy và lập trình mạnh mẽ, cho phép giải quyết các bài toán phức tạp một cách thanh lịch bằng cách chia chúng thành các bài toán con đơn giản hơn.

Các thành phần chính của một hàm đệ quy là trường hợp cơ sở để dừng quá trình và bước đệ quy để thu nhỏ quy mô bài toán.
Hiểu rõ cơ chế hoạt động của ngăn xếp lời gọi (call stack) là chìa khóa để nắm vững đệ quy.
Cần cẩn trọng với các vấn đề về hiệu năng và nguy cơ tràn bộ nhớ stack khi sử dụng đệ quy cho các bài toán có độ sâu lớn.