Recursion

This is a most potent tool for developing algorithms and a great aid for solving large classes of problems. The idea is that a function can at a certain point call itself, and when that call is done, continue working with whatever result it has received. This is usually quite helpful for certain classes of problems or definitions. The most often quoted example is the factorial function (the factorial of n is written n!) as defined for non-negative integer values:

• If n is 0, then n!=1
• If n is greater than 0, then n! = n * (n-1)!

The value of n! is the number of ways you can order n different elements in a row. For example, if you want to place five books in line, you can pick any of the five for the first place, and then order the other four in every possible way, so 5! = 5*4!. If you continue to work this example, you'll get that 5! = 5*4*3*2*1=120, so n! is the product of all numbers up to n.

This can be immediately turned into JS code:

function fact(n) {
    if (n === 0) {
        return 1;
    } else {
        return n * fact(n - 1);
    }
}
console.log(fact(5)); // 120

Recursion will be a great aid for the design of algorithms. By using recursion you could do without any while or for loops -- not that we want to do that, but it's interesting that we can! We'll be devoting the complete chapter 9, Designing Functions - Recursion, to designing algorithms and writing functions recursively.