# Understanding Recursion

In one of my previous articles I wrote about iterators and how you can use them. Today I’d like to look at the fraternal twin of iteration: recursion. Before we talk about recursion, though, let’s take a look at this snippet of code:

``````<?php
function factorial(\$number) {
if (\$number < 0) {
throw new InvalidArgumentException('Number cannot be less than zero');
}
\$factorial = 1;
while (\$number > 0) {
\$factorial *= \$number;
\$number --;
}
return \$factorial;
}``````
A factorial is the result of a number multiplied by all positive integers less than that number, and the function above calculates the factorial of any number given to it using a simple loop. Now let’s rewrite the example this way:
``````<?php
function factorial_recursive(\$number) {
if (\$number < 0) {
throw new InvalidArgumentException('Number cannot be less than zero');
}
if (\$number == 0) {
return 1;
}
return \$number * factorial_recursive(\$number – 1);
}``````
We get the same results when we call both functions, but notice that the second function calculates the factorial by calling itself. This is known as recursion.

## What’s Recursion?

A recursive function is one that calls itself, either directly or in a cycle of function calls. Recursion can also refer to a method of problem solving that first solves a smaller version of the problem and then uses that result plus some other computation to formulate an answer to the original problem. Often times, in the process of solving the smaller version, the method will solve yet a smaller version of the problem, and so on, until it reaches a “base case” which is trivial to solve. To write a recursive function, you need to provide it with some means of return or else it will keep calling itself for eternity (or until the call stack blows up, the script times out, or memory is exhausted). This is known as a guard clause or base case. The simplest form of a recursive function is as follows:
``````<?php
function my_recursive_func (args) {
if (simplest case) {
// The Base Case/Guard Clause that stops the
// function from running forever
return simple value;
}
else {
//call function again with simpler args
my_recursive_func(argsSimplified);
}
}``````

## Types of Recursion

When a function calls itself directly, it is referred to as direct recursion. A function in a cycle of function calls that eventually invokes itself is called indirect recursion. Look at the example below of indirect recursion:
``````<?php
function A(\$num) {
\$num -= 1;
if(\$num > 0) {
echo "A is Calling B(\$num)n";
\$num = B(\$num);
}
return \$num;
}

function B(\$num) {
\$num -= 2;
if(\$num > 0) {
echo "B is Calling A(\$num)n";
\$num = A(\$num);
}
return \$num;
}

\$num = 4;
echo "Calling A(\$num)n";
echo 'Result: ' . A(\$num);``````
```Calling A(4)
A is Calling B(3)
B is Calling A(1)
Result: 0```
The above example is really useless code just meant to show you how a function can call itself indirectly through another function. Calling either `A(n>4)`
or `B(n>4)` causes the called function to be called from the other function. It’s important to know a function can call itself indirectly like this, but in this article we’ll only deal with direct recursion.

## A Practical Example

To show you how powerful recursion can be, we’ll write a function that searches for a key within an array and returns the result.
``````<?php
function find_in_arr(\$key, \$arr) {
foreach (\$arr as \$k => \$v) {
if (\$k == \$key) {
return \$v;
}
if (is_array(\$v)) {
foreach (\$v as \$_k => \$_v) {
if (\$_k == \$key) {
return \$_v;
}
}
}
}
return false;
}

\$arr = [
'name' => 'Php Master',
'subject' => 'Php',
'type' => 'Articles',
'items' => [
'one' => 'Iteration',
'two' => 'Recursion',
'methods' => [
'factorial' => 'Recursion',
'fibonacci' => 'Recursion',
],
],
'parent' => 'Sitepoint',
];

var_dump(
find_in_arr('two', \$arr),
find_in_arr('parent', \$arr),
find_in_arr('fibonacci', \$arr)
);``````
```string 'Recursion' (length=9)
string 'Sitepoint' (length=9)
boolean false```
Things are all well and good, but notice that we iterate only two levels deep into the array, and so the search for “Fibonacci” in the third level fails. If we want to search an array of indeterminate depth, this would not suffice. We can instead rewrite the search as a recursive function:
``````<?php
function find_in_arr(\$key, \$arr) {
foreach (\$arr as \$k => \$v) {
if (\$k == \$key) {
return \$v;
}
if (is_array(\$v)) {
\$result = find_in_arr(\$key, \$v);
if (\$result != false) {
return \$result;
}
}
}
return false;
}``````
With the recursive function, we can search an array several levels deep since we have not hardcoded how deep the function goes. It just keeps running until it goes over all of the values in the array.

## Head and Tail Recursion

In all of the examples so far we’ve been using what is called head recursion. When the function calls itself, it waits for the result from the call before returning a value of its own. It is possible to write functions in such a way that they do not operate on returned values, but instead pass all required values as parameters. This is known as a tail call (or tail recursion). This method is usually preferred as a language’s runtime can sometimes optimize the calls so that there’s no danger of blowing up the call stack, but PHP does not do this. Below is our factorial example modified to make a tail call. Note that the result of the recursive call is returned, instead of manipulated further.
``````<?php
function factorial (\$number, \$factorial = 1) {
if (\$number < 0) {
throw new InvalidArgumentException('Number cannot be less than zero (0)');
}
if (\$number == 0) {
return \$factorial;
}
else {
return factorial(\$number - 1, \$factorial * \$number);
}
}``````

