Recursive Functions

Part of the Logic & Flow section of Coddy's PHP journey — lesson 8 of 68.

Recursion is a programming technique where a function calls itself to solve a problem. This creates a loop-like behavior, but instead of using traditional loops, the function repeatedly invokes itself with modified parameters until it reaches a solution.

Every recursive function must have two essential components to work correctly:

Base Case: This is the condition that stops the recursion. Without it, the function would call itself infinitely, causing your program to crash. The base case defines when the function should return a result instead of calling itself again.

Recursive Step: This is where the function calls itself with a modified version of the original problem, gradually moving toward the base case.

Here's a simple example of a recursive function that calculates a factorial:

<?php
function factorial($n) {
    // Base case: factorial of 1 is 1
    if ($n <= 1) {
        return 1;
    }
    
    // Recursive step: n! = n * (n-1)!
    return $n * factorial($n - 1);
}

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

In this example, factorial(5) calls factorial(4), which calls factorial(3), and so on, until it reaches factorial(1) (the base case). Then the results multiply back up: 1 × 2 × 3 × 4 × 5 = 120.

Test yourself

This lesson includes a short quiz. Start the lesson to answer it and track your progress.

Test yourself

This lesson includes a short quiz. Start the lesson to answer it and track your progress.

Test yourself

This lesson includes a short quiz. Start the lesson to answer it and track your progress.

Challenge

Easy

Create a recursive function called sumDigits that takes a positive integer and returns the sum of its digits. The function should use recursion to break down the number digit by digit.

You will receive one input: a positive integer. Read the input, call your recursive function with that number, and print the sum of its digits.

Input format: One line containing a positive integer

Expected output: The sum of all digits in the number

Cheat sheet

Recursion is a programming technique where a function calls itself to solve a problem. Every recursive function needs two components:

Base Case: The condition that stops the recursion to prevent infinite loops.

Recursive Step: Where the function calls itself with modified parameters, moving toward the base case.

Example of a recursive factorial function:

<?php
function factorial($n) {
    // Base case: factorial of 1 is 1
    if ($n <= 1) {
        return 1;
    }
    
    // Recursive step: n! = n * (n-1)!
    return $n * factorial($n - 1);
}

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

Try it yourself

<?php
// Read input
$number = intval(fgets(STDIN));

// TODO: Create your recursive function sumDigits here


// Call the function and output the result
echo sumDigits($number);
?>

Test yourself

This lesson includes a short quiz. Start the lesson to answer it and track your progress.

Recursive Functions

Cheat sheet

All lessons in Logic & Flow