Hàm đệ quy

Đệ quy là một kỹ thuật lập trình, trong đó một hàm (function) tự gọi chính nó để giải quyết vấn đề. Cách này tạo ra hành vi giống vòng lặp, nhưng thay vì dùng vòng lặp thông thường, hàm liên tục tự gọi lại với các tham số đã thay đổi cho đến khi tìm ra lời giải.

Mọi hàm đệ quy đều cần có hai thành phần thiết yếu để hoạt động chính xác:

Trường hợp cơ sở: Đây là điều kiện dừng đệ quy (recursion). Nếu không có điều kiện này, hàm (function) sẽ gọi lại chính nó vô hạn, khiến chương trình gặp sự cố. Trường hợp cơ sở xác định khi nào hàm nên trả về kết quả thay vì tiếp tục gọi lại chính nó.

Bước đệ quy: Đây là bước hàm gọi chính nó với phiên bản đã chỉnh sửa của bài toán ban đầu, dần tiến đến trường hợp cơ sở.

Đây là một ví dụ đơn giản về hàm đệ quy tính giai thừa:

<?php
function factorial($n) {
    // Trường hợp cơ sở: factorial của 1 là 1
    if ($n <= 1) {
        return 1;
    }
    
    // Bước đệ quy: n! = n * (n-1)!
    return $n * factorial($n - 1);
}

echo factorial(5);  // Đầu ra: 120
?>

Trong ví dụ này, factorial(5) gọi factorial(4), hàm này gọi factorial(3), và cứ tiếp tục như vậy cho đến khi đạt đến factorial(1) (trường hợp cơ sở). Sau đó, các kết quả được nhân ngược lên: 1 × 2 × 3 × 4 × 5 = 120.