Đệ quy trong C

Xin chào các bạn, những nhà lập trình tương lai! Hôm nay, chúng ta sẽ cùng nhau khám phá một trong những khái niệm thú vị nhất trong lập trình: đệ quy. Đừng lo lắng nếu nghe có vẻ đáng sợ - đến cuối bài hướng dẫn này, bạn sẽ trở thành chuyên gia đệ quy! Hãy cùng nhau bắt đầu hành trình thú vị này.

Đệ quy là gì trong C?

Hãy tưởng tượng bạn đang nhìn thấy mình trong gương, và đằng sau bạn cũng có một chiếc gương khác. Bạn sẽ thấy vô số phản xạ của mình. Đó là một cách nào đó giống với đệ quy trong lập trình!

Một hàm đệ quy là một hàm gọi chính nó trong quá trình thực thi. Nó giống như một hàm nói, "Hey, tôi cần một chút giúp đỡ. Ai có thể giúp tôi tốt hơn... chính tôi?"

Dưới đây là một ví dụ đơn giản:

void countdown(int n) {
if (n == 0) {
printf("Blastoff!\n");
} else {
printf("%d\n", n);
countdown(n - 1);
}
}

Trong hàm này, countdown gọi chính nó với một số nhỏ hơn mỗi lần. Nó giống như một countdown tên lửa, nơi chúng ta tiếp tục đếm cho đến khi đạt zero và sau đó blast off!

Tại sao lại sử dụng đệ quy trong C?

Bạn có thể tự hỏi, "Tại sao lại phiền phức với đệ quy khi chúng ta có vòng lặp?" Đó là một câu hỏi tuyệt vời! Đệ quy có một số ưu thế:

1. Nó có thể làm cho mã dễ đọc và thanh lịch hơn cho một số vấn đề.
2. Nó rất tốt cho các nhiệm vụ có bản chất đệ quy, như duyệt cấu trúc cây.
3. Nó có thể giảm bớt nhu cầu sử dụng cấu trúc vòng lặp phức tạp và các biến tạm.

Tuy nhiên, đệ quy không phải lúc nào cũng là sự lựa chọn tốt nhất. Nó có thể tiêu tốn bộ nhớ nhiều và chậm hơn cho một số vấn đề. Như với nhiều thứ trong lập trình, việc chọn đúng công cụ cho công việc là rất quan trọng.

Tính giai thừa bằng đệ quy

Hãy cùng xem một ví dụ kinh điển của đệ quy: tính giai thừa. Giai thừa của một số n (viết là n!) là tích của tất cả các số nguyên dương nhỏ hơn hoặc bằng n.

Dưới đây là cách chúng ta có thể tính giai thừa đệ quy:

int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}

Hãy phân tích này:

1. Nếu n là 0 hoặc 1, chúng ta trả về 1 (đây là trường hợp cơ bản).
2. Ngược lại, chúng ta nhân n với giai thừa của (n-1).

Vậy, nếu chúng ta gọi factorial(5), sẽ xảy ra gì:

• 5 * factorial(4)
• 5 (4 factorial(3))
• 5 (4 (3 * factorial(2)))
• 5 (4 (3 (2 factorial(1))))
• 5 (4 (3 (2 1)))
• 5 (4 (3 * 2))
• 5 (4 6)
• 5 * 24
• 120

Và thế là chúng ta có - 5! = 120.

Tìm kiếm nhị phân bằng đệ quy

Tìm kiếm nhị phân là một thuật toán hiệu quả để tìm một mục trong danh sách đã sắp xếp. Nó hoạt động bằng cách liên tục chia đôi khoảng tìm kiếm. Hãy thực hiện nó đệ quy:

int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l) / 2;

if (arr[mid] == x)
return mid;

if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);

return binarySearch(arr, mid + 1, r, x);
}

return -1;
}

Hàm này thực hiện các bước sau:

1. Tính toán chỉ số giữa.
2. Nếu phần tử giữa là mục tiêu, chúng ta đã xong!
3. Nếu mục tiêu nhỏ hơn phần tử giữa, tìm kiếm nửa trái.
4. Nếu mục tiêu lớn hơn phần tử giữa, tìm kiếm nửa phải.
5. Nếu không tìm thấy phần tử, trả về -1.

Nó giống như một trò chơi cao cấp "đoán số", nơi bạn luôn đoán số ở giữa trong phạm vi còn lại!

Dãy Fibonacci bằng đệ quy

Dãy Fibonacci là một dãy số nơi mỗi số là tổng của hai số trước đó. Đây là một ứng viên tuyệt vời cho đệ quy!

Dưới đây là cách chúng ta có thể tạo ra các số Fibonacci đệ quy:

int fibonacci(int n) {
if (n <= 1)
return n;
return fibonacci(n-1) + fibonacci(n-2);
}

Hàm này hoạt động như sau:

1. Nếu n là 0 hoặc 1, chúng ta trả về n (đây là các trường hợp cơ bản).
2. Đối với bất kỳ n nào khác, chúng ta trả về tổng của hai số Fibonacci trước đó.

Vậy, nếu chúng ta gọi fibonacci(5), sẽ xảy ra gì:

• fibonacci(5) = fibonacci(4) + fibonacci(3)
• fibonacci(4) = fibonacci(3) + fibonacci(2)
• fibonacci(3) = fibonacci(2) + fibonacci(1)
• fibonacci(2) = fibonacci(1) + fibonacci(0)
• fibonacci(1) = 1
• fibonacci(0) = 0

Đi ngược lại, chúng ta có:

• fibonacci(2) = 1 + 0 = 1
• fibonacci(3) = 1 + 1 = 2
• fibonacci(4) = 2 + 1 = 3
• fibonacci(5) = 3 + 2 = 5

Vậy số Fibonacci thứ 5 là 5!

Các phương pháp đệ quy phổ biến

Dưới đây là bảng tóm tắt các phương pháp đệ quy phổ biến mà chúng ta đã thảo luận:

Phương pháp	Mô tả	Trường hợp cơ bản	Trường hợp đệ quy
Giai thừa	Tính n!	n = 0 hoặc 1	n * factorial(n-1)
Tìm kiếm nhị phân	Tìm phần tử trong mảng đã sắp xếp	Phần tử tìm thấy hoặc không có trong mảng	Tìm nửa trái hoặc phải
Fibonacci	Tạo số Fibonacci	n <= 1	fibonacci(n-1) + fibonacci(n-2)

Nhớ rằng, chìa khóa để hiểu đệ quy là tin rằng cuộc gọi đệ quy sẽ thực hiện đúng công việc của nó. Nó giống như giao một nhiệm vụ cho một phiên bản sao của bạn - bạn biết họ sẽ xử lý nó như bạn vậy!

Đệ quy có thể hơi khó hiểu ban đầu, nhưng với sự luyện tập, nó sẽ trở thành một công cụ mạnh mẽ trong bộ công cụ lập trình của bạn. Hãy tiếp tục thử nghiệm, và sớm bạn sẽ thấy các giải pháp đệ quy ở mọi nơi!

Chúc các bạn lập trình vui vẻ, và hãy nhớ - để hiểu đệ quy, bạn phải trước hết hiểu đệ quy. ?

Credits: Image by storyset