Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 147 ยท Functions

Recursion

Learn recursion in PHP - base cases, factorial and power examples, walking nested arrays and folder trees, recursion depth and memory, memoization and iterative alternatives.

A recursive function is a function that calls itself. That sounds like a recipe for an endless loop, but it's one of the most natural ways to solve problems that contain smaller copies of themselves: a folder contains folders, a menu contains submenus, a comment thread contains replies to replies, and a JSON document contains objects inside objects.

The trick is that each call works on a smaller piece of the problem, and one simple case is answered directly without calling again. This lesson shows how to design recursive functions safely, walks through classic examples, applies recursion to real nested PHP arrays, and explains when a loop is the better choice.

You'll need functions, parameters and return values from Functions and Parameters and Arguments.

The two parts of every recursive function

Every correct recursive function has:

  1. A base case: an input simple enough to answer immediately, with no further call.
  2. A recursive case: the function calls itself with a smaller input and uses the result.

Factorial is the textbook example. The factorial of n, written n!, is n ร— (n-1) ร— ... ร— 1, so 5! is 120. Notice that 5! is just 5 ร— 4!. That's the recursive case. And 1! (or 0!) is 1. That's the base case.

PHP Factorial, the classic example

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with fgets(STDIN)), it gets the next line from this box.

The output is 120, 3628800 and 2432902008176640000. Note that 20! is the largest factorial that fits in a 64-bit int; factorial(21) overflows to a float, and with the int return type and strict mode that becomes a TypeError. See Integers and Floats for why.

How the calls stack up

When factorial(4) runs, it can't finish until factorial(3) returns, which waits for factorial(2), and so on. PHP keeps each unfinished call, with its own $n, on the call stack. Each call has its own local variables (see Variable Scope), so the different $n values never collide. Printing with indentation makes the stack visible:

PHP Watching the call stack grow and shrink

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with fgets(STDIN)), it gets the next line from this box.

The output shows the calls going down, then the answers coming back up:

TEXT
factorial(4) called
  factorial(3) called
    factorial(2) called
      factorial(1) called
      base case: return 1
    return 2 * ... = 2
  return 3 * ... = 6
return 4 * ... = 24

Forgetting the base case

If the base case is missing, or the input never gets smaller, the function calls itself until PHP runs out of memory. PHP has no fixed recursion limit by default: every call uses some memory, and eventually the script hits memory_limit and stops with a fatal error like:

TEXT
Fatal error: Allowed memory size of 268435456 bytes exhausted (tried to allocate 262144 bytes)

That can take seconds and produces an enormous stack trace. Before running a new recursive function, check two things: the base case exists, and every recursive call moves closer to it. (PHP 8.3 also added the zend.max_allowed_stack_size setting, which catches runaway recursion in the C stack, mostly from built-in functions calling back into your code.)

More small examples

Recursion fits any problem you can describe as "do one step, then solve the rest the same way":

PHP Sum of digits, power and palindromes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with fgets(STDIN)), it gets the next line from this box.

The output is 35, 1024, 3.375, bool(true) and bool(false). The power() function is a nice bonus: by halving the exponent each time, it needs only about log2(n) calls, so power(2, 1000) takes 11 calls instead of 1000.

Walking nested arrays

Recursion really shines with data whose depth you don't know in advance. PHP arrays nest freely, so trees of categories, menus or settings are common. A recursive function handles any depth with a few lines:

PHP Rendering a nested menu

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with fgets(STDIN)), it gets the next line from this box.

The output:

TEXT
- Home
- Learn
    - PHP
        - Basics
        - Functions
    - SQL
- About
Total items: 7

Here the base case is hidden but present: an item with no children, or an empty list, makes no further call. On a real site you'd produce nested <ul> lists and escape each title with htmlspecialchars(); the shape of the function stays the same.

A folder tree

File systems are trees too. This example simulates a folder structure with nested arrays (folders are arrays, files are sizes in bytes) and calculates the total size and the path of the largest file:

PHP Total size of a simulated folder tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with fgets(STDIN)), it gets the next line from this box.

This prints Total: 18,400 bytes, Largest: /public/logo.svg and Files: 6. For real directories on disk, PHP gives you RecursiveDirectoryIterator, which does this walking for you; it's covered in Files and Directories.

For simple "visit every leaf value" tasks, PHP has a built-in recursive helper: array_walk_recursive($array, $callback) calls your callback for every non-array value at any depth.

Memoization: avoiding repeated work

Some recursive definitions call themselves more than once per step, and the work explodes. Fibonacci numbers are the classic case: fib(n) = fib(n-1) + fib(n-2). The naive version recomputes the same values again and again: fib(30) makes over 2.6 million calls. Caching results that are already known, called memoization, fixes it:

PHP Naive vs memoized Fibonacci

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with fgets(STDIN)), it gets the next line from this box.

The naive version needs 242785 calls for fib(25), while the memoized one computes each value once and handles fib(90) (2880067194370816120) instantly. The cache is passed by reference so every call shares it. You could also keep it in a static variable, as shown in Variable Scope.

Recursion or a loop?

Anything recursive can be written with a loop, and vice versa. Choose by clarity and by data size:

  • Use recursion for trees and nested structures of unknown depth: menus, comments, folders, JSON, expression parsers. The recursive version usually mirrors the data's shape.
  • Use a loop for linear problems like summing a list or counting down. factorial is clearer as recursion in a textbook, but a for loop is just as readable and uses no extra stack.
  • Watch the depth. Each call costs memory, so recursion that's thousands of levels deep (for example, walking a linked list of 100,000 nodes) is better as a loop. PHP doesn't optimize tail calls, so writing the recursive call last doesn't help.

When a tree is too deep or you want to avoid recursion, use your own stack (an array) to remember work that's still to do:

PHP Walking a tree without recursion

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with fgets(STDIN)), it gets the next line from this box.

This prints root a a1 b, the same depth-first order the recursive version would give. Reversing the children before pushing them keeps the original left-to-right order. Swap array_pop for array_shift (and push the children without reversing them) and the same loop visits the tree level by level (breadth-first), printing root a b a1.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the purpose of the base case in a recursive function?

    Without a base case, or without moving toward it, the function calls itself until PHP runs out of memory.
  2. 2. What does function f(int $n): int { return $n === 0 ? 0 : $n + f($n - 1); } echo f(4); print?

    f(4) is 4 + 3 + 2 + 1 + 0, which is 10.
  3. 3. Why is naive recursive Fibonacci slow?

    The number of calls grows exponentially. Memoization stores each result so it's computed once.
  4. 4. Which task is the most natural fit for recursion?

    Nested structures of unknown depth match recursion's shape. The other tasks are simple loops.

Summary

  • A recursive function calls itself. It needs a base case answered directly and a recursive case that works on a smaller input.
  • Each call has its own variables on the call stack; results flow back up as the calls return.
  • A missing base case recurses until memory_limit is exhausted. PHP has no tail-call optimization.
  • Recursion is ideal for trees and nested arrays: menus, comment threads, folder structures, JSON.
  • Memoization caches results to avoid repeated work, turning exponential algorithms like naive Fibonacci into fast ones.
  • For linear problems or very deep data, use a loop, or a loop with your own stack array.

Next: Using Built-in Functions