Avatar of CrazyOne
CrazyOneFlag for United States of America

asked on 

Recursion

Ok I have some fundamental understanding of recursion. Basically it’s a loop. What I don’t understand is for example in the following code is how does the return keep updating its calculations without refreshing itself with every loop. In other words how does it not lose its value after every iteration through itself? Also with the following code eventually the value will count down to 0 so why does it not return 0 being that the first statement is set to return a 0 if 0 is detected.

For example if I pass the value 3 as the parameter the method returns 6 which is the correct return. However after each iteration the value of the parameter is reduced by 1 eventually reaching 0. Now after it reaches 0 shouldn’t the Base case statement be processed and the return be 0?

FYI this isn’t for a school project it is for my personal understanding. The semester is over but I still feel I need to increase my understanding of how and why recursion does what it does before I am able to be comfortable with using it.
public static int mystery (int n) 
   {
	 
	  if (n == 0)
		 return 0;
	  else
		 return n + mystery(n-1);
	  
	  //The following is an exampler of what recursion looks like using a loop instead
	 /* int intCount = n;
	  if (intCount == 0)
		 return 0;
	  else
	  {
		 while (n != 0)
		 {
			intCount = intCount  + n-1;
			n--;
		 }
		 //return n + mystery(n-1);
	  }
	  return intCount;*/
   }

Open in new window

Java

Avatar of undefined
Last Comment
webdev2000
Avatar of mrjoltcola
mrjoltcola
Flag of United States of America image

Well that is because recursion isn't really a loop (I mean in spirit it is but not really).

A loop would be simple iteration of the same code without changing of context (stack, etc.). Each iteration uses the same variables.

Recursion is calling of same code while changing the context (pushing local vars, etc.) so each iteration uses a new set of variables (on the stack). Each call of the same function gets its own copy of the named variables.

You must do some reading on "execution context".

Code is made up of 2 things, executable instructions and context. It is the context where your different versions of the same variables are stored.
Avatar of mrjoltcola
mrjoltcola
Flag of United States of America image

Call mystery(3)

   Push n (3) on the stack.
   Jump (call) mystery function.
   mystery has 3 as a value of n

   Call mystery(n)
   Push n (2) on the stack.
   Jump (call) mystery function.
   mystery has 2 as value of n

   ...

   Unwind of stack happens
   return (pops previous n 2 off stack)
   return (pops previous n 3 off stack)
   ..


Some languages have what is called "tail" recursion, which says if your self-call of mystery() is the last statement in the function, it allows the unwind step to be skipped (optimized away) because the function call can skip the stack manipulation since there is no more code after that statement. So if your recursion had self-called 1000 times, you would have skipped 1000 pushes to save the local value of n for the next call of your function. But this is an hidden implementation detail. In spirit, each call gets a new (n)
Avatar of for_yan
for_yan
Flag of United States of America image

And it does not return 0, because by the time you get into this method
with argument zero, you already summed up all prevuuous guys and it retutns the last one as zero
and you sum it to waht you alredy have, the total result will not be zero.
It will be zero only if zero step is very fisrt one in your summation
and then you'll get that f(0)=0, which will be correct.
Avatar of mrjoltcola
mrjoltcola
Flag of United States of America image

>>@for_yan: because by the time you get into this method with argument zero, you already summed up all prevuuous guys and it retutns the last one as zero

Actually this is incorrect. The way recursion works is that the evaluation (summing up all previous guys) doesn't happen in theory, until the last call returns. Then as the stack unwinds, the summation happens.

   return n + mystery(n-1);    <-- The "n +" part doesnt happen until the very final "return 0" happens.


  return 0;   // at this point, we have n of 3, 2, 1 all stored on the stack. As the last one returns, all the adds are executed

(Though tail recursion can optimize this away)
Avatar of for_yan
for_yan
Flag of United States of America image

I agree, I used incorrect wording
Avatar of mrjoltcola
mrjoltcola
Flag of United States of America image

Hey, CrazyOne, you are a car nut, and you know carburetors and turbos.

Recursion is like if your exhaust fed into your intake. The air is your data, the engine is your code. :)
Avatar of mrjoltcola
mrjoltcola
Flag of United States of America image

>>I agree, I used incorrect wording

Well, if the compiler does tail-call optimization, you would be correct. But that is an implementation detail that I wanted to be clear, not to confuse the asker.
Avatar of for_yan
for_yan
Flag of United States of America image

