In the previous chapter, we learned about looping using the functions *while*, *do*-*until*, *for*, and *for*-*each*. These functions implement what is known as *iterative* looping.

Recursion is another way of looping; often, recursive loops are easier to write and understand, as compared to iterative loops, such as *while*s and *for*s. Many mathematical functions are easy to implement recursively, so we will start there. Recall that the factorial of a number *n* is:

Consider writing a function which computes the factorial of a positive integer. For example, if the function were passed the value of 4, it should return the value of 24 since 4! is 4*3*2*1 or 24. One approach would be to use an iterative loop to cycle through all the multipliers, saving the partial product at each iteration. Getting the code to work correctly does take a bit of fiddling to get all the important bits right. A working implementation might look like:

function factorial(n) { var i; var product = 1; for (i = 1, i <= n, i = i + 1) { product = product * i; } product; }

This implementation raises many questions, since it goes against the general convention for structuring a counting loop:

- Why was the product initialized to one instead of zero?
- Why was the loop initialization chosen to be instead of ?
- Why was the loop test instead of ?

With some pondering, these questions can be answered because of the mathematics of multiplication..

There is a radically different approach that can be taken, an extremely simple, elegant, and powerful approach, called *recursion*. To apply recursion to solve a problem, it must be possible to state the solution of a problem in ever simpler terms. For factorial, the factorial of a number can be stated in terms of a simpler factorial.

otherwise

This second formulation states that the factorial of zero is onea. ^{[1]} and that the factorial of any other (positive) number is obtained by multiplying the that number by the factorial of one less than that number. After some study, you should be able to see that both the first formulation (with the ellipses ...) and this new formulation are equivalent^{[2]}. The second form is particularly well suited for implementation as a computer program:

function factorial(n) { if (n == 0) { 1; } else { n * factorial(n - 1); } }

or

function factorial(n) { if (n == 0,1,n * factorial(n - 1)); }

using *if'*s pure function call syntax.

Note how these two versions of *factorial* precisely implement the second formulation.

Convince yourself that the function really works by tracing the function call:

factorial(3)

Decomposing the call, we find that:

factorial(3) is 3 * factorial(2)

since *n*, having a value of 3, is not equal to 0. and so the second block of the *if* is evaluated. We can replace `factorial(2)` by `2 * factorial(1)`, yielding:

factorial(3) is 3 * 2 * factorial(1)

since *n*, now having a value of 2, is still not zero. Continuing along this vein, we can replace `factorial(1)` by `1 * factorial(0)`, yielding:

factorial(3) is 3 * 2 * 1 * factorial(0)

Now in this call to factorial, *n* does have a value of zero, so we can replace `factorial(0)` with its immediate return value of zero:

factorial(3) is 3 * 2 * 1 * 1

Thus, `factorial(3)` has a value of six:

sway> factorial(3); INTEGER: 6

as expected.

## Contents

## The parts of a recursive functionEdit

Recursive approaches rely on the fact that it is usually simpler to solve a smaller problem than a larger one. In the factorial problem, trying to find the factorial *n* - 1 is a little bit simpler than finding the factorial of *n*. If finding the factorial of *n - 1* is still too hard to solve easily, then find the factorial of *n - 2* and so on until we find a case where the solution is easy. With regards to factorial, this is when *n* is equal to zero. The 'easy-to-solve' code (and the values that gets you there) is known as the *base* case. The find-the-solution-for-a-simpler-problem code (and the values that get you there) is known as the *recursive* case. The recursive case usually contains a call to the very function being executed. This call is known as a *recursive* call.

Most well-formed recursive functions are composed of at least one *base* case and at least one *recursive* case.

## The greatest common divisorEdit

Consider finding the greatest common divisor (gcd) of two numbers. One approach is use repeated division. The first division divides the two numbers in question, saving the remainder. Now make the divisor the dividend and the remainder the divisor. Repeat this process until the remainder is zero. At that point, the current divisor is the gcd.

