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, Jul 15 '15 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, Jul 15 '15 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, Jul 15 '15 at 12:38
increase the xdebug.max_nesting_level. Check the answer here http://stackoverflow.com/questions/17488505/php-error-maximum-function-nesting-level-of-100-reached-aborting — kdlcruz, Jul 15 '15 at 12:39
@kdlcruz I don't have xdebug right now, so that can't be the problem — henry300, Jul 15 '15 at 12:49
With memory_limit set to 64M I got to `278518`. Execution time was < 2sec. Have you tried it with error_reporting=E_ALL and watching the error.log file? (for reproduction: which version of ubuntu?) — VolkerK, Jul 15 '15 at 12:49
@frz3993 The execution time is around 0.02 seconds for 20000 loops. That's not the worst I think — henry300, Jul 15 '15 at 12:51
@VolkerK Ubuntu version is 14.04.2 LTS. Haven't looked my error.log yet. Gonna do it now. — henry300, Jul 15 '15 at 12:53
Just to be on the safe side: I mean the file specified by the `error_log=....` directive in your php.ini ;-) — VolkerK, Jul 15 '15 at 12:55
@VolkerK Checked my file specified by the `error_log=...` but nothing related was in it. — henry300, Jul 15 '15 at 13:39
I suspect the reason it stops in the middle of the number above, printing only `13`, is because the rest of the output was buffered and never sent when your code overflowed the stack with too much recursion. Try adding `ob_flush()` after the `echo` statement to get the full output. — Lithis, Jul 15 '15 at 15:41

score 1 · Accepted Answer · edited May 23 '17 at 12:03

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?.

PHP stops executing after specific amount of recursion loops

1 Answers1