Tìm hiểu Hàm Đệ quy trong Python

Là một lập trình viên chuyên nghiệp, bạn cần nắm thật vững những nền tảng như biến, câu lệnh điều kiện, kiểu dữ liệu, phạm vi truy cập, lời gọi hàm, phạm vi (scope), v.v. Bất kể bạn đang viết chương trình gì — cho Middleware, cho Web Development hay Data Science — đây là những điều cơ bản mà bạn, với tư cách là lập trình viên, phải hiểu sâu. Trước hết bạn là lập trình viên, rồi sau đó mới là Nhà khoa học dữ liệu, Lập trình viên web, Kỹ sư Machine Learning, v.v.

Một khái niệm nền tảng như vậy là Đệ quy, và nó cực kỳ quan trọng khi bạn viết các hàm thuộc một số kiểu nhất định. Có thể bạn đã biết: "Gọi là Đệ quy khi một hàm tự gọi chính nó." Nhưng đằng sau hậu trường điều gì xảy ra? Bộ nhớ vật lý bị ảnh hưởng ra sao bởi đệ quy? Liệu bạn có thể biến mọi hàm khác thành hàm đệ quy không? Trong hướng dẫn này, bạn sẽ tìm lời giải cho những câu hỏi căn bản đó.

Cấu tạo của một hàm đệ quy:

Có thể bạn đã từng gặp thuật ngữ Đệ quy trong chương trình cử nhân Khoa học máy tính hay Công nghệ thông tin. Ở phần này, bạn sẽ ôn lại những khái niệm đó theo một cách thú vị. Bắt đầu nhé.

Hãy quay lại định nghĩa đệ quy: "Gọi là Đệ quy khi một hàm tự gọi chính nó". Lấy một ví dụ để minh họa định nghĩa này:

void A(n){
    if(n>=1){
        A(n-1);
        print(n);
    }
}
Được hỗ trợ bởi

Bạn có thể thấy hàm A() tự gọi chính nó. Đây là một ví dụ về đệ quy, và A() là một hàm đệ quy.

Giờ hãy học một vài điều cơ bản về hàm đệ quy.

Những điều cơ bản của một hàm đệ quy:

Một hàm đệ quy phải có hai thuộc tính sau:

Mối quan hệ truy hồi (recurrence relation)
Điều kiện dừng (termination condition)

Xét đoạn mã trên để hiểu các điểm này. Rõ ràng, hàm có một quan hệ truy hồi cụ thể:

$n\le 1$ là điều kiện dừng / điểm neo / điều kiện cơ sở, và nếu thỏa thì đệ quy dừng lại. Việc chỉ rõ điều kiện này là bắt buộc. Nếu không, hàm sẽ rơi vào một vòng lặp vô hạn.

(Lưu ý: đoạn mã trên không theo một ngôn ngữ lập trình cụ thể nào. Mục đích chính là minh họa một ví dụ về hàm đệ quy.)

Có thể bạn đang nghĩ: tại sao lại viết hàm đệ quy nếu có những cách khác tốt hơn? Đúng là đôi khi việc lần theo đệ quy khá khó, nhưng khi quen thực hành, bạn sẽ thấy đệ quy rất đẹp ở khía cạnh dễ đọc và biến số gọn gàng. Đệ quy không cần biến bổ sung để chạy, nhưng cần một điều kiện dừng đúng để kết thúc. Thường thì khó tìm ra điều kiện dừng cho một đệ quy. Một lần nữa, "Có công mài sắt, có ngày nên kim". Ở phần sau, bạn sẽ thấy một chương trình có thể đẹp và ngắn thế nào nếu dùng đệ quy thay cho cách thông thường. Bây giờ, bạn sẽ đi tiếp đến phần biểu diễn bộ nhớ của một hàm đệ quy.

Biểu diễn bộ nhớ của một hàm đệ quy:

Trong phần này, bạn sẽ học cách các hàm đệ quy được biểu diễn về mặt cơ bản trên bộ nhớ bằng cây và ngăn xếp (stack). Hãy xét hàm đệ quy A() sau để hiểu điều này:

void A(n){
    if(n>=1){
        A(n-1);
        print(n);
    }
}
Được hỗ trợ bởi

Trước hết, bạn sẽ hiểu biểu diễn bộ nhớ bằng cây. Nghe có vẻ khó, nhưng thực ra rất đơn giản. Nếu bạn ghi lại mỗi lần gọi hàm theo dạng cây, nó sẽ trông như thế nào?

