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 whiles and fors. Many mathematical functions are easy to implement recursively, so we will start there. Recall that the factorial of a number n is:

   $n!=n*(n-1)*(n-2)*...*2*1$

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 $i=1$ instead of $i=0$?
• Why was the loop test $i<=n$ instead of $i<n$?

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.

   $0!=1$
   $n!=n*(n-1)!$ otherwise

This second formulation states that the factorial of zero is onea. 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. 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

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

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 recurif 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

A third example of recursion is the computation of the $n^{th}$ 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.. 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). 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

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