Recursion

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.

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)

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.

>>@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)

I agree, I used incorrect wording

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. :)

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

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

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?

What you are saying seems to make sense to me, let's wait waht mrjoltcola says - he obviously understands this stuff much better.

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;

Select allOpen in new window

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.

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.

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.  :-)

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

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

This is a nice simple example of using recursion with Java.
http://learn-java-by-example.com/2010/java/fibonnaci-number