PHP stops executing after specific amount of recursion loops

Question

The problem which I encounter is very odd. It happens when doing recursion loops. It doesn't happen when doing the same task using for loop or any other iteration.

Everything works when calling a function recursively under ~21 000 times. The problem occurs when exeeding this number.

My working code:

foo();

function foo($i = 1) {
    if ($i > 20000) {
         return;
    }
    echo $i . '<br/>';
    foo($i + 1);

    return;        
}

Outputs:
...
19998
19999
20000

Not working code:

foo();

function foo($i = 1) {
    if ($i > 30000) {  // Or any number above ~21000
         return;
    }
    echo $i . '<br/>';
    foo($i + 1);

    return;        
}

Outputs:
...
13493
13494
13

Last row stops in the middle of the number. In some cases it just sends an empty response to the server.

I am using apache2 server on Ubuntu with PHP Version 5.6.10. Using Xampp, same problem occurs, only numbers are a little different.

Sounds like a memory problem. Try changing your maximum memory settings, restarting Apache, and running your code again. — elixenide
– elixenide, Commented Jul 15, 2015 at 12:35
Is there a real life scenario where you would need 30K of recursive calls? Sounds like simple loop would do solve the issue much more efficiently here. — martynasma
– martynasma, Commented Jul 15, 2015 at 12:37
how much memory is each script allowed to use? i think the default is 128 so you might want to change it to 256 or maybe even higher if you think its needed. check your PHP ini for "memory_limit" — lauw
– lauw, Commented Jul 15, 2015 at 12:38
increase the xdebug.max_nesting_level. Check the answer here stackoverflow.com/questions/17488505/… — kdlcruz
– kdlcruz, Commented Jul 15, 2015 at 12:39

Community · Accepted Answer · 2017-05-23 12:03:50Z

In most currently popular programming languages, including PHP, there is a limit to how much recursion a function can perform. It is not a hard limit; depending on the state of your program, it can be recursive calls tens of thousands deep or only a few deep. Thus it is not safe to implement deeply-recursive functions like your example, and your program will crash. See the note at the bottom of PHP's user-defined functions documentation:

Recursive function/method calls with over 100–200 recursion levels can smash the stack and cause a termination of the current script.

Every time you call a function, the program has to record where execution was before starting to execute the function, so it knows where to start executing again after the function returns. There is only a limited amount of space in which to store this information, so if you have too many function calls at the same time, it will run out of space and your program will crash. This information, along with a bunch of other information, is stored in the stack, and when you run out of space in the stack, it is called a stack overflow or smashing the stack.

Some languages implement a feature known as tail call optimization, which allows unlimited recursion under the right circumstances. Functional languages often support this, such as Scheme and ML. However, PHP does not, as mentioned in Does PHP optimize tail recursion?.

Collectives™ on Stack Overflow

PHP stops executing after specific amount of recursion loops

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related