Đệ quy là một kỹ thuật lập trình mà trong đó một hàm tự gọi chính nó để giải quyết các bài toán. Đệ quy thường được sử dụng để giải quyết các bài toán có cấu trúc lặp lại hoặc phân chia nhỏ hơn (chia để trị). Khi sử dụng đệ quy, cần phải có một điều kiện dừng, đảm bảo rằng hàm không tiếp tục gọi chính nó vô hạn.
Một ví dụ cơ bản của đệ quy là tính giai thừa của một số. Giai thừa của n (ký hiệu là n!) được tính bằng cách nhân tất cả các số từ 1 đến n, với quy tắc: n! = n * (n - 1)! và 0! = 1.
function factorial($n) {
if ($n == 0) { // Điều kiện dừng
return 1;
}
return $n * factorial($n - 1); // Gọi đệ quy
}
echo factorial(5); // Kết quả: 120
Đệ quy tuyến tính xảy ra khi một hàm đệ quy chỉ gọi lại chính nó một lần trong mỗi lần thực thi. Điều này tạo ra một chuỗi các lời gọi hàm theo một đường thẳng.
Tính tổng các số từ 1 đến n bằng đệ quy tuyến tính:
function sum($n) {
if ($n == 1) {
return 1; // Điều kiện dừng
}
return $n + sum($n - 1); // Gọi đệ quy tuyến tính
}
echo sum(5); // Kết quả: 15 (1 + 2 + 3 + 4 + 5)
Ở ví dụ này, hàm sum() gọi lại chính nó một lần trong mỗi lần thực thi.
Đệ quy nhị phân xảy ra khi mỗi lời gọi hàm đệ quy lại tạo ra hai (hoặc nhiều hơn) lời gọi đệ quy khác. Điều này tạo ra một “cây” các lời gọi đệ quy. Đệ quy nhị phân thường gặp trong các bài toán như tính dãy Fibonacci.
Tính dãy Fibonacci bằng đệ quy nhị phân:
function fibonacci($n) {
if ($n == 0) {
return 0; // Điều kiện dừng
} elseif ($n == 1) {
return 1; // Điều kiện dừng
}
return fibonacci($n - 1) + fibonacci($n - 2); // Gọi đệ quy nhị phân
}
echo fibonacci(6); // Kết quả: 8
Dãy Fibonacci là ví dụ điển hình của đệ quy nhị phân, vì mỗi lời gọi fibonacci($n) lại gọi thêm hai lời gọi đệ quy khác fibonacci($n - 1) và fibonacci($n - 2).
Đệ quy hỗ tương xảy ra khi có nhiều hơn một hàm và chúng gọi lẫn nhau theo chuỗi. Ví dụ, hàm A() có thể gọi hàm B(), và hàm B() lại gọi lại A().
Giả sử chúng ta có hai hàm đệ quy hỗ tương:
function even($n) {
if ($n == 0) {
return true; // Điều kiện dừng
}
return odd($n - 1); // Gọi hàm odd()
}
function odd($n) {
if ($n == 0) {
return false; // Điều kiện dừng
}
return even($n - 1); // Gọi hàm even()
}
echo even(4); // Kết quả: true
echo odd(5); // Kết quả: true
Trong ví dụ này, hai hàm even() và odd() gọi lẫn nhau để xác định xem một số là chẵn hay lẻ.
Khử đệ quy là quá trình biến một thuật toán đệ quy thành thuật toán không đệ quy. Việc khử đệ quy thường được thực hiện để tối ưu hóa về hiệu suất hoặc tránh quá nhiều lời gọi hàm lồng nhau, gây tràn bộ nhớ (stack overflow).
Khử đệ quy của việc tính giai thừa có thể được thực hiện bằng cách sử dụng vòng lặp:
function factorial_non_recursive($n) {
$result = 1;
for ($i = 1; $i <= $n; $i++) {
$result *= $i;
}
return $result;
}
echo factorial_non_recursive(5); // Kết quả: 120
Trong ví dụ này, thay vì sử dụng đệ quy, chúng ta sử dụng vòng lặp for để tính giai thừa, tránh được việc gọi đệ quy lặp đi lặp lại.
Các loại đệ quy nâng cao thường gặp trong PHP (và các ngôn ngữ lập trình khác) bao gồm đệ quy đuôi (tail recursion), đệ quy không xác định (indirect recursion) và đệ quy phân chia và chinh phục (divide and conquer recursion). Đây là các biến thể của đệ quy cơ bản nhưng được áp dụng vào các bài toán phức tạp hơn.
Đệ quy đuôi là một dạng đệ quy đặc biệt, trong đó lời gọi đệ quy là hành động cuối cùng của hàm. Điều này giúp tối ưu hóa về mặt bộ nhớ, vì trình biên dịch hoặc bộ xử lý có thể “loại bỏ” các ngăn xếp đệ quy không cần thiết (tối ưu hóa đệ quy đuôi).
Viết hàm tính tổng từ 1 đến n bằng đệ quy đuôi:
function tailSum($n, $accumulator = 0) {
if ($n == 0) {
return $accumulator; // Điều kiện dừng
}
return tailSum($n - 1, $accumulator + $n); // Gọi đệ quy đuôi
}
echo tailSum(5); // Kết quả: 15
Trong ví dụ này, hàm tailSum() sử dụng một biến tích lũy ($accumulator) để lưu trữ kết quả tạm thời và lời gọi đệ quy là hành động cuối cùng, giúp tối ưu bộ nhớ.
Đệ quy đuôi có thể dễ dàng được chuyển thành vòng lặp để tối ưu hóa hiệu suất. Trình biên dịch của một số ngôn ngữ có thể tự động tối ưu hóa đệ quy đuôi thành các vòng lặp.
Đệ quy phân chia và chinh phục là một kỹ thuật đệ quy phổ biến, được áp dụng trong các thuật toán phức tạp, như Merge Sort, Quick Sort, Binary Search, và nhiều bài toán xử lý mảng, cây. Ý tưởng là chia bài toán lớn thành các bài toán con nhỏ hơn và xử lý chúng, sau đó kết hợp kết quả lại.
Merge Sort sử dụng đệ quy phân chia và chinh phục:
function mergeSort($array) {
if (count($array) <= 1) {
return $array; // Điều kiện dừng
}
// Chia mảng ra làm đôi
$middle = count($array) / 2;
$left = array_slice($array, 0, $middle);
$right = array_slice($array, $middle);
// Gọi đệ quy
$left = mergeSort($left);
$right = mergeSort($right);
// Kết hợp kết quả
return merge($left, $right);
}
function merge($left, $right) {
$result = [];
$i = $j = 0;
while ($i < count($left) && $j < count($right)) {
if ($left[$i] < $right[$j]) {
$result[] = $left[$i++];
} else {
$result[] = $right[$j++];
}
}
return array_merge($result, array_slice($left, $i), array_slice($right, $j));
}
$array = [38, 27, 43, 3, 9, 82, 10];
print_r(mergeSort($array));
Trong ví dụ này, mảng được chia thành hai nửa nhỏ hơn, sau đó mỗi nửa được sắp xếp đệ quy, và cuối cùng kết hợp lại để tạo ra một mảng đã sắp xếp.
Đệ quy không xác định là một dạng đệ quy tương tự như đệ quy hỗ tương, nhưng phức tạp hơn. Thay vì hai hàm gọi nhau trực tiếp, chúng có thể gọi nhau một cách gián tiếp qua nhiều bước. Điều này xảy ra khi một chuỗi các hàm gọi nhau lẫn lộn.
Trong đệ quy không xác định, giả sử có ba hàm gọi lẫn nhau:
function A($n) {
if ($n <= 0) {
return;
}
echo "A: $n\n";
B($n - 1); // Gọi hàm B
}
function B($n) {
if ($n <= 0) {
return;
}
echo "B: $n\n";
C($n - 1); // Gọi hàm C
}
function C($n) {
if ($n <= 0) {
return;
}
echo "C: $n\n";
A($n - 1); // Gọi lại hàm A
}
A(3);
Kết quả đầu ra:
Ở đây, hàm A() gọi hàm B(), sau đó B() gọi hàm C(), và C() lại gọi ngược lại hàm A(). Đây là một ví dụ của đệ quy không xác định vì có nhiều hàm gọi qua lại lẫn nhau theo một chuỗi gián tiếp.
Đệ quy lồng nhau xảy ra khi một hàm đệ quy gọi lại chính nó trong phần đối số của lời gọi hàm. Đây là một hình thức phức tạp hơn của đệ quy.
Hàm Ackermann là một ví dụ điển hình của đệ quy lồng nhau:
function ackermann($m, $n) {
if ($m == 0) {
return $n + 1;
} elseif ($n == 0) {
return ackermann($m - 1, 1); // Gọi đệ quy lồng nhau
} else {
return ackermann($m - 1, ackermann($m, $n - 1)); // Gọi đệ quy lồng nhau
}
}
echo ackermann(2, 2); // Kết quả: 7
Trong ví dụ này, hàm Ackermann có cấu trúc rất phức tạp vì lời gọi hàm đệ quy có thể lồng nhiều lớp. Đây là một ví dụ tiêu biểu của đệ quy lồng nhau (nested recursion).
Đệ quy ngược là một hình thức đệ quy trong đó kết quả của lời gọi đệ quy được xử lý sau khi lời gọi đệ quy đã hoàn thành. Nó ngược với đệ quy đuôi, nơi kết quả được xử lý ngay trước khi gọi đệ quy.
In các phần tử của một mảng theo thứ tự ngược lại bằng đệ quy ngược:
function reversePrint($array, $index) {
if ($index < 0) {
return; // Điều kiện dừng
}
reversePrint($array, $index - 1); // Gọi đệ quy trước
echo $array[$index] . " "; // In ra sau khi lời gọi đệ quy kết thúc
}
$array = [1, 2, 3, 4, 5];
reversePrint($array, count($array) - 1);
Kết quả:
Đệ quy ngược rất hữu ích khi bạn muốn xử lý các lời gọi đệ quy sau khi tất cả các lời gọi trước đó đã hoàn thành.
Mỗi loại đệ quy có ứng dụng riêng trong các bài toán cụ thể, giúp giải quyết các vấn đề phức tạp một cách hiệu quả hơn.
