What is recursion?

A function that calls itself.

It is used to solve problems that can be broken down into subproblems with the same structure as the original problem. There must be a base case to avoid an infinite loop.

Example of calculating factorial:

<?php
function factorial(int $n): int
{
    // Base case
    if ($n <= 1) {
        return 1;
    }
    // Recursive call
    return $n * factorial($n - 1);
}

echo factorial(5); // Outputs 120
?>

Advantages:

• Elegance and conciseness of code for certain problems.

Disadvantages:

• Can lead to stack overflow with too deep recursion.
• Potentially less efficient than iterative solutions for the same problems due to overhead of function calls.

Often used for traversing trees, file systems, solving combinatorial problems.