Understanding how a recursion really works (recursion from the ground up)

If you're into programming and really have problem on such algorithm that you wanted to implement, however requires a recursive call (or can be an iterative call --but we'll discuss on recursion for this topic).

Take note on recursion that they are,

• using much more memory than using iteration because it copies or clones the elements in the function that tries to recurse. So it makes new copies of:
• the code
• local variables with its initial variables
• paramaters
• it's more expensive as it retains clones into the memory which I am pertaining the variables, params, code in the stack
• it's usually slower due to overhead in maintaining the stack
• Each copy of the code includes a marker indicating the current position. When a recursive call is made, the marker in the old copy of the code is just after the call; the marker in the "cloned" copy is at the beginning of the method.
• When the method returns, that clone goes away, but the previous ones are still there, and know what to execute next because their current position in the code was saved (indicated by the marker)
• However, it makes more advantageous because it makes your code simpler! It makes your code more readable, easy to maintain, and easier to understand (but difficult to understand when you dig deeper but it's more sense and helpful and more understandable after you read this ;-)).

So for example, I wanted to use this simple Fibonacci function,

int fibonacci(n) {
    if(n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        print "\nn := " + n + "\n";
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

And then call it like,

for(i = 0; i <= 6; i++) {
    print fibonacci(i) . "\0\n\n\n";
}

So this is how method calls recursive really work:

• At runtime, a stack of activation records (ARs) is maintained: one AR for each active method, where "active" means: has been called, and has not yet returned.
• Each AR includes space for:
  • the method's parameters,
  • the method's local variables,
  • the return address -- where (in the code) to start executing after the method returns.
• When a method is called, its AR is pushed onto the stack. The return address in that AR is the place in the code just after the call (so the return address is the "marker" for the previous "clone").
• When a method is about to return, the return address in its AR is saved, its AR is popped from the stack, and control is transferred to the place in the code referred to by the return address.

Take note that, that all of the recursive calls have the same return address!

So what exactly happens in the stack, just check out the screenshot I have illustrated below.

So if n=4, result is 3.

if n = 5, result is 5.

if n=6, result is 8.

So what you see on the illustrated diagram above just proves that this kind of pattern is really expensive compared than doing iteration.

Anyhow, this just also shows how does a recursion works from the ground up which also stacks the implementation (the code/function) in memory which indeed expensive plus provides extra overhead.

I hope this makes a good understanding for the beginners. I have also referenced from this writeup on this page, http://pages.cs.wisc.edu/~vernon/cs367/notes/6.RECURSION.html

Hope this helps! :-)