Module 0068: Recursive deﬁnitions and algorithms

Tak Auyeung, Ph.D.

December 2, 2021

1 About this module

2 What is recursion?

A recursive deﬁnition is one that involves the very deﬁnition that is being deﬁned. There are some well known ones.

Factorial can be recursively deﬁned. \(\forall n \in \mathbb {Z^+}: (n \ge 1) \Rightarrow (n! = n(n-1)!)\) and \(0! = 1\). Using this recursive deﬁnition, we can compute the value of \(4!\) as follows:

\begin {eqnarray} 4! & = & 4\cdot (3!) \\ & = & 4\cdot (3\cdot (2!)) \\ & = & 4 \cdot (3 \cdot (2 \cdot (1!))) \\ & = & 4 \cdot (3 \cdot (2 \cdot (1 \cdot (0!)))) \\ & = & 4 \cdot (3 \cdot (2 \cdot 1 \cdot 1)) \\ & = & 4 \cdot (3 \cdot (2 \cdot 1)) \\ & = & 4 \cdot (3 \cdot 2) \\ & = & 4 \cdot 6 \\ & = & 24 \end {eqnarray}

The name GNU is also recursively deﬁned. However, in this case, it is merely just for the sake of making it confusing. The deﬁnition of GNU is “GNU is not Unix”. Thus, expanding GNU twice gets “(GNU is not Unix) is not Unix”, expanding it three times get “((GNU is not Unix) is not Unix) is not Unix”, and so on. Obviously, there is no end to this. As a result, we really don’t know what GNU is.

3 Recursive algorithms

3.1 Factorial

001unsigned f(unsigned n)
002{
003  int res;
004  if (n > 0)
005  {
006   res = n * f(n-1);
007  }
008  else
009  {
010   res = 1;
011  }
012  return res;
013}

3.2 Pascal’s triangle

The C version of ﬁnding the value of an element in Pascal’s triangle is as follows:

001unsigned pascal(unsigned r, unsigned c)
002{
003  unsigned res;
004  if ((c == 0) || (c == r))
005  {
006   res = 1;
007  }
008  else
009  {
010   res = pascal(r-1,c-1) + pascal(r-1,c);
011  }
012  return res;
013}

3.3 Tower of Hanoi

Tower of Hanoi involves three poles. We can label these poles 1, 2 and 3. We start with a sorted stack of disks on pole 1, with the largest disk at the bottom, and the smallest disk at the top. We can move one disk from one pole to another pole in one move, but one restriction is that we can only move the top disk from one pole so it becomes the top disk of another pole. Another restriction is that only a smaller disk can be on top of a larger disk.

Let us try to ﬁgure out the algorithm. First, let us deﬁne the following prototype:

It is the prototype of a function that moves n disks from pole from to pole to through pole via. Is there a easy case? Sure! When n is one, we can just move it without using the via pole:

001void hanoi(int n, int from, int to, int via)
002{
003  if (n == 1)
004  {
005   printf("move from pole %d to pole %d\n",from,to);
006  }
007}

What if n > 1? In other words, what if we need to move a whole bunch of (n) disks from a source pole to a destination pole, given that we can use an intermediate pole? It’d be easy if we can move n-1 disks from the source pole to the intermediate pole, then move the last disk from the source pole to the destination pole, then move the n-1 disks from the intermediate pole to the destination pole.

This sounds easy, but how exactly are we going to move n-1 poles from the source pole to the intermediate pole? We can use the destination pole as the intermediate pole! Using the same reasoning, we can move n-1 poles from the intermediate pole to the destination pole using the source pole as an intermediate pole.

This means we can use hanoi to solve the two subproblems, but we need to change the parameters a little in each case:

001void hanoi(int n, int from, int to, int via)
002{
003  if (n == 1)
004  {
005   printf("move from pole %d to pole %d\n",from,to);
006  }
007  else
008  {
009   hanoi(n-1, from, via, to); // note the change of params!
010   hanoi(1, from, to, via); // recursion to use the base case
011   hanoi(n-1, via, to, from); // note the change of params again!
012  }
013}

3.4 Delete directory

Many operating systems do not allow the deletion of a directory that still has ﬁles or other directories inside it. As a result, if we are really sure that we want to delete a directory, we need to delete all its ﬁles and subdirectories ﬁrst. The problem is that the subdirectories may contain subsubdirectories, and so on.