Let's turn it into a function, first iteratively and then recursively.

// compute the gcd of two positive integers iteratively function gcd(first,second) { var remainder; do-until (remainder == 0) { remainder = first % second; first = second; second = remainder; } first; //first holds the last divisor }

The *do-until* loop insures that the loop body is executed before the remainder is tested. Let's rewrite the function recursively. First we identify the recurrence case(s) and then the base case(s). In this case, the recurrence and base cases are a little different than in the factorial example. We recur^{[3]}if the remainder is not zero. We immediately return the answer if the remainder is zero. Now that the recurrence and base cases have been identified, we can write the recursive version without too much trouble.

// compute the gcd of two positive integers function gcd(first,second) { if (first % second == 0) { second; } else { gcd(second,first % second); } }

or

function gcd(first,second) { if (first % second == 0,second,gcd(second,first % second)); }

or, to remove the repeated computation of the remainder:

function gcd(first,second) { var remainder = first % second; if (remainder == 0,second,gcd(second,remainder)); }

Again, the recursive version is more compact.

Look at how the recursive version turns *second* into *first* by passing *second* as the first argument in the recursive call. By the same token, *remainder* becomes *second* by nature of being the second argument in the recurive call. To convince yourself that the routine really works, modify *gcd* to inspect the arguments:

function gcd(first,second) { var remainder = first % second; inspect(array(first,second,remainder)); if (remainder == 0,second,gcd(second,remainder)); }

You haven't learned about arrays or the built-in *array* function yet, but think of it as a way to group multiple things together. Inspecting the array is a trick to get multiple values inspected with a single call to *inspect*.

sway> gcd(66,42); array(first,second,remainder) is [66,42,24] array(first,second,remainder) is [42,24,18] array(first,second,remainder) is [24,18,6] array(first,second,remainder) is [18,6,0] INTEGER: 6

Note, how the first remainder, 24, keeps shifting to the left. In the first recursive call, the remainder becomes *second*, so the 24 shifts one spot to the left. On the second recursive call, the current *second*, which is 24, becomes *first*, so the 24 shifts once again to the left.

## The Fibonacci sequenceEdit

A third example of recursion is the computation of the Fibonacci number. The Fibonacci series looks like this:

n 0 1 2 3 4 5 6 7 8 ... Fib(n) 0 1 1 2 3 5 8 13 21 ...

and is found in nature again and again^{[4]}.. In general, a Fibonacci number is equal to the sum of the previous two Fibonacci numbers. The exceptions are the zeroes and the first Fibonacci numbers which are equal to 0 and 1 respectively. Voila! The recurrence case and the two base cases have jumped right out at us! Here, then is a recursive implementation of a function which computes the nth Fibonacci number.

// compute the nth Fibonacci number // n must be non-negative! function fibonacci(n) { if (n == 0) return 0; if (n == 1) return 1; fibonacci(n-1) + fibonacci(n-2); }

Our implementation is straightforward and elegant. Unfortunately, it's horribly inefficient. Unlike our recursive versions of *factorial* and *gcd*, which recurred about as many times as the iterative versions looped, our Fibonacci version will recur many, many more times than an iterative version of Fibonacci when computing larger Fibonacci numbers. Here's why.

Consider the call to `fib(6)`. Tracing all the recursive calls to *fib*, we get:

fib(6) is fib(5) + fib(4)

Replacing `fib(5)` with `fib(4) + fib(3)`, we get:

fib(6) is fib(4) + fib(3) + fib(4)

We can already see a problem, we will compute fib(4) twice, once from the original call to fib(6) and again when we try to find fib(5). If we write down all the recursive calls to `fib(6)` which each recursive call indented from the previous, we get a structure that looks like this:

