Recursion demystified

Recursion is one of the main programming construct, that is very powerfull but sometimes it is not easy to understand.
I found one great example of recursive call:

// self invoking recursive function

(function foo(i) {
    if (i === 3) {
        return;
    }
    else {
        foo(++i);
    };
    console.log(i);
}(0));

Copy and paste it in chrome dev tools or in js interpreted environment. As  you can see it's not fibonacci, which is often used. This example is more straight-forward and simpler.

The output is 3,2,1.  It shows the way recursion works.
In short here is what is happening  - the inner function keeps calling outer function untill it reaches base case.
What is base case ? It is a number of calls which must be provided, usually expressed like a condition. If there is no base case, infinite loop will happen, which is not what we want. Since inner and outer function are same, we have a situation in which a function calls ifself. Foo inside will keep calling itself with provided arguments until it reaches base case.
And now important part: do you wonder why the output is inverted ? What don't we have 1,2,3 instead of 3,2,1 ?
That's because inner foo function is keeping results of calculation ( incrementing i ) somewhere in memory , but it can't provide output since it is called over and over again untill it reaches base case. That memory is called recursive stack, and it is a form of data structure, in which last data entrance is removed of called first. So when inner foo finally reaches base case, it is ready to "unwound" memory stack from the last to the first result giving 3,2,1 output.

Recursion is widely used in functional programming paradigm and it is considered for alternative to iteration.