# Find the factorial of a number using recursion?

Factorial is the product of all the integers below or equal to a given number. For example, that's how to calculate factorial 5:

5 x 4 x 3 x 2 x 1 = 120

Recursive function, in which a function calls itself, can perform the calculation. But if you try running the following function you'll get an error:

function calcFactorial($num)
{
  return ($num * calcFactorial($num-1)); 
}
calcFactorial(5);

Something like the one that I got on my computer:

Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 262144 bytes) in index.php on line 3

Why?

The error is the result of the function calling itself too many times because it has nothing that tells it to stop the execution.

From this we can learn that when using recursion it is essential to limit the number of calls that a function can make.

To fix the error we need to add a condition that stops the function from calling itself as soon as it reaches the value of 1:

function calcFactorial($num)
{
  if ($num <= 1) { 
    return 1; 
  } else { 
    return ($num * calcFactorial($num-1)); 
  } 	
}

echo calcFactorial(5);

• Once the function reaches 1, instead of calling itself it returns 1.

This way we prevented a fatal error while receiving the right answer.

In summary, a recursive function calls itself until it meets a stopping condition.

A recursive function calls itself until it meets a stopping condition.

# Why is it better not to use recursion?

An alternative approach for solving the factorial is to use a loop instead. E.g., a for loop:

function calcFactorial($num)
{
  $val = 1;
  for ($x = $num; $x >= 1; $x--) {
    $val *= $x;
  }
  
  return $val;
}

echo calcFactorial(5);

The loop runs from any integer ($num) to 1 while performing the operation sequentially. At the end of the calculation, the function returns the product of the integers.

Using a loop is cheaper in terms of computing than using recursion. This can prove itself most helpful when working on a real life system with limited resources.

From this we can learn that recursion should not be the default. It is better to use a loop if possible.

# When to use recursion?

There are cases where recursion is the simplest solution. Especially, in those cases where the data has the form of a tree with an unknown number of splits. For example, when performing operations on HTML where each node can have an unknown number of sub-nodes, or when working with XML or JSON.

The following example is of a JSON which contains items representing animal groups:

$animals = '{"animals":[
  {"name":"apes","parent":"mammals","link":"//animals.com/mammals/apes"},
  {"name":"fishes","parent":"animals","link":"//animals.com/fishes"},
  {"name":"animals","parent":"kingdom","link":"//animals.com"},
  {"name":"mammals","parent":"animals","link":"//animals.com/mammals"},
  {"name":"marsupials","parent":"mammals","link":"//animals.com/mammals/marsupials"},
  {"name":"opossums","parent":"marsupials","link":"//animals.com/mammals/marsupials/opossums"},
  {"name":"big apes","parent":"apes","link":"//animals.com/mammals/big-apes"},
  {"name":"birds","parent":"animals","link":"//animals.com/birds"},
  {"name":"cats","parent":"mammals","link":"//animals.com/mammals/cats"},
  {"name":"big cats","parent":"cats","link":"//animals.com/mammals/cats/big-cats"},
  {"name":"domestic cats","parent":"cats","link":"//animals.com/mammals/cats/domestic-cats"},
  {"name":"persian cats","parent":"domestic cats","link":"//animals.com/mammals/cats/domestic-cats/persian-cats"},
  {"name":"chimpanzee","parent":"big apes","link":"//animals.com/mammals/big-apes/chimpanzee"}
]}';

Each JSON item represents:

• The name of the group (E.g. chimpanzee)
• The name of the family to which the group belongs (E.g. apes)
• Link to an imaginary website which contains data about the item.

Our goal is to arrange the items in hierarchical order where the group of mammals is below the group of animals and above the group of apes, etc then display the result as menu items that preserve the order.

This is how it should look when we are done, a list containing several levels of sub-lists the number of which we do not know in advance:

A possible solution is to use two functions. The first, a recursive function, arranges the messy JSON in a hierarchical order. The second builds the links in the menu.

The name of the first recursive function is makeTree. It receives a multidimensional array and arranges it in a hierarchical order:

// recursive function to create the hierarchy
function makeTree($arr=[], $branch="") 

{
  $tree=[];
   
  foreach($arr as $item) {
    if($item["parent"] === $branch) {
      $item["children"]  = makeTree($arr,$item["name"]);
      $tree[$branch][] = $item;
    }
  }
 
  return $tree;
}

• The function receives two arguments:
  1. $arr - the array that the function needs to put in order
  2. $branch - the name of the branch that the function needs to find its immediate children (the items below it in the hierarchy)
• The function builds a multidimensional array, $tree, that includes all the children in a particular step.
• The function runs on the list of items in the array it receives ($arr) until it finds an item whose parent is the same as $branch.
• For the item that the function finds it searches for the it's children by further calling itself with the name of the current branch. A function that calls itself as long as a certain condition is met is a recursive function.
• Each of the children that the function finds is added to the multidimensional array $tree that the function generates in the process.
• Where is the stopping condition? The function calls itself only if an item has children.

The second function, makeNav, accepts as a parameter the ordered array that comes from the makeTree function then builds the HTML structure of a nested list (list within list):

// build the multilevel HTML
function makeNav($arr=[]) 

{
  $nav='<ul>';
  
  foreach($arr as $key => $val) {
    if($val["children"] && count($val["children"]) > 0) {
      $nav .= '<li>';
      $nav .= "<a href="{$val['link']}">{$val['name']}</a>";
      $nav .= '<ul>';
      foreach($val["children"] as $item) {
        $nav .= makeNav($item);
      }
      $nav .= '</ul>';
      $nav .= '</li>';
    } else {
      $nav .= '<li>';
      $nav .= "<a href="{$val['link']}">{$val['name']}</a>";
      $nav .= '</li>';
    }
  }
  $nav .= '</ul>';
	
  return $nav;
}

To generate the hierarchy, we call the makeTree recursive function. We then pass the result to the makeNav function to build the HTML structure:

$rootName = "kingdom";

$animalsArray = json_decode($animals, true);

$tree = makeTree($animalsArray["animals"], $rootName);

$nav  = makeNav($tree[$rootName]);

echo $nav;

The result:

# Recursive iteration over the filesystem in PHP

The file system may also have a structure that repeats itself an unknown number of times (folder within folder within folder), but if you encounter the problem then it is best to solve it using the PHP's built-in class recursive directory iterator.