What is recursive function in PHP?

Defining Recursive function

Recursion is a programming approach in which a function calls itself and the function is called a recursive function. This function call is made until a certain condition is met. This has to be handled very carefully to avoid infinite loops.

Understanding the factorial example

To understand how recursive functions work, we will briefly use the factorial example.

In mathematics factorial of a number is the product of all positive numbers less than or equal to a number.

The formula is:

n! = n x (n-1) x (n-2) x (n-3) x ….x 3 x 2 x 1

So factorial of 5 is:

5! = 5 x (5 - 1) x (5 - 2) x (5 - 3) x (5 - 4) = 120

Now we will implement the factorial function in PHP. First, we will implement it using loops and then we will implement it using recursion.

Implementation using loop

<?php
function factorials($n)    
{    
    $p = 1;
    for($i=$n; $i>0; $i--){    
       $p = $p*$i;    
    }
    return $p;
}        
echo factorials(5);   
?>

The output is: 120

Implementation using recursive function

<?php
function factorial($n)    
{    
    if ($n < 0)    
        return -1;   
    if ($n == 0)    
        return 1;    
    return ($n * factorial ($n -1));    
}        
echo factorial(5);  
?>

The output is: 120

From the above code, we can see that we have called the factorial function from within the factorial function.

From the above example, we can see that reading a recursive function is more convenient than using a loop and this is one of the advantages of using a recursive function. But in this case, using a recursive function will take more time than the code using a loop.

When to use recursive function?

Recursive functions are very useful for mathematical calculations, traversing a tree, searching and sorting algorithms, and more complex requirements.

Example of traversing a tree using recursive function

We will traverse a tree-like structure using a recursive function here to understand the advantage with an example.

We will take a tree structure with Category A at the top level and two children under it – Category B and Category C.
Category B has 2 children under it – Category D and Category E.
Category C has 1 child under it – Category F

The tree diagram is as follows:

Now considering the above tree structure we can replicate this tree structure in the following array in PHP as in the following code:

$cat = [
	'Category A'=>['parent_name' => ''], 
        'Category B'=>['parent_name' => 'Category A'], 
        'Category C'=>['parent_name' => 'Category A'], 
        'Category D'=>['parent_name' => 'Category B'], 
        'Category E'=>['parent_name' => 'Category B'], 
        'Category F'=>['parent_name' => 'Category C']
       ];

Now let’s say we have such a category tree structure on our website and category-specific posts can be searched. That is, if there is a URL like this: http://<SITEURL>/category/Category E then we display all the records of this category on that page. We can use breadcrumbs to understand which category this category is under.
The expected breadcrumbs might look like this:

Category A -> Category B -> Category E

We can implement the above breadcrumbs using recursive functions.

<?php
function breadcumb($arr, $key, $new_arr=[]){
	if($key == '') return array_reverse($new_arr);
	if(array_key_exists($key, $arr)){
		array_push($new_arr, $key);
		return breadcumb($arr, $arr[$key]['parent_category'], $new_arr);
	}
}
$cat = [
	'Category A'=>['parent_category' => ''], 
        'Category B'=>['parent_category' => 'Category A'], 
        'Category C'=>['parent_category' => 'Category A'], 
        'Category D'=>['parent_category' => 'Category B'], 
        'Category E'=>['parent_category' => 'Category B'], 
        'Category F'=>['parent_category' => 'Category C']
       ];
echo implode(" -> ", breadcumb($cat, 'Category E'));
?>

The output is: Category A -> Category B -> Category E

Here the breadcrumbs function is called from within that function until $key equals empty. As long as $key is not equal to empty then the category is pushed to an array and the recursive function is called.

Here Category A is the topmost category so its parent_category is empty and so the recursive function is called up to the parent_category of CategoryA. And since parent_category is empty, the $key equals to empty condition is satisfied and the array is returned after reversing.

Thus we can traverse the tree structure up to the nth level using recursive functions.

Advantages and Disadvantages

The advantages and disadvantages of the recursive function are listed below:

Advantages

Recursive function is used to write clear, readable, and understandable code.
Recursive functions are extremely effective for mathematical calculations, traversing a tree, searching and sorting algorithms, and more complex requirements.

Disadvantages

Recursive function uses more memory than iterative approach as in recursive function, the function is added to the stack memory with each recursion call, and remains in memory until the call ends.
Recursive functions are slower than iterative ones as for recursion, the function is added to the new stack memory with each recursion call.

Table of Contents