Kiến thức nền tảng đệ quy trong lập trình là phần khiến rất nhiều bạn mới vào nghề bị chững lại. Chúng tôi gặp câu hỏi này liên tục. Nghe giảng thì thấy hiểu, nhưng mở máy ra lại không biết bắt đầu từ đâu. Thật ra đệ quy không khó đến vậy. Vấn đề thường nằm ở cách giải thích quá khô khan và thiếu hình dung cụ thể. Trong bài này, đội ngũ Coding Guru sẽ đi từ những điều cơ bản nhất, dựa trên kinh nghiệm giảng dạy và làm việc thực tế của chúng tôi.
Vì sao nhiều người mới học thấy đệ quy khó hiểu?
Chúng tôi vẫn nhớ hồi mới vào nghề, có một bạn thực tập trong team hỏi thẳng: “Anh ơi, đệ quy để làm gì mà em đọc mãi vẫn không hiểu?”. Câu hỏi ấy khiến chúng tôi nhận ra một điều. Khi một hàm tự gọi chính nó, đầu óc người mới thường rối. Họ không nhìn thấy đâu là điểm dừng. Cảm giác lúng túng này rất bình thường, và nó không có nghĩa là bạn kém.
Thiếu nền tảng về đệ quy sẽ kéo theo khó khăn khi học các thuật toán nâng cao. Tìm kiếm nhị phân, duyệt cây hay sắp xếp nhanh đều dựa trên tư duy này. Nếu chưa nắm bản chất, bạn sẽ phải vật lộn với những bài toán phức tạp hơn nhiều. Vì vậy, hãy dành thời gian làm chắc khái niệm này ngay từ đầu. Đừng lướt qua cho xong.
Đệ quy là gì và hoạt động ra sao?
Đệ quy là kỹ thuật trong đó một hàm gọi lại chính nó ngay bên trong thân hàm. Bạn có thể hình dung như một bức tranh có chính bức tranh đó nằm ở góc. Mỗi lần gọi, hàm xử lý một phần nhỏ hơn của bài toán gốc. Quá trình này lặp lại cho đến khi gặp một trường hợp đặc biệt gọi là điều kiện cơ sở. Tại đó, hàm dừng việc gọi thêm và bắt đầu trả kết quả ngược lên trên.
Điều kiện dừng là phần sống còn của đệ quy. Thiếu nó, hàm sẽ gọi mãi không ngừng và cuối cùng gây lỗi tràn ngăn xếp (stack overflow). Chúng tôi từng gặp nhiều bạn mới viết hàm đệ quy rồi quên khai báo điều kiện dừng. Kết quả là chương trình treo hoặc crash ngay lập tức. Mỗi khi viết, hãy tự hỏi: khi nào hàm nên dừng? Trường hợp đơn giản nhất của bài toán trông như thế nào?
Hãy thử hình dung bạn đang tìm một cuốn sách trong chồng sách rất cao. Bạn lấy cuốn trên cùng ra xem. Không đúng thì đặt sang một bên và tiếp tục với cuốn kế tiếp. Việc “lấy sách ra xem” lặp lại cho đến khi bạn thấy cuốn cần tìm, hoặc hết sách. Đệ quy trong lập trình vận hành theo cách tương tự: một hành động nhỏ được lặp lại trên phần việc ngày càng nhỏ đi.
Ví dụ giai thừa để người mới làm theo
Để hiểu rõ hơn, chúng ta cùng xem bài toán kinh điển: tính giai thừa của số nguyên dương n, ký hiệu n!. Giai thừa của n là tích của mọi số từ 1 đến n. Ví dụ, 5! = 5 × 4 × 3 × 2 × 1 = 120.
Cách dễ nghĩ nhất là dùng vòng lặp:
def giai_thua(n):
ket_qua = 1
for i in range(1, n + 1):
ket_qua *= i
return ket_qua
Vòng lặp này nhân dồn từ 1 đến n, rất trực quan. Bây giờ, xem cùng bài toán viết bằng đệ quy:
def giai_thua(n):
if n == 1:
return 1
return n * giai_thua(n - 1)
Hàm này tự gọi chính nó với tham số nhỏ hơn là n – 1. Khi n bằng 1, hàm trả về 1 và dừng lại. Điều kiện dừng ở đây là n == 1. Nếu bạn bỏ dòng if n == 1, hàm sẽ chạy mãi và làm sập chương trình.
Khi gọi giai_thua(4), quá trình diễn ra như sau:
giai_thua(4)= 4 ×giai_thua(3)giai_thua(3)= 3 ×giai_thua(2)giai_thua(2)= 2 ×giai_thua(1)giai_thua(1)= 1
Sau đó, kết quả được tính ngược lên: 1 × 2 = 2, rồi 2 × 3 = 6, rồi 6 × 4 = 24. Đáp số cuối cùng là 24. Chúng tôi khuyên bạn nên tự gõ đoạn code này và thêm lệnh print ở đầu hàm để xem từng lần gọi. Chỉ cần làm một lần như vậy, khái niệm sẽ rõ hơn cả chục trang lý thuyết.
So sánh hai cách, vòng lặp đi từ 1 lên n, còn đệ quy đi từ n xuống 1 rồi quay ngược trở lại. Người mới thường thấy đệ quy khó vì phải tin rằng hàm sẽ tự lo phần còn lại. Khi đã quen, bạn sẽ thấy nó rất tự nhiên với những bài có cấu trúc lặp lại, như duyệt cây thư mục hay phân tích biểu thức. Nếu muốn ôn lại nền tảng trước khi đi tiếp, bạn có thể đọc thêm bài OOP là gì để hiểu cách tổ chức code theo đối tượng, vì hai tư duy này thường được học song song.
Chúng tôi hay khuyên người mới tập trung vào hai việc: tìm điều kiện dừng và xác định công thức truy hồi. Công thức truy hồi biểu diễn bài toán lớn thông qua bài toán nhỏ hơn. Với giai thừa, công thức là n! = n × (n – 1)!. Nắm được hai điều này, bạn có thể viết đệ quy cho rất nhiều bài toán khác.
Cần lưu ý thêm rằng đệ quy không phải lúc nào cũng tối ưu. Với giai thừa, vòng lặp nhanh hơn và tốn ít bộ nhớ hơn. Nhưng với duyệt cây, đệ quy thường là lựa chọn tự nhiên nhất. Hãy chọn theo bản chất bài toán, đừng cố dùng đệ quy chỉ vì nó trông có vẻ thông minh.
Lỗi thường gặp khi mới viết đệ quy
Từ kinh nghiệm review code của đội ngũ, có ba lỗi lặp đi lặp lại nhiều nhất. Lỗi đầu tiên là quên điều kiện dừng, như đã nhắc ở trên. Lỗi thứ hai là điều kiện dừng sai. Ví dụ bạn viết if n == 0 nhưng đầu vào lại là số âm, khiến hàm không bao giờ chạm tới đích. Lỗi thứ ba là truyền tham số không thu nhỏ bài toán, khiến hàm gọi lại đúng bài toán cũ. Mỗi khi gặp lỗi, hãy in giá trị tham số ở từng lần gọi. Cách đơn giản này giúp bạn thấy ngay chỗ hàm đi lạc.
Lời kết cho người mới bắt đầu
Hiểu đệ quy qua ví dụ đơn giản sẽ cho bạn nền tảng vững hơn khi gặp bài toán khó. Đừng nản nếu lần đầu chưa hiểu, vì chúng tôi cũng từng như vậy. Hãy thử tự viết lại hàm giai thừa, rồi chuyển sang dãy Fibonacci. Kinh nghiệm của chúng tôi là tự tay debug một hàm đệ quy sẽ giúp bạn hiểu sâu hơn bất kỳ lý thuyết nào. Nếu muốn mở rộng thêm kiến thức về một hệ sinh thái lập trình phổ biến, bạn có thể tham khảo bài .NET là gì. Chúc bạn học tốt!
