Question 276349 in PHP Question posted in
Official manual can be found here.

PHP: Why does recursion take so long

I have two pieces of code that calculate the Fibonacci sequence at a given index. One uses recursion, the other uses an array. It runs both functions and echoes out the time it takes to calculate each one:

<?php
//Calculate the index recursively
function fibonacciRecursiveAtIndex($num){
$num = 0 and $num = 1
    if($num == 0){
        return 0;
    } else if ($num == 1){
        return 1;
    } else {
        return fibonacciRecursiveAtIndex($num-1) + fibonacciRecursiveAtIndex($num-2);
    }
}

//Calculate non-recursively
function fibonacciAtIndex($num){
    $fibonacciArray = [0, 1];

    for($i = 2; $i < $num + 1; $i++){
        array_push($fibonacciArray, $fibonacciArray[$i - 1] + $fibonacciArray[$i - 2]);
    }
    
    return $fibonacciArray[$num];
}

//Recursion becomes noticeably slower for an index value above 15
$indexToCalculate = 40;

//Plug index into the fibonacciRecursiveAtIndex() function and output calculation time. 
$timeStart = microtime(true);
$valueAtIndex = fibonacciRecursiveAtIndex($indexToCalculate);
$timeEnd = microtime(true);
echo "Recursive(" . $indexToCalculate . ") = " . $valueAtIndex . " -- calculated in " . round(($timeEnd - $timeStart),7) . " s";

echo "<br><br>";

//Plug index into the fibonacciAtIndex() function and output calculation time. 
//The calculated time is several orders of magnitudes faster for large indices (index > 15).
$timeStart = microtime(true);
$valueAtIndex = fibonacciAtIndex($indexToCalculate);
$timeEnd = microtime(true);

echo "Fibonacci(" . $indexToCalculate . ") = " . $valueAtIndex . " -- calculated in " . round(($timeEnd - $timeStart),7) . " s";

Running this to calculate the fibbonaci sequence at index 40 takes around 4 seconds for recursion, but the array method takes roughly the same amount of time to calculate the index at 40 as it does for 4 (i.e. on the order of microseconds).

What is the principle behind this behavior and how does it apply here?

Tags:

2

Answers


  1. 0

    Because your recursion approach has a time complexity of O(2^n) whereas your array method has the time complexity of O(n) where n is the no. of elements in the Fibonacci sequence.

    Recursion calculates the same subproblems over and over again. For example,

     fibo(5) = fibo(4) + fibo(3)
 fibo(4) = fibo(3) + fibo(2)
 fibo(3) = fibo(2) + fibo(1)

    As you can see above, fibo(3) gets computed more than once and so does fibo(2). If you trace down the fibo for large numbers, you will notice many computations of the same subproblems over and over again making the time complexity higher and exponential.

    Hence, your recursive approach takes more time than the loop one.

    In your array approach, no subproblem is computed more than once since the results are cached thereafter making it more efficient than the recursion one.

    Note: You can however make the recursion function efficient by memoizing (caching) the subproblems’ results. This way, it will have the same time complexity as your array approach but might still be a bit slow(negligible difference in terms of milliseconds) because of the recursive call stack that needs to be maintained.

    Login or Signup to reply.
  2. 0

    Your code returns a 500 error for me on line 5, but at a glance, your recursive method is constantly asking if $num = 0 or 1 in each loop whereas the array method is declaring the first 2 steps, and then only starting the loop at the 3rd check without ever asking again if $num == 0 or 1 again.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search