PHP - Hàm Đệ quy

Xin chào các bạn đang học lập trình! Hôm nay, chúng ta sẽ cùng nhau khám phá thế giới kỳ diệu của các hàm đệ quy trong PHP. Đừng lo lắng nếu bạn mới bắt đầu học lập trình; tôi sẽ hướng dẫn bạn từng bước qua khái niệm này, tương tự như tôi đã làm với hàng trăm học viên trong những năm dạy học của mình. Nào, hãy lấy một tách cà phê (hoặc đồ uống yêu thích của bạn), và cùng nhau bắt đầu hành trình thú vị này nhé!

PHP - Recursive Functions

Hàm Đệ quy là gì?

Trước khi chúng ta đi vào chi tiết, hãy hiểu qua về hàm đệ quy là gì. Hãy tưởng tượng bạn đang nhìn thấy mình trong gương, và phía sau bạn cũng có một chiếc gương. Bạn sẽ thấy hình ảnh của mình phản chiếu vô hạn, phải không? Đó là một cách nào đó tương tự với cách hàm đệ quy hoạt động 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 của mình. Nó giống như phiên bản kỹ thuật số của những con búp bê Nga嵌套, mỗi con búp bê chứa một phiên bản nhỏ hơn của chính nó bên trong.

Tại sao sử dụng hàm đệ quy?

Bạn có thể đang tự hỏi, "Tại sao tôi lại muốn một hàm gọi chính nó? Đó có không phải là rất rối rắm không?" Thực tế, hàm đệ quy có thể rất hữu ích cho việc giải quyết các vấn đề có cấu trúc lặp lại. Chúng có thể làm cho mã của chúng ta trở nên thanh lịch và dễ hiểu hơn cho một số loại vấn đề nhất định.

Hãy cùng xem một ví dụ đơn giản để làm quen:

function countDown($n) {
if ($n <= 0) {
echo "Blastoff!";
} else {
echo $n . "... ";
countDown($n - 1);
}
}

countDown(5);

Nếu chúng ta chạy hàm này với countDown(5), đây là những gì xảy ra:

Nó in ra "5... "
Sau đó gọi chính nó với giá trị 4
In ra "4... "
Gọi chính nó với giá trị 3
Và cứ thế cho đến khi đạt giá trị 0 và in ra "Blastoff!"

Kết quả sẽ là: "5... 4... 3... 2... 1... Blastoff!"

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

Mỗi hàm đệ quy đều có hai phần chính:

Trường hợp cơ sở (Base case): Đây là điều kiện dừng đệ quy. Nếu không có điều kiện này, hàm của bạn sẽ gọi chính nó mãi mãi (hoặc cho đến khi máy tính của bạn hết bộ nhớ)!
Trường hợp đệ quy (Recursive case): Đây là phần mà hàm gọi chính nó, thường với một tham số đã thay đổi.

Trong ví dụ countdown của chúng ta, if ($n <= 0) là trường hợp cơ sở, và countDown($n - 1) là trường hợp đệ quy.

Tính toán阶乘 bằng đệ quy

