Recursion [WIP]

[aznricepuff]

Lesson: Recursion

Recursion is a very powerful tool in programming. However, its uses are very limited in JASS since most of the situations in which it is usually implemented just don't crop up while working with JASS. However, JASS still supports recursion, so it is an available tool to use and hence the existence of this lesson.

A Model of Recursion

Recursion typically involves the execution of a procedure that includes instructions to repeat itself, but with each repetition changing the conditions under which it is being executed such that eventually it reduces to one or a few base cases. When such a base case is reached, repetition stops. Generally, with each repetition of the procedure the conditions are changed such that the task that the next repetition of the procedure must carry out is smaller or simpler than the previous. When such a thing happens (the reduction of the task to a smaller or simpler task) via a repetition of the procedure, we say that we have progressed to the next level of recursion.

The above image illustrates our model of recursion. We begin with an initial task that gets broken down into successively smaller and smaller tasks until it is reduced to a single base case. Every yellow box represents one instance (one repetition) of the recursive procedure. Boxes of the same size belong to the same level of recursion. The teal box represents a base case. Red arrows denote input, blue arrows denote computations carried out within a single instance of the procedure, and green arrows denote output. Notice that the later levels of recursion (including the base case) may feed information back to earlier levels. Indeed in many cases a recursive procedure will require data from successive recursions and will have to wait until those recursions complete their tasks before it can finish its own task. In such situations essentially nothing can be completed until the recursion reaches a base case, at which point the information "feeds back" into the earlier recursions.

Recursion in JASS

A classic example of using recursion is the computation of factorials. The factorial of a non-negative integer n is defined as

n! = (n)(n - 1)(n - 2)(n - 3)...(1)

Remember that 0! = 1.

Before we look at the factorial function, let us first recognize that n! = n * (n - 1)!. This is something we will keep coming back to, so it is important to remember.

And now let's look at a recursive function in JASS:

function Factorial takes integer n returns integer
    if (n == 0) then
        return 1
    endif
    return n * Factorial(n - 1)
endfunction

Here we see that function Factorial() contains a call to itself. This is how recursion is implemented: a function that makes a call to itself. This function call is called the recursive call. If a function contains such a call the function is said to be a recursive function.

Upon closer examination of Factorial() we can identify the base case for this recursion: when n is equal to 0, return 1. The function first checks to see if the base case condition is satisfied; if it is, then the function goes to the base case, otherwise it goes to the recursive call. Will this function always eventually reduce to the base case? Well, remember that n is always a non-negative integer, so if it is not 0 to begin with, the recursive call will keep on decrementing n by 1 until it reaches 0. So the function always eventually reduces to the base case and recursion will always terminate after a finite number of steps.

function Factorial takes integer n returns integer
    if (n == 0) then
        return 1 // Base case
    endif
    return n * Factorial(n - 1) // Recursive call
endfunction

To understand how Factorial() is able to correctly return the factorial of n, let's think about what it is actually doing.

Firstly, we assume that the initial call to Factorial() has n greater than 0 (the case where n = 0 is trivial). Because n is not equal to 0, the function goes to its recursive call and returns n multiplied by the value returned by Factorial() when n = n - 1. How does this help us? Remember that we have already decided that n! = n * (n - 1)!. So as long as Factorial() works correctly for n - 1 it works correctly for n. This means that Factorial(n) works as long as Factorial(n-1) works, which works as long as Factorial(n-2) works, which works as long as Factorial(n-3) works, etc. all the way to Factorial(0). Why must we stop at 0? Because when n = 0, the recursive call is not made so our statement does not apply. But does Factorial(0) work? Well, when n = 0, the function goes to its base case and returns 1, which is indeed 0!. Therefore, Factorial(0) works. Moreover, because of this, Factorial(n) also works for any non-negative n because we can always trace the correctness of Factorial(n) back to Factorial(0).

In general if you can prove the following 3 properties of a recursive function, you can be assured the function works correctly:

1. The function always eventually reduces to one of its base cases.
2. The function performs correctly under all of its base cases.
3. The function performs correctly given that it performs correctly for the next level of recursion.

For logic buffs the first property ensures that the correctness of the function is a candidate for proof via induction while the second (basis) and third (inductive step) properties are those that must be satisfied in order to use the principle of induction to conclude the function is correct for all cases.

Building Recursive Code

We now set off to create a recursive function.

Coming Soon...

Linear vs. Tree Recursion

All of the recursive functions we've looked at so far have been examples of linear recursion. That is, each call to the recursive function can only lead to a maximum of one recursive call before the function returns. This means that the amount of time required for the recursion to complete increases linearly with respect to the maximum depth of the recursion.

Linear Recursion

From the graphic above, we see that with 6 levels of linear recursion, the recursive procedure is repeated 6 times. Assuming that the procecure takes x amount of time to complete every time, the time for this entire recursive task to finish is 6x.

There are, however, other types of recursive functions that result in what's called tree recursion. In this type of recursion, a single call to the function may lead to two or more recursive calls before the function returns. Consequently, the amount of time required for the recursion to complete increases exponentially with respect to the maximum depth of the recursion.

Tree Recursion

From the graphic above, we see that with tree recursion, just 4 levels of recursion causes the recursive procedure to be repeated 15 times (a single yellow box represents one repetition of the procedure while all boxes of the same size represent a single level of recursion). Therefore the completion time for the entire task is 15x. If we were to increase the depth of the recursion to 5, then that time would increase to 31x.

Recursion vs. Iteration

In many cases recursive functions can be rewritten to use iteration and vice versa. So which is better? Recursion requires a function call to be made with every recursive call, and function calls are slow in JASS. Therefore, it is a general rule that recursive functions will have worse performance times than their iterative counterparts. This is why the use of recursion is very rare in JASS. A general rule of thumb is: if you can convert a recursive function to an iterative one without much trouble, then do so.

There are, of course, procedures where recursion is the preferred method (usually because of issues of code simplicity or prohibitive memory space requirements when using the iterative version). Examples of such procedures include binary search tree traversal, and divide-and-conquer sorting algorithms.

Homework

Short Answer Problems

Give a one to two sentence answer to the following questions. Writing up code is not necessary unless you feel it helps to illustrate your answer.

1. You are given the following function:
   

   function Foo takes integer x returns integer
       if (x > 100) then
           return x - 10
       endif
       return Foo(Foo(x + 11))
   endfunction

   • Identify the base case.
   • What does Foo(98) return? (Try to figure this out without running the actual code.)
   • Does this function always terminate (eventually stop recursing) for x > 0? Justify your answer.

Coding Problems

Write up code for each problem that meets the given specifications.

1. Write a recursive function that computes the nth Fibonacci number. The Fibonacci sequence is defined as follows:
   
   f₀ = 1
   f₁ = 1
   f_n = f_n-1 + f_n-2, n >= 2
2. Write a recursive function that approximates the square root of a non-negative real r. Use Newton's method, which states that given any real-valued function f(x) and an approximation of one of its zeroes (values of x where f(x) = 0) x₀, a better approximation for the zero is given by
   
   x₀ - f(x₀)/f'(x₀)
   
   where f'(x) is the derivative of f(x). How close your function approximates the root is up to you, but you should be accurate to at least 2 or 3 decimal places. (Hint: Use f(x) = x² - r and never use 0 as an approximation.)

Challenge Problems

These are optional problems that you may try at your discretion. They are often far more difficult than the other types of problems.

1. Implement the fibonacci function from Coding Problem 1 so that it does not unnecessarily duplicate any computations. (In other words, use linear rather than tree recursion.)
2. Write a recursive function that computes the greatest common divisor of two positive integers j and k.