How can we do this as an algorithm? When we encounter a subdirectory, we simply invoke the same function that is being used to delete the parent directory!

001void nukedir(const char *name)
002{
003  DIR *pDir = opendir(name);
004  if ((pDir == NULL) && (errno == ENOTDIR))
005  {
006   unlink(name);
007  }
008  else if (pDir != NULL)
009  {
010   struct dirent *entry;
011
012   chdir(name);
013   while ((entry = readdir(pDir) != NULL))
014   {
015     nukedir(entry->d_name);
016   }
017   closedir(*dir);
018   chdir("..");
019   rmdir(name);
020  }
021}

4 When to consider recursion?

A recursive algorithm can be converted to an iterative one, and vice versa. This is illustrated by the implementation of recursive algorithm using languages that do not support recursion. On the other hand, Lisp is a language that has no iterations (loops), but yet it can be used to implement any algorithm that contains loops.

Consequently, technically speaking, there is no diﬀerence between a recursive algorithm and its iterative counterpart.

However, to a computer scientist or a programmer, some algorithms are more simple in their recursive form. This section explores what kinds of problem lend themselves to recurisve solutions.

4.1 Recursive deﬁnitions

Any algorithm to implement a recursive deﬁnition can be done recursively. This is quite obvious! Recursion, Fibonacci, Pascal’s triangle are just a few examples.

4.2 Self similar structure

Some data structures are self similar. This means the parent (containing) structure is structurally similar to its children (contained) structures. One example is a tree structure. Each branch is a tree by itself.

A lesser known structure is a list. A non-empty list consists of a value and “the rest of the list”. “The rest of the list” is considered a list by itself.

4.3 Self similar action

A self similar action is an action that can be broken down to operations that involve the same kind of action, but with diﬀerent parameters. We have already seen an example: tower of Hanoi. There are other algorithms that ﬁt in this category.

One algorithm is called depth-ﬁrst-search. It is a search algorithm that can work on any graph and state spaces.

5 Practical issues with recursion

Although recursion may be the best form of solution, it is not always practical. This section explains the limitations of recursion, and when not to use recursion.

5.1 Implementation

Recursion is possible because most languages maintain a context per invocation of a subroutine, and not per subroutine. The “context” of an invocation includes all parameters, all auto local variables, and the return address. The entire context is saved on the stack.

001int pascal(int r, int c)
002{
003  int res;
004  if ((c == 1) || (c == r))
005  {
006   res = 1;
007  }
008  else
009  {
010    res =
011      pascal(r−1,c−1) +
012      pascal(r−1,c);
013  }
014  return res;
015}

In this example, each invocation (call) of pascal saves at least this much information on the stack:

001void test(void)
002{
003  int i;
004
005  i =
006    pascal(3,2);
007}

When pascal is called the ﬁrst time from line 006, the following context is constructed (we omit the context of invoking test and all earlier contexts):

Then, the program executes the code in pascal. When pascal is invoked again on line 011, a new context is constructed. At this point, there are two contexts (the ﬁrst one is the ﬁrst one created):

Transfer is, once again, transferred to the beginning of pascal. This time, because c = 1, we execute line 006. Immediately before we return on line 014, the stack looks like the following:

As we return, we naturally return to line 012 to continue execution based on the return address. Note that as soon as a subroutine returns, the invocation context is removed from the stack. Thus, the intermediate state of the stack is as follows (with only one context):

At this point, we have evaluated the left hand side of the additional operator. We are now ready to evaluate the right hand side of the addition operator.

Line 012 invokes pascal again, but this time the parameters are diﬀerent. We end up with the following contexts immediately after the invocation on line 012:

Control now starts from the beginning of pascal. Because c == r, we execute line 006, which changes the stack to the following state:

When we reach line 014, we return to line 010. At this point, we are ready to compute the addition of the assignment expression. Because both recursive calls to pascal returned 1s, the sum is 2. As a result, we update res so that the context is as follows:

After this, execution reaches line 014. As a result, we return a value of 2, and execution continues on line 005. Subroutine test proceeds to store the value of 2 in i.

5.2 Implementation overhead

The context of an invocation is not limited only to the parameters and local variables. It also includes the return address, as well as the saved values of hardware registers. Compared to an iterative approach, a recursive solution always has more storage overhead.

In terms of performance, however, a recursive implementation can be very competitive with respect to a equivalent iterative implementation. This is especially the case for a multi-point recursive solution (such as the tower of Hanoi, as opposed to factorial).