Recursion in computer science “is a method where the solution to a problem depends on solutions to smaller instances of the same problem“. (source: Wikipedia). In more practical terms recursion is an algorithm where a function can call itself. In PHP this is usually demonstrated with the well-known calculation of a factorial:

function factorial($num) {
  if ($num === 0) {
     return 1;
  }
  else {
     return $num * factorial($num-1);
  }
}
echo factorial(5);

In this example the factorial of 5 (5! or 5x4x3x2x1) = 120. As you can see the function factorial is called inside the function if the same name.

Other ways exist to arrive at the same result, one is by passing by referencing:

function factorial($num, &$total) {
    if($num > 0){
        $total = $total * $num;
        factorial($num - 1, $total);
    }
}
$total = 1;
factorial(5, $total);
echo $total; // results in 120

Note that the second argument in the function has to be variable. In another one a static variable is introduced.

function factorial($num) {
    static $total = 1;
    if($num > 0){
        $total = $total * $num;
        factorial($num - 1);
    }    
    return $total;
}
echo factorial(5); // results in 120

Note that in this type of construct all the code in the function is executed except the return. The result of the following piece of code is not 120 but 126:

function factorial($num) {
    static $total = 1;
    if($num > 0){
        $total = $total * $num;
        factorial($num - 1);
    } 
    $total++;
    return $total;
}
echo factorial(5); // results in 126

The calculation of e as the base of the natural logarithm requires the use of two different recursions. The recursion will converge towards 2.71 but will never quite reach it so the algorithm requires a stopper.

function factorial($n) {
  if ($n === 0) {
     return 1;
  }
  else {
     return $n * factorial($n-1);
  }
}

function reciprocal($n, &$total) {
    static $counter = 0;
    $counter++;
    if($counter < 20){
        $total += (1 / factorial($n + 1)); ;
     reciprocal( ($n + 1) , $total);
    }
}

$total = 1;
reciprocal(0, $total);
echo $total; // results in 2.718281828459

After 20 round the approximation is a fair 2.718281828459. Note that the function reciprocal() uses the static method. Recursion method one invariably results in excess memory use and failure. Likewise because the function factorial() is called multiple times the static method fails because the variable cannot be reset.

Even the number 1 can be estimated. This code surprisingly yields 1 as 1/2 + 1/3 + 1/8 + 1/30 + 1/144 .. (to infinity):

function factorial($n) {
    if ($n === 0) {
        return 1;
    } else {
        return $n * factorial($n - 1);
    }
}

function reciprocal($n, &$total) {
    static $counter = 0;
    $counter++;
    if ($counter < 20) {
        $total += (1 / ( ($n + 2) * factorial($n) ) );
        reciprocal(($n + 1), $total);
    }
}
$total = 0;
reciprocal(0, $total);
echo $total; // results in 1

More multiple recursions can be found in the calculation of a Fibonacci number [1]:

function fibonacci($num) {
    if ($n == 1 || $n == 2) {
        return 1;
    } else {
        return fibonacci($num - 1) + fibonacci($num - 2);
    }
}
echo fibonacci(11);  // results in 89

Want some pie? Then do like Leibniz who showed a long time ago pi can be approximated as 4/1 - 4/3 + 4/5 - 4/7 .... as long as you go to infinity but we give the processor a rest after just 200 rounds.

function pie($n, &$total, $sign) {
    static $counter = 0;
    $counter++;
    if ($counter < 200) {
        if($sign == 0){
            $total = $total - 4 / $n;
        }else {
            $total = $total + 4 / $n;
        }
        $sign = ($sign)?0:1;
        pie(($n + 2), $total, $sign);
    }
}
$total = 0;
$sign = 1;
pie(1, $total, $sign);
echo $total; // results in 3.1466177474955

The result is as close to pie as you can get.

Addendum

Thus far we have been using a stopper but how about running the pie script indefinitely and from the php command line?

#!/usr/local/bin/php
<?php
function pie($n, &$total, $sign) {   
        if($sign == 0){
            $total -=  4 / $n;
        }else {
            $total +=  4 / $n;
        }
        echo $total . PHP_EOL;
        $sign = ($sign)?0:1;
        pie(($n + 2), $total, $sign);
}
$total = 0;
$sign = 1;
pie(1, $total, $sign);

Unfortunately a script like this will fail by memory size exhausted (Xampp). No amount of variation will change the outcome. On the other hand by reverting to a simple for-loop, the script will run happily for hours:

#!/usr/local/bin/php
<?php
$total = 0;
$sign = 1;
for ( $n = 1 ; $n < 1000000000; $n += 2){
    if($sign == 0){
            $total -=  4 / $n;
        }else {
            $total +=  4 / $n;
        }
        echo $total . PHP_EOL;

        $sign = ($sign)?0:1;
}

Best effort after 40 minutes: 3.141592. After one hour a firm 6 can be added. The memory_get_usage() flatlines.

Addendum II

Can recursion do anything useful? This command-line script will recursively echo all files starting from the current location:

#!/usr/local/bin/php
<?php
function fileContent($dir){
    $files = glob($dir . '/*');
    foreach($files as $file){
        echo $file . PHP_EOL;
        fileContent($file);
    }
}
$currentFolder = dirname(__FILE__);
fileContent($currentFolder);

1] http://www.lornajane.net/posts/2012/php-recursive-function-example-factorial-numbers

Advertisements