Bây giờ chúng ta đã hiểu được cơ bản, hãy cùng giải quyết một bài toán kinh điển: tính toán giá trị阶乘. Giá trị阶乘 của một số n (viết tắ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.

Ví dụ: 5! = 5 4 3 2 1 = 120

Dưới đây là cách chúng ta có thể tính阶乘 bằng đệ quy:

function factorial($n) {
if ($n <= 1) {
return 1;
} else {
return $n * factorial($n - 1);
}
}

echo factorial(5); // Output: 120

Hãy cùng phân tích này:

Trường hợp cơ sở của chúng ta là if ($n <= 1). Chúng ta biết rằng 1! và 0! đều bằng 1, vì vậy chúng ta trả về 1 trong trường hợp này.
Đối với bất kỳ số nào khác, chúng ta nhân $n với giá trị阶乘 của (n-1).

Khi chúng ta gọi factorial(5), đây là những gì xảy ra sau hậu trường:

factorial(5) = 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

Có phải nó rất đẹp mắt cách hàm liên tục gọi chính nó cho đến khi đạt đến trường hợp cơ sở, và sau đó kết quả được cộng dồn lên?

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

Bây giờ, hãy nâng cấp và xem xét một ví dụ phức tạp hơn: tìm kiếm nhị phân. Tìm kiếm nhị phân là một thuật toán hiệu quả để tìm kiếm một mục trong danh sách đã được sắp xếp. Nó hoạt động bằng cách liên tục chia đôi phần của danh sách có thể chứa mục, cho đến khi bạn thu hẹp được vị trí có thể chứa mục xuống chỉ còn một.

Dưới đây là cách chúng ta có thể thực hiện tìm kiếm nhị phân bằng đệ quy:

function binarySearch($arr, $left, $right, $x) {
if ($right >= $left) {
$mid = $left + floor(($right - $left) / 2);

// Nếu phần tử có mặt chính giữa
if ($arr[$mid] == $x) {
return $mid;
}

// Nếu phần tử nhỏ hơn phần tử giữa, nó chỉ có thể có mặt trong nửa trái
if ($arr[$mid] > $x) {
return binarySearch($arr, $left, $mid - 1, $x);
}

// Ngược lại, phần tử chỉ có thể có mặt trong nửa phải
return binarySearch($arr, $mid + 1, $right, $x);
}

// Khi phần tử không có trong mảng
return -1;
}

$arr = [2, 3, 4, 10, 40];
$x = 10;
$result = binarySearch($arr, 0, count($arr) - 1, $x);
echo ($result == -1) ? "Phần tử không có trong mảng" : "Phần tử có mặt tại chỉ số " . $result;

Hàm này có thể trông đáng sợ ban đầu, nhưng hãy cùng phân tích nó:

Chúng ta bắt đầu bằng cách kiểm tra nếu chỉ số phải lớn hơn hoặc bằng chỉ số trái. Đây là điều kiện tiếp tục.
Chúng ta tính toán chỉ số giữa.
Nếu phần tử giữa là mục tiêu của chúng ta, chúng ta đã hoàn thành!
Nếu phần tử giữa lớn hơn mục tiêu, chúng ta đệ quy tìm kiếm trong nửa trái của mảng.
Nếu phần tử giữa nhỏ hơn mục tiêu, chúng ta đệ quy tìm kiếm trong nửa phải của mảng.
Nếu chúng ta đã耗尽 tìm kiếm (phải < trái), chúng ta trả về -1 để chỉ ra rằng phần tử không có trong mảng.

Sự đẹp mắt của cách tiếp cận đệ quy này là nó tự nhiên chia bài toán thành các bài toán con nhỏ hơn, làm cho mã trở nên thanh lịch và dễ hiểu hơn khi bạn nắm bắt được khái niệm.

Kết luận

Hàm đệ quy có thể trông hơi rối rắm ban đầu, nhưng chúng là một công cụ vô cùng mạnh mẽ trong bộ công cụ của một nhà lập trình. Chúng cho phép chúng ta giải quyết các bài toán phức tạp với mã thanh lịch và gọn gàng. Khi bạn gyak hơn, bạn sẽ bắt đầu nhận biết các bài toán phù hợp với giải pháp đệ quy.

Nhớ rằng, giống như bất kỳ công cụ mạnh mẽ nào khác, đệ quy nên được sử dụng một cách cẩn thận. Đôi khi, một giải pháp theo vòng lặp có thể hiệu quả hơn hoặc dễ hiểu hơn. Khi bạn có nhiều kinh nghiệm hơn, bạn sẽ phát triển trực giác để biết khi nào nên sử dụng đệ quy và khi nào nên sử dụng các phương pháp khác.

Tiếp tục lập trình, tiếp tục thử nghiệm, và quan trọng nhất, hãy vui vẻ! Lập trình không chỉ là khoa học mà còn là nghệ thuật, và việc nắm vững khái niệm như đệ quy sẽ giúp bạn tạo ra mã đẹp mắt và hiệu quả. Hẹn gặp lại các bạn vào lần sau, chúc các bạn lập trình vui vẻ!

Credits: Image by storyset

Hướng Dẫn Trước:

PHP - Chuyển giao hàm

Hướng Dẫn Tiếp Theo:

PHP - Gợi ý kiểu