Reverse an array in PHP by using recursion

Let’s go back to a computer science textbook topic. Show you how to reverse an array in PHP without using any native array functions such as array_xxx().

Recursion

Recursion is a process in computer science to make a function call itself. The corresponding function is called recursive function. Certain complicated problems can be solved easily by using the recursive method.

The best way to understand the recursive function is to show you the example of Fibonacci nunmbers. The Fibonacci numbers can be defined as:

F(0) = 0, F(1) = 1
F(N) = F(N-1) + F(N-2) (N > 1)

The recursive function for the Fibonacci nunmbers is:

function F(int $n): int {
    if ($n == 0) return 0; // Stop condition
    if ($n == 1) return 1; // Stop condition
return F($n - 1) + F($n - 2);
}
echo 'F(18) = ' . F(18); // F(18) = 2584

The most important thing in a recursive function is the stop condition, where the function stops calling itself. In the code snippet above, there are two stop conditions:

if ($n == 0) return 0;

and

if ($n == 1) return 1;

These stop conditions are the cases for F(0) = 0 and F(1) = 1. When N > 1, the recursive function calls itself and returns the value of F($n - 1) + F($n - 2). If no stop condition is defined, a recursive function can run into the problem of infinite resursion. This is like the case of infinite looping.

Reversing an array

This is an example of using recursion to reverse an array without using the native array functions, i.e. array_xxx(), in PHP.

We define a recursive function called reverseArray(array $array) to reverse an array. It iterates over an input array and reverses each element's position by calling the function insertToFront() where each element read from the input array is put in the front of the return array $result.

function reverseArray(array $array) {
    $result = [];
    foreach ($array as $key => $value) {
        // check if it is an array
        if (is_array($value)) {
            // insert into the front of the result array
            $result =  insertToFront($key, reverseArray($value), $result);
            continue;
        }      
        $result = insertToFront($key, $value, $result);  
    }
    return $result;
}

In the recursive function reverseArray(array $array), the stop condition is when the element's value type is not an array. Each iterated array element is put to the front of the return array $result in turn:

$result = insertToFront($key, $value, $result);

If the element’s value type is an array, the recursive function is called to reverse this array:

$result =  insertToFront($key, reverseArray($value), $result);

The processure of putting an array element to the front of the return array is as below:

function insertToFront($key, $value, $array) {
$result = [];
    // insert into the front of the result array 
    $result[$key] = $value;
// append all the rest data
    foreach ($array as $oldKey => $oldValue) {
        $result[$oldKey] = $oldValue;
    }
return $result;
}

To test the recursive function reverseArray(array $array), first, let's test with the indexed array:

// Indexed array
$inputArray = [1, 2, 3, 4, 5];
echo 'Before Reverse:' . PHP_EOL;
var_dump($inputArray);
echo 'After Reverse:' . PHP_EOL;
var_dump(reverseArray($inputArray));

The output is:

Before Reverse:
array (size=5)
  0 => int 1
  1 => int 2
  2 => int 3
  3 => int 4
  4 => int 5
After Reverse:
array (size=5)
  4 => int 5
  3 => int 4
  2 => int 3
  1 => int 2
  0 => int 1

Then we can test the associative array:

// Associative array
$inputArray = ['a' => 1, 'b' => 2, 'c' => 3, 'd' => 4, 'e' => 5];
echo 'Before Reverse:' . PHP_EOL;
var_dump($inputArray);
echo 'After Reverse:' . PHP_EOL;
var_dump(reverseArray($inputArray));

The output is:

Before Reverse:
array (size=5)
  'a' => int 1
  'b' => int 2
  'c' => int 3
  'd' => int 4
  'e' => int 5
After Reverse:
array (size=5)
  'e' => int 5
  'd' => int 4
  'c' => int 3
  'b' => int 2
  'a' => int 1
array (size=5)
  'e' => int 5
  'd' => int 4
  'c' => int 3
  'b' => int 2
  'a' => int 1

Last, let’s try a multidimensional case:

$inputArray = ['a' => [1, 2, 'a' => ['a', 'b' => ['a', 'b', 'c', 'd' => [1, 2, 3]], 'c'], 3], 2, 'c' => 'e', 4, 5];

In order to show all data, you need to set the configurable variables at runtime as below before the function var_dump() is called.

// set configurable variables in php.ini at runtime
// for var_dump() showing all data
ini_set('xdebug.var_display_max_depth', -1);
ini_set('xdebug.var_display_max_children', -1);
ini_set('xdebug.var_display_max_data', -1);

echo 'Before Reverse:' . PHP_EOL;
var_dump($inputArray);
echo 'After Reverse:' . PHP_EOL;
var_dump(reverseArray($inputArray));

The output is:

Before Reverse:
array (size=5)
  'a' => 
    array (size=4)
      0 => int 1
      1 => int 2
      'a' => 
        array (size=3)
          0 => string 'a' (length=1)
          'b' => 
            array (size=4)
              0 => string 'a' (length=1)
              1 => string 'b' (length=1)
              2 => string 'c' (length=1)
              'd' => 
                array (size=3)
                  0 => int 1
                  1 => int 2
                  2 => int 3
          1 => string 'c' (length=1)
      2 => int 3
  0 => int 2
  'c' => string 'e' (length=1)
  1 => int 4
  2 => int 5
After Reverse:
array (size=5)
  2 => int 5
  1 => int 4
  'c' => string 'e' (length=1)
  0 => int 2
  'a' => 
    array (size=4)
      2 => int 3
      'a' => 
        array (size=3)
          1 => string 'c' (length=1)
          'b' => 
            array (size=4)
              'd' => 
                array (size=3)
                  2 => int 3
                  1 => int 2
                  0 => int 1
              2 => string 'c' (length=1)
              1 => string 'b' (length=1)
              0 => string 'a' (length=1)
          0 => string 'a' (length=1)
      1 => int 2
      0 => int 1

Although this example is for reversing an array in PHP, it can give you a practical example for handling hierarchical data structure, e.g. file directory and tree, by using recursion.

Resources

• Fibonacci nunmber

Thanks for reading! To find more programming tutorials, please visit: CodeBilby.com