# The Sway Reference Manual/Recursion

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.

## The parts of a recursive function[edit | edit source]

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 divisor[edit | edit source]

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 sequence[edit | edit source]

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 loops[edit | edit source]

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.

## Footnotes[edit | edit source]

- ↑ 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.