Gần như hình sau?

Một vài điểm cần lưu ý:

Hàm được gọi với A(3) và vì thế có 4 (3+1) lần gọi hàm ở đây. Tổng quát, nếu gọi A(n) thì tổng số lần gọi hàm sẽ là (n+1).
Các lời gọi P() là các lệnh in ra do print(n) tạo ra.
Hàm dừng ở lời gọi A(0) vì câu lệnh if (sau lời gọi A(0)) sẽ nhận n < 1 khiến hàm kết thúc.

Bạn thấy biểu diễn dạng cây trước vì để biểu diễn hàm đệ quy trên ngăn xếp, cần có biểu diễn này. Giờ bạn sẽ thấy điều đó.

(Stack là một cấu trúc dữ liệu tuân theo thứ tự vào sau ra trước — LIFO)

Với biểu diễn bằng stack, bạn sẽ cần duyệt cây theo thứ tự từ trên xuống và trái sang phải. Hình sau sẽ làm rõ.

Diễn giải cây trông có vẻ kỳ lạ này. Hãy nhớ rằng một stack có hai thao tác — 1. Push để đưa phần tử vào stack & 2. Pop để lấy phần tử ra khỏi stack.

Bây giờ, bạn bắt đầu duyệt cây theo thứ tự từ trên xuống và trái sang phải:

Bất cứ khi nào gặp một lần gọi hàm, bạn sẽ push nó vào stack.
Nếu gặp lời gọi print()/P(), bạn chỉ việc in phần tử tương ứng theo thứ tự gặp.

Sau đây là các phần tử của stack thu được khi duyệt cây từ A(3) đến A(0) chỉ theo chiều từ trên xuống:

Giờ bạn bắt đầu nửa còn lại của quá trình duyệt cây, tức là theo thứ tự trái sang phải. Bất cứ khi nào bạn thấy một lời gọi hàm lần thứ hai, bạn sẽ pop nó. Thật bất ngờ, phần tử đầu tiên của stack (A(0)) được pop ra lại là phần tử vào stack cuối cùng (LIFO, nhớ chứ?). Trên đường đi bạn sẽ gặp ba lời gọi P() — P(1), P(2) và P(3). Bạn sẽ in chúng theo đúng thứ tự xuất hiện trong quá trình duyệt. Thứ tự sẽ là:

1 2 3

Cuối cùng, khi kết thúc quá trình duyệt, stack sẽ rỗng hoàn toàn. Để hiểu thao tác pop rõ hơn, dưới đây là hình của stack sau khi đã pop hết.

Bạn đã thấy cách biểu diễn một hàm đệ quy đơn giản lên bộ nhớ bằng cây và stack. Bây giờ, bạn sẽ học cách lần theo một đệ quy.

Lần theo một đệ quy:

Ở phần này, bạn sẽ học cách lần theo một đệ quy một cách có phương pháp. Xét hàm đệ quy sau:

void A(n){
    if(n>0){
        print(n-1);
        A(n-1);
    }
}
Được hỗ trợ bởi

Một điểm then chốt ở đây là bất cứ khi nào một hàm được gọi, một activation record (bản ghi kích hoạt) sẽ được tạo trong bộ nhớ, chứa các biến cục bộ của hàm đó và một con trỏ lệnh (instruction pointer, biểu thị tác vụ tiếp theo sẽ thực thi khi việc gọi quay trở lại hàm). Giả sử một hàm tên main() gọi hàm A() ở trên như A(3). Hãy đánh số các dòng của A() từ câu lệnh if để dễ hiểu hơn:

void A(n){
    1. if(n>0)
    2. {
        3. print(n-1);
        4. A(n-1);
    5. }
}
Được hỗ trợ bởi

Các activation record sẽ trông như sau:

Như đã đề cập, các hàm có bản sao biến cục bộ và con trỏ lệnh của riêng mình (trong trường hợp này là số dòng). Sau A(0) hàm A() sẽ kết thúc và bắt đầu pop. Lưu ý rằng ở đây dùng một stack nằm ngang, chính xác giống với các stack bạn đã thấy trước đó trong hướng dẫn. Khi các bản ghi được push vào stack, việc in cũng sẽ diễn ra và các phần tử sau sẽ được in ra:

2 1 0