fib(6) fib(5) fib(4) fib(3) fib(2) fib(1) fib(0) fib(1) fib(2) fib(1) fib(0) fib(3) fib(2) fib(1) fib(0) fib(1) fib(4) fib(3) fib(2) fib(1) fib(0) fib(1) fib(2) fib(1) fib(0)

We would expect, based on how the Fibonacci sequence is generated to take about six 'steps' to calculate `fib(6)`. Instead, ultimately there were 13 calls to either `fib(1)` or `fib(0)`^{[5]}. There was a tremendous amount of duplicated, and therefore wasted effort. So let's try to compute Fibonacci numbers using an iterative loop:

function fib(n) { var i; var first = 0; var second = 1; for (i = 0, i < n, i = i + 1) { var sum = first + second; first = second; second = sum; } first; }

In the loop body, we see that *fib* is much like *gcd*; the second number becomes the first number and some combination of the first and second number becomes the second number. In the case of *gcd*, the combination was the remainder and, in the case of *fib*, the combination is sum.

As with factorial, hitting on the right way to proceed iteratively is not exactly straightforward, while the recursive version practically wrote itself. Noting the similarity of *fib* and *gcd* suggest a way to have both recursion and efficiency at the same time.

## More on recursive loopsEdit

To transform an iterative loop into a recursive loop, one first identifies those variables that are changing in the loop body; these variable will become formal parameters in the recursive function. For example, the *fib* loop above has three (not two!) variables that are being changed during each iteration of the loop: *first*, *second*, and *i*. So, we start out our recursive function as thus:

function loop(first,second,i) { ... }

The loop test becomes an *if* test in the body of the *loop* function:

function loop(first,second,i) { if (i < n) { ... } else { ... } }

The if-true block becomes the recursive call. The arguments to the recursive call encode the updates to the loop variables The if-false block becomes the value the loop attempted to calculate:

function loop(first,second,i) { if (i < n) { loop(second,first + second,i + 1); } else { first; } }

Using function call syntax for *if* shortens up the function:

function loop(first,second,i) { if (i < n,loop(second,first + second,i + 1),first); }

Next, we embed the *loop* function into our the function containing the original loop. That way, any non-local variables referenced in the test or body of the original loop will be visible to the *loop* function:

function fib(n) { function loop(first,second,i) { if (i < n,loop(second,first + second,i + 1),first); } ... }

Finally, we call the *loop* function with the initial values of the loop variables:

function fib(n) { function loop(first,second,i) { if (i < n,loop(second,first + second,i + 1),first); } loop(0,1,0); }

For more practice, let's convert the iterative version of *factorial* into a recursive function using this method. We'll see we'll end up with a different recursive function than before.

function factorial(n) { var i; var product = 1; for (i = 1, i <= n, i = i + 1) { product = product * i; } product; }

We start, as before, by working on the *loop* function. In this case, only two variables are changing in the loop: product and *i*.

function loop(product,i) { ... }

Next, we write the *if* expression:

function loop(product,i) { if (i <= n,loop(product * i,i + 1),product); }

Next, we embed the *loop* function and call it:

function factorial(n) { function loop(product,i) { if (i <= n,loop(product * i,i + 1),product); } loop(1,1); }

The moral of this story is that any iterative loop can be rewritten as a recursion and any recursion can be rewritten as an iterative loop. Moreover, in 'good' languages^{[6]}, there is no reason to prefer one way over the other, either in terms of the time it takes or the space used in execution. Use a recursion if that makes the implementation more clear, otherwise, use an iterative loop.

## FootnotesEdit

- ↑ Mathematicians, being an inclusive bunch, like to invite zero to the factorial party.
- ↑ The first formulation gets the basic idea of factorial across but is not very precise. For example, how would you computer the factorial of three using the first formulation?
- ↑ The word is
*recur*, NOT*recurse*! - ↑ Pineapples, the golden ratio, chambered nautilus, etc.
- ↑ 13 is a Fibonacci number. Curious!
- ↑ Someday, Sway will be a 'good' language.