DANH SÁCH BÀI VIẾT Tìm hiểu thuật toán Quy hoạch động Tìm hiểu về Hàm đệ quy Thuật toán tìm kiếm nhị Tìm hiểu về Thuật toán quay lui (Backtracking) Tìm hiểu thuật toán Loang Tìm hiểu thuật toán chia để trị Tìm hiểu thuật toán tham lam trong lập trình Giải thuật tìm kiếm theo chiều sâu DFS (Depth First Search) Giải thuật tìm kiếm theo chiều rộng BFS (Breadth-first search) Tìm hiểu về thuật toán Sàng nguyên tố (sàng Eratosthenes)
Đệ quy là một trong số các thuật toán căn bản trong lập trình, thuật toán này chúng ta sẽ rất thường xuyên gặp phải và áp dụng rất nhiều!
Vậy chúng ta sẽ cùng nhau tìm hiểu về hàm đệ quy là gì? Cơ chế hoạt động của nó như thế nào? Và làm một vài ví dụ biểu diễn trong ngôn ngữ lập trình C++ trong bài viết này nhé.
Hàm đệ quy là gì?
Một hàm được gọi là hàm đệ quy nếu trong thân hàm có một hoặc nhiều lệnh gọi đến chính hàm đó.
Bạn hãy nhìn xuống bức ảnh dưới đây và hình dung một chút.
Bạn có thể thấy điều gì đặc biệt trong bức ảnh này, có một chiếc màn hình máy tính ở bên trong có một chiếc màn hình máy tính ở bên trong có một chiếc màn hình máy tính ở bên trong có một chiếc màn hình máy tính.v.v…..Và hàm đệ quy cũng tương tự như vậy.
Một ví dụ đơn giản áp dụng thuật toán đệ quy là hàm đệ quy tính giai thừa.
int giaiThua(int n){
if(n<=1) return 1;
return n * giaiThua(n-1);
}
Trong hàm này bạn sẽ thấy hàm giaiThua() được gọi ngay ở bên trong chính hàm đó, và cụ thể kết quả trả về của hàm này sẽ bằng n nhân với kết quả của gọi lại chính hàm tính Giaithua(n-1).
Theo như bạn đã biết công thức để tính giai thừa của n là n! = 1*2*3*4….*n.
Mình sẽ lấy một con số cụ thể để bạn dễ dàng hình dung hơn. Giả dụ ở đây mình cần tính giai thừa của 4 chẳng hạn thì chương trình bên trên sẽ chạy lần lượt như sau.
Bước 1: Ban đầu nó sẽ gọi hàm giaiThua(4), ở đoạn code trên có thể thấy hàm sẽ chỉ trả về kq là 1 nếu n nhỏ hoặc bằng 1. Mà ở đây n = 4, như vậy nó sẽ chạy xuống lệnh bên dưới tức là return n*giaiThua(n-1) mà ở đây n đang là 4 thế nên ở đây nó sẽ là return 4 * giaiThua(3)(Vì gọi lại hàm n sẽ trừ đi 1), và đương nhiên lúc này hàm giaiThua(3) vẫn chưa có kết quả, như vậy code sẽ chạy xuống bước thứ 2.
Bước 2: Bước này giaiThua(3) sẽ được trả về kết quả là 3*giaiThua(2), mà hàm giaiThua(2) cũng chưa có kết quả nó sẽ gọi tiếp hàm tính giai thừa của 2.
Bước 3: Tiếp tục giaiThua(2) sẽ là return 2*giaiThua(1).
Bước 4: Hàm giaiThua(1) tức là lúc này n=1 như vậy hàm này sẽ ngay lập tức được trả về kết quả cho hàm là 1. Trường hợp này hay còn gọi là trường hợp suy biến trong đệ quy, hay là điều kiện dừng.
Bước 5: Lúc này hàm giaiThua(1) đã có kết quả là 1, hàm Đệ quy sẽ trả ngược kết quả cho các hàm phía trên nó giaiThua(2) = 2*giaiThua(1), tức là giaiThua(2) = 2 *1. Tương tự trả ngược kết quả đối với giaiThua(3), giaiThua(4)…….lúc này giaiThua(4) chính là kết quả cuối cùng của bài toán.
Đệ quy để mà nói đơn giản thực ra cũng không hề đơn giản cho lắm, mà nói khó cũng không hản là khó. Tuy nhiên nếu với những bạn nào không có điểm mạnh về tư duy logic có thể sẽ có một chút khó hình dung hơn. Mình hy vọng qua ví dụ này có thể giúp bạn nắm rõ hơn về hàm đệ quy.
Một số chương trình C++ áp dụng hàm đệ quy
Minh họa thuật toán tính giai thừa bằng hàm đệ quy
#include <stdio.h>
//Hàm tính giai thừa
int giaiThua(int n){
if(n<=1) return 1;//Trường hợp suy biến
return n * giaiThua(n-1); //Gọi lại hàm đệ quy để tính giai thừa n-1
}
int main()
{
printf("Giai thua cua 4 la: %d", giaiThua(4));
}
Minh họa thuật toán tìm kiếm nhị phân bằng đệ quy
#include <stdio.h>
// Hàm tìm kiếm nhị phân sử dụng giải thuật đệ quy
int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = (l+r)/2; //vị trí ở giữa
// Nếu arr[mid] = x, trả về chỉ số và kết thúc.
if (arr[mid] == x)
return mid;
// Nếu arr[mid] > x, gọi hàm đệ quy thực hiện tìm kiếm nửa trái của mảng
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Nếu arr[mid] < x, gọi hàm đệ quy thực hiện tìm kiếm nửa phải của mảng
return binarySearch(arr, mid + 1, r, x);
}
// Nếu không tìm thấy
return -1;
}
int main(void) {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n - 1, x);
if (result == -1)
printf("Khong tim thay phan tu %d trong mang",x);
else
printf("%d xuat hien tai chi so %d", x, result);
return 0;
}
Minh họa thuật toán tính số Fibonacci bằng đệ quy
#include <stdio.h>
//Hàm tính fibonacci
int fibonacci(int n){
if(n<=2) return 1; //Trường hợp nếu n<= sẽ trả ngay kq về cho hàm
return fibonacci(n-1) + fibonacci(n-2); //Gọi lại hàm đệ quy để tính fibonaci thứ n-1 và n-2
}
int main()
{
printf("Fibonacci = %d", fibonacci(6));
}
Cảm ơn bạn đã theo dõi bài viết!
XEM THÊM Các bước đơn giản để tạo một website WordPress trên Infinityfree.net Cấu hình gửi mail trong WordPress sử dụng Plugin WP SMTP Defender Security – Blugin bảo mật WordPress tốt nhất hiện nay Hiển thị CODE các ngôn ngữ lập trình trong bài viết WordPress