Con trỏ lệnh rất quan trọng ở đây vì thường trong một hàm đệ quy, điều khiển quay về cùng một hàm nhưng với giá trị biến khác. Để giữ mọi thứ đồng bộ, các con trỏ này thực sự hữu ích. Bạn có thể làm theo đúng quy trình này để lần theo một đệ quy bằng biểu diễn cây.

Giờ bạn sẽ học cách thực hiện phân tích thời gian-không gian cho một hàm đệ quy.

Phân tích thời gian - không gian của một hàm đệ quy:

DataCamp có một bài viết xuất sắc về Phân tích tiệm cận trong Python, và khuyến nghị bạn xem qua trước khi đọc phần này. Hãy điểm lại nhanh ý nghĩa của phân tích thời gian và không gian của một hàm (còn gọi là độ phức tạp không gian và độ phức tạp thời gian):

Với một đầu vào cho trước, một hàm dự kiến tạo ra một đầu ra nào đó. Để làm được điều đó, hàm mất bao nhiêu thời gian? Thước đo độ phức tạp thời gian ước lượng thời gian này, còn gọi là thời gian chạy của hàm. Tương tự, thước đo độ phức tạp không gian ước lượng nhu cầu không gian (bộ nhớ) của một hàm, tức là cho một đầu vào cho trước. Nhưng tại sao cần những thứ này?

Thay vì chạy hàm trên dải đầu vào với kích thước khác nhau, bạn có thể dễ dàng ước lượng hàm sẽ cư xử thế nào với các đầu vào có kích thước khác nhau.
Nếu bạn có hai hàm cùng đạt một mục tiêu, bạn sẽ chọn hàm nào? Bạn sẽ dựa vào thước đo nào để quyết định? Đúng vậy. Bạn sẽ so sánh bằng cách phân tích độ phức tạp không gian và thời gian của chúng và xem hàm nào hiệu quả hơn.

Giờ hãy lấy một hàm đệ quy đơn giản và phân tích độ phức tạp thời gian và không gian của nó.

void A(n){
    if(n>1) // Anchor condition
    {
       return A(n-1);
    }
}
Được hỗ trợ bởi

Hãy phân tích độ phức tạp thời gian trước. Giả sử tổng thời gian mà hàm A() ở trên tiêu tốn là $T(n)$. Khi đó $T(n)$ là tổng của thời gian so sánh n có lớn hơn 1 hay không và thời gian thực thi A(n-1). Vậy $T(n)$ có thể biểu diễn như sau -

$T(n)$ = 1 + $T(n-1)$

1 là thời gian cho phép so sánh (bạn có thể đặt bất kỳ hằng số nào ở đó). Vậy thời gian (theo $T(n)$) để thực thi A(n-1) là bao nhiêu?

$T(n-1)$ = 1 + $T(n-2)$

Tương tự,

$T(n-2)$ = 1 + $T(n-3)$

và cứ thế.

Nếu để ý kỹ các phương trình, chúng đều liên kết với nhau. Đúng chứ? Nếu bạn thế chúng nối tiếp nhau, bạn được -

$T(n)$ = 1 + (1 + $T(n-2)$) = 2 + $T(n-2)$ = 3 + $T(n-3)$ = .... = k + $T(n-k)$ (sau khi chạy hàm trong k bước)

Giờ bạn cần xác định tại điểm nào hàm sẽ dừng. Theo điều kiện neo đã cho, bạn có thể viết -

Giả sử sau khi chạy k bước, hàm dừng. Khi đó, phải có -

$n - k = 1 => k = n - 1$

Bây giờ thay giá trị k (= n - 1) vào $T(n) = k + T(n-k)$:

$T(n) = (n-1) + T(n-(n-1))$
$=> T(n) = (n-1) + T(1)$
$=> T(n) = n-1 + 1 = n$ // Với T(1) chỉ cần phép so sánh

Theo quy tắc của phân tích tiệm cận, $T(n) = n$ có thể viết lại thành $T(n) = \mathcal{O}(n)$. Điều này có nghĩa độ phức tạp thời gian (trong trường hợp xấu nhất) của hàm là $\mathcal{O}(n)$.

Bạn có thể muốn chậm lại một chút và quan sát kỹ từng bước của quá trình này. Rất khuyến khích bạn làm điều này trên giấy bút để hiểu rõ từng phần.

