Recursive programming

For new computer science students, the concept of recursive programming is often difficult. Recursive thinking is difficult because it almost seems like circular reasoning. It's also not an intuitive process; when we give instructions to other people, we rarely direct them recursively.
For those of you who are new to computer programming, here's a simple definition of recursion: Recursion occurs when a function calls itself directly or indirectly.
A classic example of recursion
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:

Listing 1. First try at factorial function

int factorial(int n) { return 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.
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:

Listing 2. Actual factorial function

int factorial(int n) { if(n == 1) { return 1; } else { return n * factorial(n - 1); } }

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.

---

Back to top

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

Using an inductive definition
Sometimes when writing recursive programs, finding the simpler sub-problem can be tricky. Dealing with inductively-defined data sets, however, makes finding the sub-problem considerably easier. An inductively-defined data set is a data structure defined in terms of itself -- this is called an inductive definition.
For example, linked lists are defined in terms of themselves. A linked list consists of a node structure that contains two members: the data it is holding and a pointer to another node structure (or NULL, to terminate the list). Because the node structure contains a pointer to a node structure within it, it is said to be defined inductively.
With inductive data, it is fairly easy to write recursive procedures. Notice how like our recursive programs, the definition of a linked list also contains a base case -- in this case, the NULL pointer. Since a NULL pointer terminates a list, we can also use the NULL pointer condition as a base case for many of our recursive functions on linked lists.
Linked list example
Let's look at a few examples of recursive functions on linked lists. Suppose we have a list of numbers, and we want to sum them. Let's go through each step of the recursive sequence and identify how it applies to to our summation function:

1. Initialize the algorithm. This algorithm's seed value is the first node to process and is passed as a parameter to the function.
2. Check for the base case. The program needs to check and see if the current node is the NULL list. If so, we return zero because the sum of all members of an empty list is zero.
3. Redefine the answer in terms of a simpler sub-problem. We can define the answer as the sum of the rest of the list plus the contents of the current node. To determine the sum of the rest of the list, we call this function again with the next node.
4. Combine the results. After the recursive call completes, we add the value of the current node to the results of the recursive call.

Here is the pseudo-code and the real code for the function:

Listing 3. Pseudo-code for the sum_list program

function sum_list(list l) is l null? yes - the sum of an empty list is 0 - return that data = head of list l rest_of_list = rest of list l the sum of the list is: data + sum_list(rest_of_list)

The pseudo-code for this program almost identically matches its Scheme implementation.

Listing 4. Scheme code for the sum_list program

(define sum-list (lambda (l) (if (null? l) 0 (let ( (data (car l)) (rest-of-list (cdr l))) (+ data (sum-list rest-of-list))))))

For this easy example, the C version is just as simple.

Listing 5. C code for the sum_list program

int sum_list(struct list_node *l) { if(l == NULL) return 0; return l.data + sum_list(l.next); }

You may be thinking that you know how write this program to perform faster or better without recursion. We will get to the speed and space issues of recursion later on. In the meantime, let's continue our discussion of recursing of inductive data sets.
Suppose we have a list of strings and want to see whether a certain string is contained in that list. The way to break this down into a simpler problem is to look again at the individual nodes.
The sub-problem is this: "Is the search string the same as the one in this node?" If so, you have your solution; if not, you are one step closer. What's the base case? There are two:

• If the current node has the string, that's a base case (returning "true").
• If the list is empty, then that's a base case (returning "false").

This program won't always hit the first base case because it won't always have the string being searched for. However, we can be certain that if the program doesn't hit the first base case it will at least hit the second one when it gets to the end of the list.

Listing 6. Scheme code for determining if a given list contains a given string

(define is-in-list (lambda (the-list the-string) ;;Check for base case of "list empty" (if (null? the-list) #f ;;Check for base case of "found item" (if (equal? the-string (car the-list)) #t ;;Run the algorithm on a smaller problem (is-in-list (cdr the-list) the-string)))))

This recursive function works fine, but it has one main shortcoming -- every iteration of the recursion will be passing the same value for the-string. Passing the extra parameter can increase the overhead of the function call.
However, we can set up a closure at the beginning of the function to keep the string from having to be passed on each call:

Listing 7. Scheme program for finding a string using a closure

(define is-in-list2 (lambda (the-list the-string) (letrec ( (recurse (lambda (internal-list) (if (null? internal-list) #f (if (equal? the-string (car internal-list)) #t (recurse (cdr internal-list))))))) (recurse the-list))))

This version of the program is a little harder to follow. It defines a closure called recurse that can be called with only one parameter rather than two. (For more information on closures, see Resources.) We don't need to pass in the-string to recurse because it is already in the parent environment and does not change from call to call. Because recurse is defined within the is-in-list2 function, it can see all of the currently defined variables, so they don't need to be re-passed. This shaves off one variable being passed at each iteration.
Using a closure instead of passing the parameter doesn't make a lot of difference in this trivial example, but it can save a lot of typing, a lot of errors, and a lot of overhead involved in passing variables in more complex functions.
The way of making recursive closures used in this example is a bit tedious. This same pattern of creating a recursive closure using letrec and then calling it with an initial seed value occurs over and over again in recursive programming.
In order to make programming recursive patterns easier, Scheme contains a shortcut called the named let. This construct looks a lot like a let except that the whole block is given a name so that it can be called as a recursive closure. The parameters of the function built with the named let are defined like the variables in a regular let; the initial seed values are set the same way initial variable values are set in a normal let. From there, each successive recursive call uses the parameters as new values.
Named let's are fairly confusing to talk about, so take a look at the following code and compare it with the code in Listing 7.

Listing 8. Named let example

(define is-in-list2 (lambda (the-list the-string) ;;Named Let ;;This let block defines a function called "recurse" that is the ;;body of this let. The function's parameters are the same as ;;the variables listed in the let. (let recurse ;;internal-list is the first and only parameter. The ;;first time through the block it will be primed with ;;"the-list" and subsequent calls to "recurse" will ;;give it whatever value is passed to "recurse" ( (internal-list the-list) ) ;;Body of function/named let block (if (null? internal-list) #f (if (equal? the-string (car internal-list)) #t ;;Call recursive function with the ;;rest of the list (recurse (cdr internal-list)))))))

The named let cuts down considerably on the amount of typing and mistakes made when writing recursive functions. If you are still having trouble with the concept of named lets, I suggest that you thoroughly compare every line in the above two programs (as well as look at some of the documents in the Resources section of this article).
Our next example of a recursive function on lists will be a little more complicated. It will check to see whether or not a list is in ascending order. If the list is in ascending order, the function will return #t; otherwise, it will return #f. This program will be a little different because in addition to having to examine the current value, we will also have to remember the last value processed.
The first item on the list will have to be processed differently than the other items because it won't have any items preceding it. For the remaining items, we will need to pass the previously examined data item in the function call. The function looks like this:

Listing 9. Scheme program to determine whether a list is in ascending order

(define is-ascending (lambda (the-list) ;;First, Initialize the algorithm. To do this we ;;need to get the first value, if it exists, and ;;use it as a seed to the recursive function (if (null? the-list) #t (let is-ascending-recurse ( (previous-item (car the-list)) (remaining-items (cdr the-list)) ) ;;Base case #1 - end of list (if (null? remaining-items) #t (if (< previous-item (car remaining-items)) ;;Recursive case, check the rest of the list (is-ascending-recurse (car remaining-items) (cdr remaining-items)) ;;Base case #2 - not in ascending order #f))))))

This program begins by first checking a boundary condition -- whether or not the list is empty. An empty list is considered ascending. The program then seeds the recursive function with the first item on the list and the remaining list.
Next, the base case is checked. The only way to get to the end of the list is if everything so far has been in order, so if the list is empty, the list is in ascending order. Otherwise, we check the current item.
If the current item is in ascending order, we then have only a subset of the problem left to solve -- whether or not the rest of the list is in ascending order. So we recurse with the rest of the list and try it again.
Notice in this function how we maintained state through function calls by passing the program forward. Previously we had just passed the remainder of the list each time. In this function though, we needed to know a little bit more about the state of the computation. The result of the present computation depended on the partial results before it, so in each successive recursive call, we pass those results forward. This is a common pattern for more complex recursive procedures.

---

Back to top

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 which 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!
What? (You say increduluously!) 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 tertiary 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;.
(We'll discuss loop variables later in the article.)
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 misordered state change again!

Introduction to Recursion

Hi! So you're all set to dive into recursive programming. Well, this page is about the basics. The definition. The meaning. And a small cute example.

I assume that you have a fair knowledge of one of the languages: C, C++, Pascal, etc. which supports recursion.

First the formalities. Meaning of Recursion. You may skip it if you already know what the concept is.

Recursion In normal procedural languages, one can go about defining functions and procedures, and 'calling' these from the 'parent' functions. I hope you already know that. Some languages also provide the ability of a function to call itself. This is called Recursion. Factorial Factorial is a mathematical term. Factorial of a number, say n, is equal to the product of all integers from 1 to n. Factorial of n is denoted by n! = 1x2x3...x n. Eg: 10! = 1x2x3x4x5x6x7x8x9x10 The simplest program to calculate factorial of a number is a loop with a product variable. Instead, it is possible to give a recursive definition for Factorial as follows: 1) If n=1, then Factorial of n = 1 2) Otherwise, Factorial of n = product of n and Factorial of (n-1) Check it out for yourself; it works. The following code fragment (in C) depicts Recursion at work. int Factorial(int n) { if (n==1) return 1; else return Factorial(n-1) * n; }

The important thing to remember when creating a recursive function is to give an 'end-condition'. We don't want the function to keep calling itself forever, now, do we? Somehow, it should know when to stop. There are many ways of doing this. One of the simplest is by means of an 'if condition' statement, as above. In the above example, the recursion stops when n reaches 1. In each instance of the function, the value of n keeps decreasing. So it ultimately reaches 1 and ends. Of course, the above function will run infinitely if the initial value of n is less than 1. So the function is not perfect. The n==1 condition should be changed to n<=1. Imagination is a very hard thing. Imagination of Recursion is all the more tricky. Think of clones. Say you have a machine to make clones of yourself, and (for lack of a better pass-time) decide to find the factorial of a number, say 10, using your clones. So, being smart, this is what you do: First, there's only You. Let's call you You-1. You have the number 10 in your pocket. Being smart, you know that all you need to find the factorial of 10 (10*9*...*2*1) is to somehow obtain the value of 9 factorial (9*8*..*2*1), and then just multiply it with 10. So that's what you do. You turn on your machine and out pops a clone! You give the clone You-2 strict instructions to find the factorial of 9 and make it quick! Your job is done for a while, so you (You-1) stretch on your sofa sipping on your lemonade. Meanwhile... You-2 is (you guessed it) just as smart as you! He tucks his number (9) into his pocket, turns on the machine, and out pops a clone (You-3). The new clone is given the job of 8-factorial, which it proceeds to do while (unbeknownst to you) You-2 is sipping on his own glass of lemonade on his own sofa. And so the story goes on until finally one fine day... Out pops You-10 who is given strict instructions (by You-9) to get the factorial of 1. Now, You-10, being just as smart as any of the other you's, knows very well that the factorial of 1 is... 1. So he says to You-9 (who was just about to doze off on his sofa), "Here's your factorial of 1." You-9 snatches the result from his subordinate You-10, takes out his plasma gun, and zaps You-10 out of existence. He scribbles on a piece of paper, calculating the product of the value he got from You-10 with the number in his pocket, 2. "Heh, heh, heh" he thinks, and goes to his boss, You-8, saying,"Here's your factorial of 2..." ...blah...blah... and finally You-2 wakes you up from your slumber, and says to you, "Here's your factorial of 9" You zap him off, multiply by the 10 in your pocket, and There You Have It !! Now, wasn't that simple? Here, 'You' were the function. The 'clones' are merely new instances of the same function. They all think and act alike. At one point, there are 10 You's (which occupies a lot of memory space). As soon as an instance returns a value and finishes its job, it is zapped off from memory. Recursion can get much, much trickier than that - get your fundas right.