递归会导致内存使用量激增

Question

function rec_func($x) {   
   echo $x;
   if ($x < 1000) {
      $x++;
      rec_func(&$x);
   }
}

This is not the actual recursive function, that I am going to be using for my PHP script. Just like this example, my real function works perfectly fine, up to the point where I start examining how much memory is it using.

If I loop this function, say, a 100 times, nothing bad happens. The used memory in each iteration stays the same. But If I loop 1000 times and more, at one point this function will start consuming more memory than before, right up to the last iteration.

The amount of spikes seem to depend on how big is the variable I give it, and how many iterations it goes through, but I can't be certain. And this is where the problem begins. This function will start consuming more memory just once in a 1000 times. My function, however, does this every 150 or so times in 1000 iterations, and the worst thing is that MY function may have to loop even more times than that.

This made me curious, because the obvious thing to do would be to use a traditional loop instead (which I have done), but I really want to understand why is this happening, and if it can be avoided.

P.S. note that I'm using a real variable only in the first iteration and all of the iterations following it are using a reference, to preserve memory. Thanks in advance.

Answer 1

(correct me if I am wrong). I think, it is related with your PHP module memory handling: It does reserve some memory when it starts running (if it is used as CGI for example, or you call it from a command prompt).

Every time when you start a recursion, it will do two things basically:

Before calling the next level of recursion, saves the current status to the call stack. If you are not manipulating with references, then the variable data as well, with the current stack state. As long as the reserved memory is enough, your memory consumption will not be increased, but when you run out of memory, a new bunch of memory will be reserved, in order if more will be needed. It means the following:

function rec_func($x) {   
   echo $x;
   if ($x < 1000) {
      $x++;
      rec_func($x);
   }
}

This will have a significant bigger memory usage, as every time a recursion occures, there will be an extra line in the stack, and you will create an extra $x in the memory to store it's current state, in order to reserve the value when the recursion get's back to the current stack call.

The following lines will get rid of the memory usage problem - it manipulates with variable references (obviously ruins the functionality in this case:

function rec_func(&$x) {   
   echo $x;
   if ($x < 1000) {
      $x++;
      rec_func($x);
   }
}

(your original code causes fatal error due to call-time reference passing).

In case if you want to reduce the memory usage, you should (or can) use references in the function declaration for variables, which will not change during the recursion, but never do that with variables, that change meanwhile.

You can try it out yourself by playing with debug_zval_dump(), like this:

<?php
function rec_func_ref(&$x) {  
   //echo $x;
   if ($x < 100000) {
      $x++;
      rec_func_ref($x);
   }
  echo 'rec_func_ref:'.$x.'------<br />';
  debug_zval_dump($x);
  echo "<br />";
}

function rec_func_not_ref($x) {  
   //echo $x;
   if ($x < 100000) {
      $x++;
      rec_func_not_ref($x);
   }
  echo 'rec_func_not_ref:'.$x.'------<br />';
  debug_zval_dump($x);
  echo "<br />";
}


$a = 1;
rec_func_ref($a);
$a = 1;
rec_func_not_ref($a);
?>