Recursive Referenced Use-Variables

[iwato]

Question One: Are the following two statements true? If not, please explain.

• A return statement can be executed only once in any function.
• The referenced use variable &$fib permits the function fib($n) to call itself. Without this reference the recursiveness cannot take place.

Question Two: Could someone please explain how the expression $fib($n - 1) + $fib($n - 2) drives the function $fib($n) and generates the below set of output when the second set of code is run.First Code Set

<?php	$fib = function($n) use(&$fib) {		if($n == 0 || $n == 1) {			return 1;		}		return $fib($n - 1) + $fib($n - 2);	};?>

Second Code Set

for ($i=1; $i<=10; $i++) {	echo "$i: ", $fib($i), '<br />';}

The Generated Output for $n = 1 thru 10

1: 12: 23: 34: 55: 86: 137: 218: 349: 5510: 89

Roddy

[boen_robot]

1.a. I guess you could say that... a return statement terminates the current function and gives a certain returned value to it. The fact that you can execute it only once is a consequence of the termination.1.b. Yes. For an anonymous function to call itself, it needs to somehow get access to itself, which can happen by it being passed in the "use" statement. I haven't worked enough with closures in PHP to know if/why the reference in this case is significant though.2. Plain ol' recursion style? Each execution context is placed in a stack that eventually reaches its ending conditions, after which the execution contexts start to get out of the stack, doing the calculations along the way.

[iwato]

2. Plain ol' recursion style? Each execution context is placed in a stack that eventually reaches its ending conditions, after which the execution contexts start to get out of the stack, doing the calculations along the way.

"Plain ol' recursion style?" If only, I understood.Take a small number like 6 and run it through to its end for me would you?Roddy

[boen_robot]

Fibonacci is a little more complex than what I'm willing to go over, so I'll use the other common recursion example - factorial, and this sample implementation:

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

(slightly modified from the example in the Wikipedia article on recursion)So for example in factorial(3):1. You're in the main scope and execute factorial(3). This call is added to the "execution stack".2. The condition is checked for. It's not met so we go to the else.3. Return is about to terminate the function with a certain value that will be computed in the expression.4. "$n *" is evaluated to "3 *", after which the factorial() function is about to be called. Its return value is expected to be the second operand of "*".5. The arguments of the function are processed before the call. "$n-1" is evaluated to 2.6. factorial(2) is being called. Again, it is added into the execution stack.7. (same as 2.)8. (same as 3.)9. "$n *" is evaluated to "2 *", after which the factorial() function is about to be called. Its return value is expected to be the second operand of "*".10. The arguments of the function are processed before the call. "$n-1" is evaluated to 1.11. factorial(1) is being called. Again, it is added into the execution stack.12..... here's where it gets interesting.... The condition is checked for. 1 is indeed "less than or equal" to 1, so factorial(1) returns 1.13. factorial(1) is pulled off from the execution stack, and the returned value is added to the next function in the stack at the point where the control was previously passed. In other words, right at the return statement of factorial(2).14. The whole expression in the return statement of factorial(2) now reads "2 * 1", and is evaluated as "2". This becomes the returned value of factorial(2).15. factorial(2) is pulled off from the execution stack, and the returned value is added to the next function in the stack at the point where the control was previously passed. In other words, right at the return statement of factorial(3).16. The whole expression in the return statement of factorial(3) now reads "3 * 2", and is evaluated as "6". This becomes the returned value of factorial(3).17. factorial(2) is pulled off from the execution stack, and the returned value is added to the next function in the stack at the point where the control was previously passed. In other words, right at the main scope where factorial(3) was called.Closures or not, that's just the way function calling and recursion work.

[iwato]

. . . that's just the way function calling and recursion work.

Thank you for introducing me to the notion of a stack. The concept of FIFO, and the push and pop operations are fairly easy to understand for someone with my increasing knowledge of PHP's array functions. This said, how to you explain the sudden reversal from ascending to descending numerical order generated by the following piece of code? Indeed, once $a reaches 10, the if-statement should become irrelevant, and the function should nothing left to do.The Code

function recursion($a) {	if ($a < 10) {		echo "$a<br />";		recursion($a + 1);		echo "$a<br />";	}}recursion(8);

The Output

8998

Roddy

[boen_robot]

Perhaps instead of "In other words", I should've used "In this case", because in this new case you're outlining, it's the same deal, only instead of instantly returning to the previous function's return statement, you're simply resuming the execution of the next function in the stack.So... think about that... Every time before the next recursive call, you have an echo that prints the numbers, in this case 8 and 9. When the exit condition is met, the last function in the execution stack terminates with no return value, and the next one in the stack resumes. You then have one more echo before that function also ends (again with no return value), and is therefore also popped from the stack. That echo outputs the value of $a in the current execution context. Since items got in the stack in the order "8, 9", they get out in the order "9, 8".You might want to check out call stack on Wikipedia... the term "execution stack" I used is another synonym.