Erlang Central

Recursion

Revision as of 08:33, 2 September 2006 by Rvg (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Contents

Note

This article is originally from Mastering Recursive Programming. We have modified it for INTERNAL use only so as to be applicable for Erlang.

Overview

Recursion occurs when a function calls itself directly or indirectly. The classic example of recursive programming involves computing factorials. The factorial of a number is computed as that number times all of the numbers below it up to and including 1. For example, factorial(5) is the same as 5*4*3*2*1, and factorial(3) is 3*2*1.

An interesting property of a factorial is that the factorial of a number is equal to the starting number multiplied by the factorial of the number immediately below it. For example, factorial(5) is the same as 5 * factorial(4). You could almost write the factorial function simply as this:

factorial(N) ->
   N * factorial(N-1).

The problem with this function, however, is that it would run forever because there is no place where it stops. The function would continually call factorial. There is nothing to stop it when it hits zero, so it would continue calling factorial on zero and the negative numbers. Therefore, our function needs a condition to tell it when to stop. Incidentally, when this function hits 0, the answer would become 0 and be 0 forever afterwards. This is incorrect.

Since factorials of numbers less than 1 don't make any sense, we stop at the number 1 and return the factorial of 1 (which is 1). Therefore, the real factorial function will look like this:

factorial(N) ->
  case N of										
	1 => 1;
	N -> N * factorial(N-1)
  end.

As you can see, as long as the initial value is above zero, this function will terminate. The stopping point is called the base case. A base case is the bottom point of a recursive program where the operation is so trivial as to be able to return an answer directly. All recursive programs must have at least one base case and must guarantee that they will hit one eventually; otherwise the program would run forever or until the program ran out of memory or stack space. The function above does not utilise the pattern matching power of Erlang however, so we rewrite it as:

factorial(1) -> 1;					                (2)				
factorial(N) -> N * factorial(N-1).

In (2) we used pattern matching in the function clause to detect the case N == 1. Essentially the function clause gives us a first level if or case for free, so we can easily avoid lines as in (1).

Basic steps of recursive programs

Every recursive program follows the same basic sequence of steps:

  1. Initialize the algorithm. Recursive programs often need a seed value to start with. This is accomplished either by using a parameter passed to the function or by providing a gateway function that is non-recursive but that sets up the seed values for the recursive calculation.
  2. Check to see whether the current value(s) being processed match the base case. If so, process and return the value.
  3. Redefine the answer in terms of a smaller or simpler sub-problem or sub-problems.
  4. Run the algorithm on the sub-problem.
  5. Combine the results in the formulation of the answer.
  6. Return the results.

Writing provably correct programs

Bugs are a part of the daily life of every programmer because even the smallest loops and the tiniest function calls can have bugs in them. And while most programmers can examine code and test code for bugs, they do not know how to prove that their programs will perform the way they think they will. With this in mind, we are going to examine some of the common sources of bugs and then demonstrate how to make programs that are correct and can be proven so.

Bug source: State changes

One of the primary sources of bugs occurs when variables change states. You might think that the programmer would be keenly aware of exactly how and when a variable changes state. This is sometimes true in simple loops, but usually not in complex ones. Usually within loops, there are several ways that a given variable can change state.

For example, if you have a complicated if statement, some branches may modify one variable while others modify other variables. On top of that, the order is usually important but it is difficult to be absolutely sure that the sequence coded is the correct order for all cases. Often, fixing one bug for one case will introduce other bugs in other cases because of these sequencing issues.

In order to prevent these kinds of errors, a developer needs to be able to:

  • Tell by sight how each variable received its present value.
  • Be certain that no variable is performing double-duty. (Many programmers often use the same variable to store two related but slightly different values.)
  • Be certain that all variables hit the state they are supposed to be in when the loop restarts. (A common programming error is failure to set new values for loop variables in corner cases that are rarely used and tested.)

To accomplish these objectives, we need to make only one rule in our programming: Assign a value to a variable only once and NEVER MODIFY IT! This rule is enforced in Erlang and makes pattern matching possible.

This rule is blasphemy for many who have been raised on imperative, procedural, and object-oriented programming -- variable assignment and modification are at the core of these programming techniques! Still, state changes are consistently one of the chief causes for programming errors for imperative programmers.

So how does a person program without modifying variables? Let's look at several situations in which variables are often modified and see if we can get by without doing so:

  • Reusing a variable.
  • Conditional modification of a variable.
  • Loop variables.

Let's examine the first case, reusing a variable. Often, a variable is reused for different, but similar, purposes. For example, sometimes if part of a loop needs an index to the current position in the first half of a loop and the index immediately before or after for the rest of the loop, many programmers use the same variable for both cases, just incrementing it in the middle. This can easily cause the programmer to confuse the two uses as the program is modified. To prevent this problem, the best solution is to create two separate variables and just derive the second from the first the same way you would do so if you were just writing to the same variable.

The second case, the conditional modification of a variable, is a subset of the variable reuse problem except that sometimes we will keep our existing value and sometimes we will want a new value. Again, the best thing is to create a new variable. In most languages, we can use the ternary operator ? : to set the value of the new variable. For example, if we wanted to give our new variable a new value, as long as it's not greater than some_value, we could write:

	int new_variable = old_variable > some_value ? old variable : new_value;.

Once we have rid ourselves of all variable state changes, we can know that when we first define our variable, the definition of our variable will hold for as long as the function lasts. This makes sequencing orders of operations much easier, especially when modifying existing code. You don't have to worry about what sequence a variable might have been modified in or what assumptions were being made about its state at each juncture.

When a variable cannot change state, the full definition of how it is derived is illustrated when and where it is declared! You never have to go searching through code to find the incorrect or mis-ordered state change again!

Loop variables

Now, the question is how to do loops without assignment? The answer lies in recursive functions. Take a look at the properties of loops and see how they compare with those of recursive functions in the following table:

Properties Loops Recursive Functions
Repetition Execute the same block of code repeatedly to obtain the result; signal their intent to repeat by either finishing the block of code or issuing a continue command. Execute the same block of code repeatedly to obtain the result; signal their intent to repeat by repeat by calling themselves.
Terminating Conditions In order to guarantee that it will terminate, a loop must have one or more conditions that cause it to terminate and it must be guaranteed at some point to hit one of these conditions. In order to guarantee that it will terminate, a recursive function requires a base case that causes the function to stop recursing.
StateCurrent state is updated as the loop progresses.Current state is passed as parameters.

Tail-recursive functions

So I've showed you how loops and recursive functions are related and how you can convert loops into recursive, non-state-changing functions to achieve a result that is more maintainable and provably correct than the original programming.

However, one concern people have with the use of recursive functions is the growth of stack space. Indeed, some classes of recursive functions will grow the stack space linearly with the number of times they are called -- there is one class of function though, tail-recursive functions, in which stack size remains constant no matter how deep the recursion is.

When we converted our loop to a recursive function, the recursive call was the last thing that the function did. If you evaluate print_report_i, you will see that there is nothing further that happens in the function after the recursive call.

It is exhibiting a loop-like behaviour. When loops hit the end of the loop or if it issues a continue, then that is the last thing it will do in that block of code. Likewise, when print_report_irecurses, there is nothing left that it does after the point of recursion.

A function call (recursive or not) that is the last thing a function does is called a tail-call. Recursion using tail-calls is called tail-recursion. Let's look at some example function calls to see exactly what is meant by a tail-call:

int test1() {
    int a = 3;
    test1(); /* recursive, but not a tail call.  We continue */
             /* processing in the function after it returns. */
    a = a + 4;
    return a;
}

int test2() {
    int q = 4;
    q = q + 5;
    return q + test1(); /* test1() is not in tail position.
                         * There is still more work to be
                         * done after test1() returns (like
                         * adding q to the result
                         */
}

int test3() {
    int b = 5;
     b = b + 2;
     return test1();  /* This is a tail-call.  The return value
                      * of test1() is used as the return value
                      * for this function.
                      */
} 

int test4() {
    test3(); /* not in tail position */
    test3(); /* not in tail position */
    return test3(); /* in tail position */
}

As you can see, in order for the call to be a true tail-call, no other operation can be performed on the result of the tail-called function before it is passed back. Notice that since there is nothing left to do in the function, the actual stack frame for the function is not needed either. The only issue is that many programming languages and compilers don't know how to get rid of unused stack frames. If we could find a way to remove these unneeded stack frames, our tail-recursive functions would run in a constant stack size.

Tail-call optimization

The idea of removing stack frames after tail-calls is called tail-call optimization. So what is the optimization? We can answer that question by asking other questions:

  • After the function in tail position is called which of our local variables will be in use? None.
  • What processing will be done to the return value? None.
  • Which parameters passed to the function will be used? None.

It seems that once control is passed to the tail-called function, nothing in the stack is useful anymore. The function's stack frame, while it still takes up space, is actually useless at this point, therefore the tail-call optimization is to overwrite the current stack frame with the next one when making a function call in tail position while keeping the original return address. Essentially what we are doing is surgery on the stack. The activation record isn't needed anymore, so we are going to cut it out and redirect the tail-called function back to the function that called us. This means that we have to manually rewrite the stack to fake a return address so that the tail-called function will return directly to our parent.