Hàm đệ quy - Giải quyết vấn đề toán học một cách nhìn trực quan

Hàm đệ quy là gì? Hãy cùng tìm hiểu về khái niệm quan trọng này trong lập trình. Trong ngôn ngữ lập trình, hàm đệ quy được hiểu là quá trình lặp lại các mục theo cách tương tự. Tức là, một hàm được coi là hàm đệ quy nếu có sự gọi lại của chính hàm đó ngay bên trong nó.

Khi sử dụng hàm đệ quy, chúng ta cần chú ý đến việc thiết lập điều kiện thoát khỏi hàm. Nếu không có điều kiện này, hàm sẽ thực hiện vô hạn, tương tự như vòng lặp vô hạn, gây ra hiện tượng giật, lag và tràn bộ nhớ.

Hàm đệ quy có thể giúp giải quyết nhiều vấn đề toán học, ví dụ như tính giai thừa của một số, tạo chuỗi Fibonacci và nhiều vấn đề khác.

Cấu trúc của hàm đệ quy

Một hàm đệ quy có cấu trúc như sau:

void recursion() {     // Gọi lại chính bản thân hàm     recursion(); }

Trong đó:

• void là kiểu trả về của hàm (tùy vào bài toán mà có kiểu trả về khác nhau)
• recursion là tên hàm đệ quy (tên hàm có thể đặt bất kỳ theo ý muốn)

Một cách nhìn trực quan về hàm đệ quy trong lập trình:

Chương trình dưới đây minh họa việc tính giai thừa của một số thông qua sử dụng hàm đệ quy.

#include   int giaithua(int n) {     // Nếu n bằng 0 hoặc n bằng 1, thì n! = 1     if(n == 0 || n == 1) {         return 1;     }      // Gọi lại hàm tính giai thừa theo công thức n! = n * (n-1)!     return n * giaithua(n - 1); }  int main() {     // Khai báo n     int n;      printf("Nhập N: ");     scanf("%d", &n);      printf("%d giai thừa là: %d\n", n, giaithua(n)); }

Kết quả:

Nhập N: 5 5 giai thừa là: 120

Dưới đây là hình minh họa việc sử dụng đệ quy để tính giai thừa của một số (ở đây n = 5).

Giải thích:

Vì kết quả của phép tính giai thừa là một số nguyên, hàm có kiểu trả về là int. Như ta đã biết, n! (n giai thừa) được tính theo công thức n! = n * (n-1)! và khi tính giai thừa, ta quy ước 0! = 1 và 1! = 1. Quy ước này chính là điều kiện dừng của hàm đệ quy tính n giai thừa ở chương trình trên.

Điều kiện return 1; ở trên là rất cần thiết, nó phải được đặt ở đầu hàm để kiểm tra trước khi hàm đệ quy gọi lại chính nó.

Chuỗi số Fibonacci được tính theo công thức: f(n) = f(n-1) + f(n-2) (công thức này đúng khi n > 2). Trong dãy Fibonacci, ta cũng quy ước rằng f(1) = 1 và f(2) = 1.

Chương trình dưới đây sử dụng đệ quy để tính dãy Fibonacci trong khoảng từ 1 đến n (n được người dùng nhập vào).

#include   int fibonacci(int n) {     // Điều kiện dừng của Fibonacci     if(n == 0) {         return 0;     }     if(n == 1) {         return 1;     }      // Tính kết quả chuỗi Fibonacci theo f(n) = f(n-1) + f(n-2)     return fibonacci(n-1) + fibonacci(n-2); }  int main() {     int n;      printf("Nhập N: ");     scanf("%d", &n);      printf("Kết quả chuỗi FIBONACCI từ 0 đến %d là:\n", n);      // Duyệt các số từ 0 đến n và đưa vào hàm fibonacci để nhận kết quả     for (int i = 0; i < n; i++) {         printf("%d\n", fibonacci(i));     } }

Nhập N: 5

Kết quả chuỗi FIBONACCI từ 0 đến 5 là:

0 1 1 2 3

Dưới đây là minh họa chương trình trên dưới dạng cây:

Giải thích:

Hàm Fibonacci cũng trả về một kết quả là số nguyên, vì vậy ta cũng có kiểu trả về là int.

Trong hàm, ta có điều kiện dừng khi n = 0 thì return 0 hoặc khi n = 1 thì return 1. Đây chính là điều kiện kết thúc hàm đệ quy trong bài toán này!

Câu lệnh return fibonacci(n-1) + fibonacci(n-2); chính là việc thực hiện phép tính f(n) = f(n-1) + f(n-2).

Chú ý: Số lượng tính toán sẽ tăng gấp đôi sau mỗi lần gọi đệ quy, vì vậy khi nhập N quá lớn, chương trình sẽ mất thời gian để tính toán và đưa ra kết quả!