Đệ quy là một khái niệm căn bản mà chúng ta cần hiểu rõ khi bắt đầu làm quen với lập trình. Vậy đệ quy là gì? Dưới đây là toàn bộ kiến thức về đệ quy mà supperclean.vn tồng hợp, hy vọng sẽ thật hữu ích với bạn đọc!
Contents
Đệ quy là gì?
Đệ quy được hiểu là sự vật được định nghĩa theo chính nó hoặc thuộc loại của nó. Hình minh họa về bìa cuốn sách Toán lớp 3 dưới đây là một ví dụ về đệ quy. Đó là hình ảnh bạn nữ cầm cuốn sách Toán lớp 3.
Hoặc khi bạn đạt hai chiếc gương giống hệt nhau và đối diện nhau. Khi nhìn vào gương thứ nhất, bạn sẽ thấy bóng phản chiếu của tấm gương thứ hai có kích thước nhỏ hơn kích thước thật. Ngược lại, khi nhìn vào tấm gương thứ hai, bạn sẽ thấy bóng phản chiếu của tấm gương thứ nhất trong gương thứ hai.
Trong tin học, đệ quy là việc một hàm tự gọi lại chính nó.
Phân loại đệ quy
Trong C++, Java, Python,… và lập trình nói chung, đệ quy được chia thành 6 loại như sau:
- Đệ quy tuyến tính (còn gọi là đệ quy đơn)
- Đệ quy nhị phân
- Đệ quy đuôi
- Đệ quy đa tuyến
- Đệ quy lồng
- Đệ quy hỗ trợ (tương hỗ)
Mặc dù có nhiều loại khác nhau nhưng bản chất của hàm đệ quy vẫn được giữ nguyên. Điểm khác biệt chủ yếu là số lượng lời gọi đệ quy hoặc vị trí của lời gọi. Ví dụ như đệ quy tuyến tính chỉ có duy nhất một lời gọi chính nó bên trong thân hàm. Trong khi đó, đệ quy nhị phân sẽ gọi lại chính hàm đó 2 lần.
Thành phần cấu tạo hàm đệ quy là gì?
Hàm đệ quy gồm có 2 thành phần chính, đó là:
- Phần cơ sở: Đây là điều kiện để chương trình thoát khỏi đệ quy. Nếu như không có phần cơ sở thì hàm sẽ thực hiện liên tục, không dừng lại, làm tràn bộ nhớ.
- Phần đệ quy: Hay còn gọi là thân hàm, là các câu lệnh để xử lý trong hàm. Nó sẽ thực hiện cho đến khi thỏa mãn điều kiện ở phần cơ sở thì dừng lại.
Ví dụ minh họa về hàm đệ quy trong lập trình
Để bạn đọc hiểu rõ hơn về thuật toán đệ quy là gì trong lập trình, chúng ta cùng tham khảo đoạn code tính n! bằng đệ quy dưới đây:
Khi bắt đầu, máy tính sẽ lưu các hàm cần tính vào bộ nhớ. Để thuận tiện theo dõi thì factorial (n) được viết tắt là f(n).
Với n = 5 thì hệ thống sẽ xử lý hàm f(5). Trong câu lệnh đầu tiên, do n#0 nên câu lệnh không được thực hiện.
Tiếp theo, để chạy lệnh return, máy tính cần giá trị n và factorial(n-1). Vì vậy, hệ thống sẽ tính giá trị của f(4). Lúc đó, f(5) được đẩy vào hàng chờ của bộ nhớ stack.
Với n = 4, hệ thống sẽ thực hiện quá trình tương tự như f(5). f(4) được đẩy vào stack và máy tính đi tính giá trị f(3). Với n = 1, 2, 3 cũng tương tự như vậy.
Khi n = 0, trạng thái sẽ hiển thị như dưới hình minh họa. Với n = 0 thì câu lệnh đầu tiên đúng nên f0) trả về kết quả là 1 và thoát.
Sau đó, máy tính sẽ lấy hàm trên đỉnh trong hàng chờ (cụ thể là f(1)) để tiếp tục xử lý. Trước khi đưa vào stack, hàm dừng ở đâu sẽ xử lý ở đó. Với f(1), do hàm dừng ở câu lệnh return nên sẽ thực hiện bắt đầu từ câu lệnh này.
Sau khi xử lý f(1), máy tính sẽ tiếp tục xử lý hàm ở đỉnh stack cho đến khi stack rỗng thì đệ quy kết thúc.
Ưu và nhược điểm của hàm đệ quy là gì?
Về ưu điểm
Ưu điểm của hàm đệ quy là giúp chia bài toán lớn thành các bài toán nhỏ hơn. Điều này rất thuận tiện cho quá trình tính toán. Đồng thời, không phải dùng nhiều hàm phức tạp, phù hợp với những bạn mới bắt đầu làm quen với lập trình.
Về nhược điểm
- Tốn nhiều không gian bộ nhớ
- Tốn nhiều thời gian xử lý
- Gặp nhiều khó khăn khi debug
- Nếu xác định sai điều kiện cơ sở có thể gây ra vòng lặp vô hạn, không có điểm dừng.
Các ứng dụng của hàm đệ quy
Đệ quy được sử dụng rộng rãi trong ngành khoa học máy tính với các ứng dụng phổ biến như:
- Thuật toán tìm kiếm và sắp xếp: Ví dụ như tìm kiếm nhị phân, sắp xếp trộn, sắp xếp nhanh,…
- Thuật toán trên cây và đồ thị: Ví dụ như BFS, DFS, tìm kiếm quãng đường đi ngắn nhất,…
- Đệ quy còn được ứng dụng để giải toán rời rạc
Giải thuật đệ quy là gì?
Giải thuật đệ quy là việc phân tách bài toán lớn thành những bài toán nhỏ và dễ giải hơn. Sau đó, tìm cách kết hợp giải những bài toán nhỏ, tạo thành lời giải cho bài toán lớn ban đầu.
Giải thuật toán đệ quy và toán quy nạp có mối quan hệ khăng khít với nhau. Ở toán quy nạp, người ta sẽ chứng minh tính chất toán học dựa vào cách chứng minh nó đúng với một số trường hợp rồi chứng minh nó đúng với mọi trường hợp. Tương tự vậy, khi giải thuật toán đệ quy, chúng ta sẽ đi tìm lời giải cho bài toán cơ sở trước rồi suy ra lời giải cho bài toán lớn.
Khử đệ quy là gì?
Khử đệ quy là việc thay thế các thuật toán đệ quy bằng các thuật toán không đệ quy để giảm tiêu tốn không gian bộ nhớ và thời gian xử lý. Tuy nhiên, không phải lúc nào việc khử đệ quy cũng dễ dàng. Vì vậy, trong một vài trường hợp bắt buộc phải sử dụng thuật toán đệ quy.
XEM THÊM:
Hy vọng với những chia sẻ trên sẽ giúp bạn đọc phần nào hiểu rõ đệ quy là gì. Mọi câu hỏi thắc mắc hoặc góp ý về bài viết vui lòng để lại bình luận bên dưới, supperclean.vn luôn sẵn sàng đón nhận!
