Recursion function

[jimfog]

What follows is a recursion function for printing a string in reverse:

function reverse_r($str){ if (strlen($str)>0) reverse_r(substr($str, 1)); echo substr($str, 0, 1); return;}

From a point onwards i am really confused about this code progresses.Let me explain:Suppose the parameter is Hello-reverse_r('Hello');According to the if statement, the string is tested if it is bigger than, after that, the function is called again, until the if condition returns false(this happens when reverse_r(''),then code execution proceeds to the echo statement where it has nothing to echo since the string is empty.Then the return keyword is used to call the last instance of the function, namely reverse_r('o') which lead to reverse_r(''),SO FAR I UNDERSTAND THE CODE EXECUTION.Here on the problems begins, according to the author of the book, after the reverse_r('o') is called by the "return", o is printed by the echo statement.And then, all the previous instances of the function are called by the return keyword till olleh is printed(the reverse of hello)I do not understand the following point:When return calls reverse_r('o'), how 'o' can be printed SINCE AGAIN IT MUST PASS FROM THE IF CONDITION WHERE reverse_r('o') will be converted to reverse_r('').The return keyword, eventually, will call all the previous instances of the function till olleh is printed.HOW CAN THAT BE?SINCE EVERY TIME IT MUST PASS FROM THE IF CONDITION TILL WE HAVE reverse_r('').I would appreciate if someone could explain that to me.It is really confusing for me.

[dsonesuk]

You don't need the return? the echo takes place everytime the reverse function is called because the string length is greater than 0

function reverse_r($str){if (strlen($str)>0)reverse_r(substr($str, 1)); /* will call the function reverse_r('ello') , then  reverse_r('llo') and so on... until string length = 0 as in '' */echo substr($str, 0, 1); /* will display the first character from $str 'h' from 'hello' then 'e' from 'ello', and so on *///return;}

it is basically doing the same as

for($i=0;$i<5;$i++){echo $i;}

as the code loops it echo the current value to display, till you end up with '01234'

[jimfog]

You don't need the return? the echo takes place everytime the reverse function is called because the string length is greater than 0

function reverse_r($str){if (strlen($str)>0)reverse_r(substr($str, 1)); /* will call the function reverse_r('ello') , then  reverse_r('llo') and so on... until string length = 0 as in '' */echo substr($str, 0, 1); /* will display the first character from $str 'h' from 'hello' then 'e' from 'ello', and so on *///return;}

it is basically doing the same as

for($i=0;$i<5;$i++){echo $i;}

as the code loops it echo the current value to display, till you end up with '01234'

Ok, but, i run the code and the the reverse string is printedThe reverse of hello, meaning ollehHow that happens, it does not make sense.In your example hello is printed, not olleh as the author of the book AND the code i run did.

[ShadowMage]

DD, might beat me to it but here goes... (Nope, he didn't chime in. )The function is first called:reverse_r('hello');Inside the function, it checks if strlen is greater than 0. At this point it is. (It's 5). If the length is greater than 0, it calls itself (the reverse_r function) again and waits for that call to be finished before continuing with the code inside the first call. This continues until there is no string left, at which point, it starts printing out the letters, starting from the last call made, which would be reverse_r('o').Hopefully that made sense...

[jeffman]

Try executing this slightly modified version. It might help you see the way the recursions are "stacking up":

function reverse_r($str){   echo '$str now set to "' . $str . '"<br>';   if (strlen($str)>0) {	  echo 'I\'m passing "' . substr($str, 1) . '" to reverse_r <br><br>';	  reverse_r(substr($str, 1));   }   echo substr($str, 0, 1) . '<br>';   return;}

[jimfog]

Try executing this slightly modified version. It might help you see the way the recursions are "stacking up":

function reverse_r($str){   echo '$str now set to "' . $str . '"<br>';   if (strlen($str)>0) {	  echo 'I\'m passing "' . substr($str, 1) . '" to reverse_r <br><br>';	  reverse_r(substr($str, 1));   }   echo substr($str, 0, 1) . '<br>';   return;}

Your code does not work, i do not know why, i mean there is no output at all, not that it is flawed and cannot be used for demonstation purposes.Nonetheless, i am slowly beginning to grasp this concept of recursion.There are some details that i missed.First of all the functions are held to memory. I mean the recursion(not satisfied if condition) does not let the whole code to be executed but to be LET ON HOLD on the memory.So we have 5 functions in memory waiting to be executed. Are we ok with this?The second is, that when execution starts, it begins from the last function,(in case of reverse('hello')) this is reverse('o').I thought that execution would begun from reverse('hello'). Probably this order has to with the concept of stacking which i do not know-correct me if i am wrong.BUT MORE IMPORTANTLY-since function reverse('o') is where execution begins, i though it must pass again through the IF condition-this is the point that confused me the most.It seems that code execution does not PASS AGAIN from the if statement-BUT FROM WHERE IT STOPPED.Correct me if i am wrong-regarding the above.I was thinking all these in my bed till 1 a.mThat is why i like computers(and math) they make you think and keep the most important organ(our brains) in shape.

[jeffman]

Did you invoke the function with a statement like this:reverse_r("hello");? That's the only way to make it run.About your questions. As long as the amount of code waiting to be executed is not seriously enormous, recursing 5 times is pretty trivial. Yes, we are OK with this. 5000 iterations of 1000 mysql queries might be a problem. That's what testing is for. Execution does not begin with the last iteration. It begins with the first, which is the point of my demo. It seems like it begins with the last iteration, but only because all the echo statements come AFTER the recursive calls to reverse_r. That's when the stacking starts to unstack.In Iteration X of the function, execution passes to the next, to the next, and so on, and when execution returns to Iteration X, control resumes immediately after the call to reverse_r. So I think that's a yes to your "PASS AGAIN" question.I souped up the demo a little bit. Maybe this will run. If so, it should explain a little more.

<?php	function reverse_r($str)	{	   echo '$str now set to "' . $str . '"<br>';	   if (strlen($str)>0) {		  echo 'I\'m passing "' . substr($str, 1) . '" to reverse_r <br><br>';		  reverse_r(substr($str, 1));	   }	   else {		  echo '<br>Statements that follow recursive calls to reverse_r will now be executed<br><br>';	   }	   echo '$str now set to "' . $str . '"<br>';	   echo 'The first character of $str is: ';	   echo substr($str, 0, 1) . '<br><br>';	   return;	}	reverse_r("hello"); // to get the whole thing going?>

[justsomeguy]

So we have 5 functions in memory waiting to be executed.

What you're describing is the execution stack. There are several instances of the recursive function on the stack in various states of completion, waiting for the ones higher up on the stack to finish.http://en.wikipedia.org/wiki/Call_stack

Are we ok with this?

What does that mean? I think we are OK with this. We use the execution stack all the time, in every program, during every function call. This is normal for us. We have been doing this for a long time. Note that the wikipedia article doesn't even give a date the stack came about. As soon as languages started being able to call functions or subroutines, there was a need for something to keep it all straight. That's the stack.

I thought that execution would begun from reverse('hello').

It does. The recursion happens before the echo, which means that the function completely recurses before any output is sent. Since the recursion happens before the output, you can visualize the execution flow like this:

reverse('hello')  reverse('ello')	reverse('llo')	  reverse('lo')		reverse('o')		echo 'o'	  echo 'l'	echo 'l'  echo 'e'echo 'h'

If you move the echo statement before the recursive call, you'll see a different result.

BUT MORE IMPORTANTLY-since function reverse('o') is where execution begins

That's not where execution begins, that's where output begins (for the reasons above). Execution begins and finishes with the first one you call. The call to reverse('hello') is the first one to start and the last one to finish.

[jimfog]

At last, i got it. These 2 last posts revealed all the details surrounding the recursion mechanism.Probably, not other concept, such as this, has confused me so much when it comes to studying PHP.Thanks both of you.Has any of you studied computer science?With so much brain food it is unlikely i will suffer from Alzheimer's disease in my life. :)By the way, DD, your code worked this time.

[jeffman]

JSG studied has Computer Science formally. (boenrobot, too. I'm not sure who else.) I have not, but I seem to know more about it than a lot of web developers.I'm not sure if you know this, but a lot of CompSci involves the underlying engineering of chips/hardware/etc., learning how to program in Assembly language, and other things that web developers can benefit from in an indirect way that's hard to pin down most of the time. Computer Scientists also study ways of making data structures efficient, and algorithms for performing repetitive tasks most efficiently. Like, if you ever have to search a big database, it was a computer scientist who wrote and benchmarked the underlying search algorithms so that you don't have to. Computer Scientists also learn about models of project development. A lot of freelance web developers just kind of jump into a project (bad idea) but there are tested models (waterfall, spiral, and some others) that have advantages in some contexts and disadvantages in others. If you're a developer working in a corporate environment, unless you're a team manager, you could go for years without knowing what development model you're actually a part of on any given project.You can learn more than the average web developer just by downloading a simple, free C compiler and teaching yourself that language. All you want is something that generates simple programs that run in a blank window--no GUI to confuse you. PHP is derived from C, so the syntax will be familiar. The important things you will learn have to do with the way computers use memory, and how memory is related to data structures, like strings and arrays. You'll be amazed at the kinds of things high-level languages like PHP are hiding from you to simplify your life.

[iwato]

At last, i got it ....

This is a variation on your function that you might find useful. It goes just a little further than the PHP strrev() function and makes could use of the reverse_r() function discussed in this topic.If you enter only $str, the function returns the same string in reversed order that you can either echo or use elsewhere.If you enter str_rev($str, 1), the function returns an array containing the elements of the input string in reverse order. Thus, you have reversal with format conversion.

<?php	function str_rev($str, $format = 0, $str_arr = array()) {		if (strlen($str)>0) {			str_rev(substr($str, 1), $format, &$str_arr);			array_push($str_arr, substr($str, 0, 1));					}		if ($format == 0) {			return implode($str_arr);		}		if ($format == 1) {			return $str_arr;		};	}?>

Roddy