Đệ quy là gì? Đây là thắc mắc của hầu hết những ai đang theo học lập trình. Hàm Đệ quy được ứng dụng rất phổ biến trong lập trình giúp giải quyết nhiều bài toán khó, mang đến hiệu quả cao, tiết kiệm được các code phức tạp. Bài viết sau đây sẽ cung cấp cho bạn đọc những thông tin cơ bản nhất về phương pháp đệ quy cũng như những sai lầm nhiều người thường mắc phải khi sử dụng loại hàm này.
Đệ quy là gì?
Đệ quy là một loại hàm được sử dụng trong lập trình để giải quyết các vấn đề bằng cách, sử dụng một ví dụ đơn giản hơn của chính vấn đề đó.
Trái ngược với vòng lặp là cố gắng xây dựng một giải pháp, hàm đệ quy nhằm mục đích chia một vấn đề thành dạng cơ bản nhất của nó.
Ví dụ: Khi bạn đặt 2 chiếc gương giống y như nhau đối diện nhau (gương A và gương B). Khi nhìn vào mặt gương A ta sẽ thấy bóng phản chiếu của tấm gương B sẽ nhỏ hơn kích thước thật.
Nhưng trên mặt của tấm gương B lại đang phản chiếu ảnh của gương A nên khi mặt tấm gương B bị phản chiếu trong A thì có thể nhìn thấy bóng của A trong bóng của B (bóng của A lại bị thu nhỏ hơn bóng của gương B).
Quá trình này cứ lặp đi lặp lại cho đến khi mắt người không nhìn thấy được. Người ta gọi là ảnh trong ảnh
Đệ quy chỉ đơn giản là một công cụ để giải quyết một bài toán. Bất kỳ bài toán nào có thể được giải quyết bằng hàm đệ quy hoặc giải quyết bằng vòng lặp.
Đệ quy trong C++ là gì?
Hàm đệ quy trong lập trình là phương pháp dùng hàm để gọi lại chính nó. Trong quá trình giải thuật toán, một hàm lại có thể gọi lại chính tên hàm đó để tiếp tục giải dựa trên dữ liệu đã khai báo trước đó.
Ưu và nhược điểm của hàm đệ quy
- Ưu điểm: Làm một hàm từ phức tạp trở nên đơn giản hơn bằng cách giải từng phần nhỏ.
- Hạn chế: Thời gian làm bài sẽ không được tối ưu vì phải giải nhiều bài hơn. Thậm chí còn rất tốn bộ nhớ nếu phải chia nhỏ quá nhiều lần.
Phân loại đệ quy
Đệ quy trực tiếp là phương pháp đệ quy dùng 1 hàm để tự gọi lại chính nó.
Đệ quy gián tiếp là phương pháp đệ quy dùng 1 hàm X lời gọi đến hàm Y mà hàm Y lại chứa lời gọi đến chính hàm X.
Đệ quy đuôi và đệ quy đầu
Đệ quy đuôi khác gì đệ quy đầu?
Chúng ta gọi là đệ quy đuôi khi hàm đệ quy được đặt ở cuối, sau khi chương trình chạy qua điều kiện dừng. Còn lại thì ta gọi là đệ quy đầu.
Với phương thức đệ quy đuôi, hàm đệ quy sẽ được chương trình ưu tiên xử lý dứt điểm. Chương trình sẽ không phải chạy nhiều vòng để xử lý điều kiện như phương thức đệ quy đầu, nên theo logic sẽ giảm được nguy cơ tràn bộ nhớ Stack
So sánh giữa hàm đệ quy và vòng lặp
Ưu điểm lớn nhất của phép đệ quy là tiếp cận để xử lý vấn đề bằng những đoạn code sạch, gọn gàng, dễ hiểu.
Nhược điểm rõ ràng của hàm đệ quy là nguy cơ cao tràn bộ nhớ Stack như đã giải thích ở trên.
Cùng giải quyết một bài toán nhưng có một phương án khác để thay thế đệ quy là sử dụng vòng lặp.
Dù vòng lặp có ưu điểm là chỉ có một vòng duy nhất và ta sẽ không phải lo nghĩ gì về vấn đề tràn bộ nhớ Stack. Nhưng vòng lặp cũng có một nhược điểm so với hàm đệ quy là code xử lý sẽ viết dài và phức tạp hơn.
Xem thêm: Ebook là gì? Ebook mang đến những lợi ích gì trong học tập và giải trí?
Dãy Fibonacci và đệ quy
Dãy Fibonacci là dãy vô hạn các số tự nhiên được bắt đầu bằng hai phần tử là 0 và 1, dãy được thiết lập theo quy tắc mỗi phần tử luôn bằng tổng 2 phần tử trước nó, ta có dãy Fibonacci sau: 0 1 1 2 3 5 8 13 21 34 55 …
| Dãy số Fibonacci | 0 | 1 | 1 | 2 | 3 | 5 | 8 | … | … |
| Số thứ tự | 1 | 2 | 3 | 4 | 5 | 6 | 7 | … | n |
Tìm số Fibonacci tương ứng với số thứ tự n, để sử dụng hàm đệ quy tìm được số Fibonacci tương ứng, ta cần xác định quy luật và điều kiện dừng trước của dãy số Fibonacci.
- Quy luật, số n chính là tổng của hai chữ số đứng sau nó là (n-2) + (n-1).
- Chắc chắn rằng n1 = 0 và n2= 1 là điều kiện dừng của dãy số.
- Như vậy, ta sẽ chia thành 2 trường hợp và thực hiện phương pháp đệ quy như sau:
public int fibonacci(int n) {if (n <= 1) {return n;}return fibonacci(n-1) + fibonacci(n-2);}
Biểu diễn số thập phân dưới dạng nhị phân với hàm đệ quy
Thử đặt ra đề bài với tình huống khi bạn muốn chuyển một số từ dạng thập phân n sang dạng nhị phân, tương tự như các bước bên trên ta thực hiện:
Xác định được quy luật chuyển đổi từ số thập phân sang hệ nhị phân là chia số n cho 2, giữ lại phần dư (là 0 hoặc 1), tiếp tục lấy thương chia cho 2, đến khi trở về trường hợp 1 chia cho 2 (0 dư 1).
Xác định điều kiện dừng của quy luật là khi số n = 0, ta có 0 chia 2 vẫn bằng 0 và n = 1, 1 chia 2 bằng 0 dư 1.
Như vậy ta chia ra làm 2 trường hợp để thực hiện phép đệ quy như sau:
public String toBinary(int n) {if (n <= 1 ) { return String.valueOf(n);} return toBinary(n / 2) + String.valueOf(n % 2);}
Sai lầm khi viết thuật toán đệ quy
Một sai lầm phổ biến mà mọi người thường mắc phải khi cố gắng viết một thuật toán đệ quy để giải quyết vấn đề là cố gắng suy nghĩ về cách chia nhỏ vấn đề cho đến khi gặp đến trường hợp cơ sở (trường hợp cuối cùng để kết thúc vòng lặp). Thay vào đó, chúng ta nên tập trung vào vấn đề đơn giản hơn một mức so với vấn đề mà chúng ta đang cố tìm cách giải quyết. Và sau đó, chúng ta viết thuật toán đệ quy để xử lý vấn đề này.
Có thể nói, đệ quy chính là một trong những phương pháp cơ bản và quan trọng trong kỹ thuật lập trình. Đối với những ai đang theo học lập trình, cần tìm hiểu kỹ về hàm đệ quy để giải quyết các bài toán khó. Tuy nhiên, bạn cũng nên cân nhắc vì đệ quy giúp bạn dễ đọc code nhưng lại khó debug. Hy vọng những thông tin trên đây đã giúp bạn hiểu được đệ quy là gì cũng như ứng dụng loại hàm này trong thực tế tốt nhất nhé!