Phân tích độ phức tạp không gian của hàm thì đơn giản. Hàm là một hàm trong bộ nhớ và không sử dụng biến bổ sung nào. Vì vậy, bạn có thể kết luận rằng độ phức tạp không gian của hàm là $\mathcal{O}(n)$.

Giờ bạn sẽ ghép tất cả lại và triển khai một hàm đệ quy đơn giản trong Python.

Triển khai một hàm đệ quy đơn giản trong Python:

Bạn sẽ viết một hàm đệ quy để tìm giai thừa của một số cho trước. Sau đó bạn sẽ viết phiên bản lặp của cùng hàm đó. Bắt đầu nhé.

# Recursive function factorial_recursion()

def factorial_recursion(n):  
   if n == 1:  
       return n  
   else:  
       return n*factorial_recursion(n-1)
Được hỗ trợ bởi

# Call the function

num = 7
print("The factorial of ",num," is ",factorial_recursion(num))
Được hỗ trợ bởi

The factorial of  7  is  5040
Được hỗ trợ bởi

Nhớ hai thành phần then chốt để viết một hàm đệ quy chứ?

Quan hệ truy hồi
Điều kiện dừng

Trong trường hợp này, quan hệ truy hồi có thể là -

$f(n) = n!$
$f(n) = n * f(n-1)$ và cứ thế.

Điều kiện dừng là khi n bằng 1.

Đơn giản, đúng không?

Giờ bạn sẽ triển khai phiên bản lặp của cùng hàm đó.

def factorial_iterative(num):
    factorial = 1
    if num < 0:
        print("Sorry, factorial does not exist for negative numbers")
    elif num == 0:
        print("The factorial of 0 is 1")
    else:
        for i in range(1,num + 1):
           factorial = factorial*i
        print("The factorial of",num,"is",factorial)
Được hỗ trợ bởi

factorial_iterative(7)
Được hỗ trợ bởi

The factorial of 7 is 5040
Được hỗ trợ bởi

Bạn có thể dễ dàng thấy sự khác biệt giữa hai phiên bản. Phiên bản đệ quy đẹp hơn rất nhiều so với phiên bản lặp. Đúng không?

Chúc mừng!

Bạn đã đi đến cuối cùng. Trong hướng dẫn này, bạn đã nghiên cứu sâu về các hàm đệ quy. Từ những điều cơ bản nhất đến phân tích độ phức tạp thời gian và không gian của một hàm đệ quy, bạn đã bao quát tất cả. Bạn cũng đã thấy đệ quy có thể hữu ích như thế nào để giải các bài toán có đặc trưng phù hợp. Giờ đây, bạn nên có khả năng giải các bài toán (có quan hệ truy hồi và điều kiện dừng) bằng đệ quy. Bạn có thể thử giải bài toán tìm các Số Fibonacci trong một phạm vi bằng đệ quy.

Tôi khuyến khích bạn giải một số bài toán kinh điển như Tìm kiếm nhị phân, Merge Sort, Tháp Hà Nội, v.v. bằng đệ quy và thực hiện phân tích thời gian-không gian. Điều này chắc chắn sẽ giúp bạn trở thành một lập trình viên giỏi hơn.

Ở mức độ nhập môn, những gì bạn đã học là đủ. Nhưng nếu muốn học thêm về đệ quy, hãy xem các liên kết sau:

Nếu bạn muốn học thêm về Python, hãy tham gia khóa miễn phí Intro to Python for Data Science của DataCamp.

Chủ đề

Python Khoa học Dữ liệu Phân tích dữ liệu

Chủ đề

Công nghệ

Tìm hiểu Hàm Đệ quy trong Python

Khám phá cùng AI

Cấu tạo của một hàm đệ quy:

Những điều cơ bản của một hàm đệ quy:

Biểu diễn bộ nhớ của một hàm đệ quy:

Lần theo một đệ quy:

Phân tích thời gian - không gian của một hàm đệ quy:

Triển khai một hàm đệ quy đơn giản trong Python:

Chủ đề

Tìm hiểu thêm về Python

Nhập môn Khoa học Dữ liệu với Python

Nhập môn Python

Python nâng cao

Liên quan

Claude Opus 4.6: Tính năng, Điểm chuẩn, Bài kiểm tra thực hành và hơn thế nữa

Chủ đề

Công nghệ

Tìm hiểu thêm về Python

Nhập môn Khoa học Dữ liệu với Python

Nhập môn Python

Python nâng cao