As I mentioned earlier, there are problems which can only be solved easily using recursion – iterative solutions lack the elegance and (in this specific case) efficiency of the recursive solution. The example I will use here is the “change problem”.

This problem sets out to calculate how many different ways there are of giving change for some amount of money using only the n smallest coins. Below I will use a pseudo-code example, utilizing an array called “coins”, which we will define to be our corrency denominations in cents, eg. [5, 10, 20, 50, 100, 200]. Calling our “change” function with the parameters 800 and 4 would calculate how many different ways there are of giving change for $8.00 using only the 4 smallest denominations, in this case [5, 10, 20, 50].
The recursive implementation:

function change( amount, n )
{
    // These are our base cases

    // Exactly 1 way of making change for $0
    if amount equals 0 then
        return 1
    endif

    // no ways of making change for negatives
    if amount < 0 then
        return 0
    endif

    // no ways of making change with no coins
    if n equals 0 then
        return 0
    endif

    // This is our recursive case
    return change(amount,n-1) + change(amount-coins[n], n)
}

Another example often used to demonstrate the elegance of recursion is the factorial function in mathematics. n! (read as “n factorial”) is defined to be n * (n-1) * (n-2) * ... * 1, and 0! is defined to be 1 (by convention). For example, 4! = 4 * 3 * 2 * 1.

This can be elegantly described by the following recursive function:

function factorial( x )
{
    if x equals 0 then
        return 1
    endif

    return x * factorial( x-1 )
}

That’s all there is to it, really! If you want to learn more about recursion, then a quick search should turn up a myriad of recursion tutorials and resources.

1. What is Recursion?
2. Why is recursion useful?
3. Recursion by example