Yes, but you are right, it is easier to understand, if we say that we have them all prepared for summation, so that even the last one is zero, but the total becomes something - to address this piece of the asker's question
Avatar of CrazyOne
CrazyOne
Flag of United States of America image

ASKER

Ok cool so in a sense when the recursion gets to 0 am I correct in assuming at this point it checks to see if the stack is empty and if it is not then it pops each element one at a time and in this case adds each of those element together, and returns the summed value to the caller?
Avatar of for_yan
for_yan
Flag of United States of America image

What you are saying seems to make sense to me, let's wait waht mrjoltcola says - he obviously understands this stuff much better.
ASKER CERTIFIED SOLUTION
Avatar of mrjoltcola
mrjoltcola
Flag of United States of America image

Blurred text
THIS SOLUTION IS ONLY AVAILABLE TO MEMBERS.
View this solution by signing up for a free trial.
Members can start a 7-Day free trial and enjoy unlimited access to the platform.
See Pricing Options
Start Free Trial
Avatar of CrazyOne
CrazyOne
Flag of United States of America image

ASKER

Referring to your comment ID 35756191 in which I am gathering it is the unwinding where it all comes together. So in this case the actual function would be O(2n) if there were such a thing as O(2n). In other words the function cycles through twice. If this is correct would it not be more efficient, not programmatically but functionally to do something like the following? Wouldn’t that be a true O(n).

BTW thanks for the info so far it has been quite helpful.
intintCount=n;
if(intCount==0)
     return0;
else
{
     while(n!=0)
     {
       intCount=intCount+n-1;
       n--;
     }
}
return intCount;

Open in new window

Avatar of mrjoltcola
mrjoltcola
Flag of United States of America image

The order of an algorithm using recursion depends on the algorithm and how you use recursion. No rule says you only call your function once within each call. For example a binary sort may use recursion to iteratively split an array into smaller and smaller pieces, with more calls the deeper you go.

And in your case, no it does not make 2 cycles per function. Each function call executes once per N, so it would be O(n) already.
Avatar of for_yan
for_yan
Flag of United States of America image

So the advnatge of recursion is not in its performance but in simplicity
of programming; some opertaions - liket traversing the file system, is probably very difficult to
prioogram without recursion.

That's what you read in http://en.wikipedia.org/wiki/Recursion_%28computer_science%29 :

In languages (such as C and Java) that favor iterative looping constructs, there is usually significant time and space cost associated with recursive programs, due to the overhead required to manage the stack and the relative slowness of function calls; in functional languages, a function call (particularly a tail call) is typically a very fast operation, and the difference is usually less noticeable.

As a concrete example, the difference in performance between recursive and iterative implementations of the "factorial" example above depends highly on the language used. In languages where looping constructs are preferred, the iterative version may be as much as several orders of magnitude faster than the recursive one. In functional languages, the overall time difference of the two implementations may be negligible; in fact, the cost of multiplying the larger numbers first rather than the smaller numbers (which the iterative version given here happens to do) may overwhelm any time saved by choosing iteration.

Avatar of CrazyOne
CrazyOne
Flag of United States of America image

ASKER

I kind of understand what you are saying it is just hard for me to vision in this case that this particular function isn’t a loop. I mean it is acting like a loop in that it is calling on itself several times to complete its action just like a loop does at least that is the way I am seeing it.  :-)
Avatar of mrjoltcola
mrjoltcola
Flag of United States of America image

A loop uses the same variables, in the same scope.

Recursion uses a new set of variables in a new scope.
Avatar of webdev2000
webdev2000

Java
Java

Java is a platform-independent, object-oriented programming language and run-time environment, designed to have as few implementation dependencies as possible such that developers can write one set of code across all platforms using libraries. Most devices will not run Java natively, and require a run-time component to be installed in order to execute a Java program.

102K
Questions
--
Followers
--
Top Experts
Get a personalized solution from industry experts
Ask the experts
Read over 600 more reviews

TRUSTED BY

IBM logoIntel logoMicrosoft logoUbisoft logoSAP logo
Qualcomm logoCitrix Systems logoWorkday logoErnst & Young logo
High performer badgeUsers love us badge
LinkedIn logoFacebook logoX logoInstagram logoTikTok logoYouTube logo