Đây là một quyển sách toán lớp 3, ở trong bìa sách có ba học sinh, trong đó có một học sinh lại cầm một quyển sách toán lớp ba khác. Và trong quyển sách đó lại có ba học sinh, và cũng có một học sinh cầm một quyển sách lớp 3. Đây chính là ví dụ cho một khái niệm rất căn bản trong bất kỳ ngôn ngữ lập trình nào – khái niệm “đệ quy”.
Đang xem: Một Ví Dụ Đơn Giản Giải Thích Hàm Đệ Quy Là Gì
Đệ quy là gì ?
Đệ quy có nghĩa là một hàm tự gọi lại chính nó.
Ví dụ:
void hello(int count){ count++; if (count
Thành phần của một hàm đệ quy.
Một hàm đệ quy gồm 2 phần:
Phần cơ sở: Điều kiện để thoát khỏi đệ quy. Nếu như không có phần này, hàm đệ quy sẽ thực hiện mãi mãi gây ra tràn bộ nhớ Stack.Phần đệ quy: Thân hàm có chứa phần gọi đệ quy, thực hiện cho đến khi thỏa mãn điều kiện ở phần cơ sở.
Ví dụ:
void hello(int count){ count++; if (count Như ví dụ trên, nếu chúng ta không cài đặt điều kiện dừng thì chương trình sẽ chạy mãi mãi.
Bộ nhớ Stack.
Nguyên tắc hoạt động của bộ nhớ Stack là LIFO (Last in – First out hay còn gọi là vào sau – ra trước ). Khi một biến được khai báo trong hàm, nó sẽ được đẩy vào Stack, khi hàm đó kết thúc thì tất cả những biến đó sẽ được đẩy ra, giải phóng khỏi Stack. Hình dưới là minh họa cách hoạt động của bộ nhớ Stack.
Ưu điểm:
Thuận lợi cho việc biểu diễn bài toán, như ở ví dụ trên, nhìn vào hàm là chúng ta có thể thấy ngay nó biểu diễn dãy số fibonacci, hay tính giai thừa.
Xem thêm: Nghĩa Của Từ Cưa Sừng Làm Nghé Là Gì, Vietgle Tra Từ
Nhược điểm:
Tốn nhiều bộ nhớ, nếu không phần cơ sở ( điểm dừng) thì sẽ gây ra việc tràn bộ nhớ stack. Bên cạnh đó việc sử dụng đệ quy tốn nhiều thời gian hơn vòng lặp.
Các ví dụ.
Tính tổng các số từ 1 đến n.
#include int sum(int n){ if(n == 0) // điều kiện dừng (phần cơ sở) return 0; return n + sum(n-1);} int main(){ int sum = sum(5); printf(“Sum = %d”, sum);}Kết quả.
Giải thích hàm đệ quy
Với n = 5
#include int fibonacci(int n){ if ((n == 1) || (n == 2)) return 1; return fibonacci(n-1) + fibonacci(n-2);}int main(){ printf(“%d”, fibonacci(30));}Kết quả.
Tính giai thừa
#include int factorial(int n){ if (n == 1) return 1; else return factorial(n-1)*n;}int main(){ printf(“%d”, factorial(5));}Kết quả.
Tạm kết
Đệ quy là một phương pháp cơ bản trong kỹ thuật lập trình. Trong lập trình Web hay Winform thường thì không sử dụng đệ quy nhưng nên học kỹ thuật này, vì nó không quá khó để nắm bắt. Việc sử dụng đệ quy vào các bài toán thì nên cân nhắc, mặc dù đệ quy khiến code chúng ta dễ đọc, nhưng rất khó cho việc debug.
Trên đây là khái niệm về đệ quy, hy vọng giúp ích cho mọi người mới tìm hiểu về kỹ thuật này, nếu có câu hỏi hay góp ý gì thì hãy bình luận ở bên dưới nhé. Chúc mọi người học tốt.