PHP - Recursive Functions
Một hàm đệ quy là một hàm tự gọi chính nó cho đến khi một điều kiện nhất định được thỏa mãn. Trong PHP, có thể định nghĩa một hàm đệ quy.
-
Đệ quy được sử dụng khi một vấn đề nhất định được định nghĩa theo chính nó.
-
Đôi khi, việc giải quyết một vấn đề bằng cách tiếp cận lặp lại có thể rất tẻ nhạt. Cách tiếp cận đệ quy cung cấp một giải pháp rất ngắn gọn cho những vấn đề dường như phức tạp.
-
Đệ quy trong PHP rất giống với đệ quy trong C và C++.
-
Các hàm đệ quy thường được sử dụng trong việc duyệt các cấu trúc dữ liệu lồng ghép, cũng như trong các thuật toán tìm kiếm hoặc sắp xếp.
-
Duyệt cây nhị phân, sắp xếp heap và tìm đường đi ngắn nhất là một số trường hợp mà đệ quy được sử dụng.
Calculation of Factorial using Recursion
Ví dụ phổ biến nhất về đệ quy là tính giai thừa. Về mặt toán học, giai thừa được định nghĩa là −
n! = n × (n-1)!
Có thể thấy rằng chúng ta sử dụng chính giai thừa để định nghĩa giai thừa. Do đó, đây là một trường hợp phù hợp để viết một hàm đệ quy.
Hãy mở rộng định nghĩa trên để tính giá trị giai thừa của 5.
5! = 5 × 4!
5 × 4 × 3!
5 × 4 × 3 × 2!
5 × 4 × 3 × 2 × 1!
5 × 4 × 3 × 2 × 1
= 120
Trong khi chúng ta có thể thực hiện phép tính này bằng cách sử dụng vòng lặp, hàm đệ quy của nó liên quan đến việc gọi lại nó một cách liên tiếp bằng cách giảm số cho đến khi nó đạt 1.
Example
Dưới đây là hàm đệ quy để tính giai thừa.
<?php
function factorial ($n) {
if ($n == 1) {
echo $n . PHP_EOL;
return 1;
} else {
echo "$n * ";
return $n*factorial($n-1);
}
}
echo "Factorial of 5 = " . factorial(5);
?>
Nó sẽ tạo ra output −
5 * 4 * 3 * 2 * 1 Factorial of 5 = 120
Binary Search using Recursion
Hãy cùng xem một ví dụ khác để hiểu cách hoạt động của đệ quy. Vấn đề ở đây là kiểm tra xem một số đã cho có mặt trong danh sách hay không.
Trong khi chúng ta có thể thực hiện tìm kiếm tuần tự cho một số nhất định trong danh sách bằng cách sử dụng một vòng lặp for và so sánh từng số, thì tìm kiếm tuần tự không hiệu quả, đặc biệt nếu danh sách quá lớn. Ở đây, chúng ta có thể sử dụng thuật toán tìm kiếm nhị phân kiểm tra xem chỉ số 'high' có lớn hơn chỉ số 'low' hay không. Dựa trên giá trị hiện có tại biến 'mid', hàm sẽ được gọi lại để tìm kiếm phần tử.
Chúng tôi có một danh sách các số, được sắp xếp theo thứ tự tăng dần. Sau đó, chúng tôi tìm điểm giữa của danh sách và giới hạn việc kiểm tra sang bên trái hoặc bên phải của điểm giữa tùy thuộc vào việc số mong muốn nhỏ hơn hay lớn hơn số ở điểm giữa.
Sơ đồ dưới đây cho thấy cách thức hoạt động của tìm kiếm nhị phân −
Example
Đoạn mã sau đây triển khai kỹ thuật tìm kiếm nhị phân đệ quy −
<?php
function bsearch($my_list, $low, $high, $elem) {
if ($high >= $low) {
$mid = intval(($high + $low)/2);
if ($my_list[$mid] == $elem)
return $mid;
elseif ($my_list[$mid] > $elem)
return bsearch($my_list, $low, $mid - 1, $elem);
else
return bsearch($my_list, $mid + 1, $high, $elem);
}
else
return -1;
}
$list = [5,12,23, 45, 49, 67, 71, 77, 82];
$num = 67;
$result = bsearch($list,0,count($list)-1, $num);
if ($result != -1)
echo " Number $num found at index " . $result;
else
echo "Element not found!";
?>
Nó sẽ tạo ra output −
Number 67 found at index 5
Bạn có thể kiểm tra đầu ra cho các số khác nhau có trong danh sách đã cho, cũng như những số không có trong danh sách.