Recursion

Recursion is repeatedly calling the same function to provide some meaningful output; at least that's what a computer scientist will tell you. A more mathematical definition of recursion is plugging in some start values into a function, getting the function's results, and reapplying them to the original function. Recursive functions often have odd sounding explanations. A factorial can be explained in recursive terms.

In case you don't know, the factorial of n, written n!

n * (n - 1) * (n - 2) * ... * (n - (n - 1))

So, 5! (pronounced five factorial)

5 * (5 - 1) * (5 - 2) * (5 - 3) * (5 - 4) * 1

is equal to 5 * 4 * 3 * 2 * 1, or 120

A factorial can be defined recursively as follows:

Start out with some natural number N (in our example, 5)
The factorial of N is N * the factorial of N - 1.

So, if we let N be 5, then 5! is 5 * 4!. Now, we "recurse", letting N be 4. So 4! is 4 * 3!. So 5! = 5 * 4 * 3!. (I know most are probably lost now. We started out with 5 factorial, and then let 5 factorial equal 5*4 factorial. We then let 5 factorial equal 5 * 4 * 3 factorial, by repeatedly applying the recursive definition of factorial.) So, 3! is 3 * 2!, 2! is 2 * 1!, 1! is 1 * 0!, and 0! is defined to equal 1. So,

5! =
5 * 4! =
5 * 4 * 3! =
5 * 4 * 3 * 2! =
5 * 4 * 3 * 2 * 1! =
5 * 4 * 3 * 2 * 1 * 0! =
5 * 4 * 3 * 2 * 1 * 1 = 120

We applied the recursive definition of a factorial to go from 5! to 120.

Now you may be wondering how in the world you write code to do this. Well, you simply write a function that will call itself.

function factorial(N) {
     if (N > 1) return N * factorial(N - 1);
     else return N;
}

If you were to do:
document.write(factorial(5)) ==> 120

see the code in action

The above function has all of the same rules that our mathematical recursive definition of a factorial did. We define 0! to equal 1, and we define factorial N (where N > 0), to be N * factorial(N - 1). All recursive functions must have an exit condition, that is a state when it does not recurs upon itself. Our exit condition in this example is when N = 0. If you do not have an exit condition, you're recursive function will recurs forever until you run out of stack space. To make a long story short, you'll receive some nasty error about lack of memory, or stack overflow.

You're probably wondering what is really happening in the code. You can see if you trace the flow of the function through. It can be difficult at times, but you must be able to do this to fully understand recursion.

When the factorial function is first called with, say, N = 5, here is what happens:

FUNCTION:
Does N = 0? No
Function return Value = 5 * factorial(4)

At this time, the function factorial is called again, with N = 4.

FUNCTION:
Does N = 0? No
Function return Value = 4 * factorial(3)

At this time, the function factorial is called again, with N = 3.

FUNCTION:
Does N = 0? No
Function return Value = 3 * factorial(2)

At this time, the function factorial is called again, with N = 2.

FUNCTION:
Does N = 0? No
Function return Value = 2 * factorial(1)

At this time, the function factorial is called again, with N = 1.

FUNCTION:
Does N = 0? No
Function return Value = 1 * factorial(0)

At this time, the function factorial is called again, with N = 0.

FUNCTION:
Does N = 0? Yes
Function return Value = 1

Now, we have to trace our way back up! See, the factorial function was called six times. At any function level call, all function level calls above still exist! So, when we have N = 2, the function instances where N = 3, 4, and 5 are still waiting for their return values.

So, the function call where N = 1 gets retraced first, once the final guy returns 0. So, the function call where N = 1 returns 1 * 1, or 1. The next higher function call, where N = 2, returns 2 * 1 (1, because that's what the function call where N = 1 returned). You just keep working up the chain.

Where N = 2, = > 2 * 1, or 2 was returned
Where N = 3, = > 3 * 2, or 6 was returned
Where N = 4, = > 4 * 6, or 24 was returned
Where N = 5, = > 5 * 24, or 120 was returned

And since N = 5 was the first function call (hence the last one to be recalled), the value 120 is returned.