Any code that can be written iteratively can also be written recursively. However, this is not always easy to do (or even wise to do). Recursion shines when traversing trees and lists or performing most O(n log n) sorts. When you need to divide a repetitive problem up, recursion will fit better than an iterative approach, as in the case of searching within the file system and you need to enter any subdirectories to search within as well. Where there’s the traversal of an indeterminate depth, recursion works great. Keep in mind that PHP does not optimize recursive functions, even if you write them to make tail calls, and recursive functions in general are less efficient and slower than their iterative counterparts, though they sometimes do the job better as shown in the code samples above. Recursion is usually a favored alternative to iteration in functional programming and therefore most functional languages optimize recursive functions. If you’re using XDebug, be sure to inspect your system’s configuration. By default you’ll have a limit of 100 recursive calls and if you exceed this, your script will throw a “maximum nested limit reached” error. You can update the `debug.max_nesting_level` config value if you need to change this. Finally, it’s a good idea to read an explanation of stack heap and recursion causing stack overflow to understand what happens to the call stack during recursion.

## Conclusion

In this article I’ve given you a broad look at recursion and how it compares to iteration. I’ve also show you how to write recursive functions, when to write them, and why. I have also tried warn you of some of the pitfalls that you might fall into when using recursion. Recursion is such that even many experienced programmers can go years without using it and many others have never even heard of it, which is sad because it is a truly powerful concept. I hope with this article I might have given you sufficient knowledge to go out there and start writing your own recursive functions. But remember that like with fire, you have to always be careful and use the tool wisely. Image by Alexandre Duret-Lutz via Flickr

## Frequently Asked Questions (FAQs) about Understanding Recursion in PHP

### What is the base case in a recursive function in PHP?

The base case in a recursive function is the condition that stops the function from calling itself indefinitely. It’s a crucial part of any recursive function. Without a base case, a recursive function would keep calling itself endlessly, leading to a stack overflow error. In PHP, the base case is usually defined using an ‘if’ statement at the beginning of the function. The function checks this condition before proceeding with the recursive call. If the condition is met, the function returns a value and stops calling itself.

### How does a recursive function work in PHP?

A recursive function in PHP works by calling itself within its own function body until a specified condition, known as the base case, is met. When a recursive function is called, it performs a specific task and then calls itself to repeat the task. This process continues until the base case is met, at which point the function stops calling itself. Each call to the function creates a new layer on the call stack, storing the variables and the return address for the function call. Once the base case is met, the function starts returning, unwinding the call stack layer by layer.

### Can all problems be solved using recursion in PHP?

While recursion can be a powerful tool in PHP, not all problems can or should be solved using recursion. Recursion is best suited for problems that can be broken down into smaller, similar problems, such as traversing a file directory or sorting an array. However, recursion can lead to high memory usage and stack overflow errors if not used carefully. It’s also generally slower than iterative solutions due to the overhead of function calls. Therefore, it’s important to understand the problem at hand and choose the right approach.

### How can I prevent stack overflow in recursive functions in PHP?

Stack overflow in recursive functions can be prevented by carefully defining a base case that the function will eventually reach. The base case is a condition that, when met, stops the function from making further recursive calls. Without a base case, the function would keep calling itself indefinitely, leading to a stack overflow. It’s also important to ensure that each recursive call brings the function closer to the base case, to avoid infinite recursion.

### What is tail recursion in PHP?

Tail recursion is a special kind of recursion where the recursive call is the last operation in the function. This means that there’s no need to keep track of the previous function calls, allowing the compiler or interpreter to optimize the recursion and reduce the risk of a stack overflow. However, PHP does not natively support tail recursion optimization. Therefore, while you can write tail-recursive functions in PHP, they won’t be optimized and will still consume stack space for each recursive call.

### How does recursion compare to loops in PHP?

Both recursion and loops can be used to repeat a set of instructions in PHP. However, they work in different ways and have different strengths and weaknesses. Recursion is a powerful tool for solving complex problems that can be broken down into smaller, similar problems. It’s particularly useful for tasks like traversing a tree or a graph. On the other hand, loops are generally more efficient for simple, repetitive tasks. They use less memory than recursion and are less likely to cause a stack overflow.

### Can I use recursion to traverse arrays in PHP?

Yes, recursion can be a very effective way to traverse arrays in PHP, especially multidimensional arrays. A recursive function can be used to iterate over each element in the array, and if an element is an array itself, the function can call itself to iterate over that array. This process continues until all elements have been visited. However, keep in mind that recursion can be slower and use more memory than an iterative solution, especially for large arrays.

### What is mutual recursion in PHP?

Mutual recursion occurs when two or more functions call each other in a cyclic manner. In PHP, this means that function A calls function B, and function B calls function A. This can be a powerful tool for solving certain types of problems, but it can also be more difficult to understand and debug than simple recursion. As with any recursive function, it’s important to define a base case to prevent infinite recursion.

### How can I debug a recursive function in PHP?

Debugging a recursive function in PHP can be challenging due to the function calling itself multiple times. However, there are several strategies you can use. One approach is to use print statements or a debugger to trace the function calls and see the state of the variables at each step. Another approach is to draw a recursion tree to visualize the function calls. It’s also important to carefully check the base case and the recursive case to ensure they are correct.

### Are there any limitations to using recursion in PHP?

While recursion can be a powerful tool in PHP, it does have some limitations. One of the main limitations is the risk of a stack overflow if the recursion goes too deep. This is because each recursive call adds a new layer to the call stack, and the stack size is limited. Recursion can also be slower and use more memory than an iterative solution due to the overhead of function calls. Furthermore, recursive functions can be more difficult to understand and debug than iterative solutions.

Stefan Froelich
View Author

Stefan "frostymarvelous" Froelich is a hobby programmer who loves to work with scripting languages. He's always up for a challenge and the opportunity to learn something new. At times he freelances, but mostly helps out in forums and various Q&A sites. His aim is to contribute to the community that has given so much to him over the years. Stefan dreams of a world where knowledge is freely shared.

Beginner