# 5. Recursion

Why are we talking about recursion in a data structures class?
• Recursion is implemented using a data structure we have studied.
• More importantly, recursion is used to define other data structures we will study, and the algorithms for manipulating them.

## Uses of Recursion

Definitions:
Recursion is used to define infinite sets with a finite description. Example: defining the set of natural numbers. Recursive definitions can be used to both generate and test elements of the set.
Indefinite repetition:
Recursion is used to do something an indefinite number of times without resorting to iteration constructs such as for or while loops. Example: computing the factorial of a number.
These two uses are closely related.

## Recursive Definitions

Recursive definitions reference themselves, either directly or indirectly. Recursive definitions always include:
Anchor, Base or Ground Case(s): Simple case(s) that can be handled without resort to recursion.
Recursive Relation or Rules:
Rules that inductively define complex cases in terms of simpler ones.

### Example: Natural Numbers

This is an example of defining an infinite set.
Ground Case: 0 is a natural number.
Recursive Relation:
If n is a natural number, then n+1 is a natural number.
We can generate the natural numbers by starting with the ground case, 0, and applying the recursive rule to 0 and to each newly generated element.
```  0
1 (from 0 + 1)
2 (from 1 + 1)
3 (from 2 + 1) ... etc.
```
We can test whether a number is a natural number by showing that it is possible to generate the number:
```  4 is a natural number because 4 = 3 + 1 and
3 is a natural number because 3 = 2 + 1 and
2 is a natural number because 2 = 1 + 1 and
1 is a natural number because 1 = 0 + 1 and
0 is a natural number by definition.
```

### Example: Factorial

This example shows a recursive definition of a function on an infinite domain (or equivalently, of an infinite set of pairs).

The factorial of a number n is the product of all integers from 1 to n (i.e., 1 * 2 * ... * n-1 * n ). The factorial of 0 is defined to be 1.

Ground Case: The factorial of 0 is 1.
Recursive Relation: The factorial of n is n times the factorial of n-1.
Later we see how this definition can be used to compute the factorial, using recursion instead of iteration.

## Recursive Functions

Recursion involves a different way to think about problems: a problem is decomposed into simpler problems until it is trivially solvable.

There is nothing mysterious about recursion. We use function calls to accomplish various things, and it is no different if what we want to accomplish happens to be handled by the function that we are writing. We just need to be sure that the recursion terminates!

### Solving Problems Recursively

Here is a general approach to solving a problem recursively:
Decompose the problem: Identify how you can break the problem into simpler problems of the same type. In other words, identify the recursive relation.
Compose solutions to simpler problems: Assume that you could solve simpler versions of the same problem. (This is the part students find mysterious.) Then figure out how to put those solutions together into a solution to the original problem.
Solve the simplest problem: Identify the ground case and specify its solution nonrecursively.

### Example: Factorial

Decompose the problem: The factorial operates on integers. We can make a problem involving integers smaller (simpler) by subtracting 1. The factorial of n-1 is simpler because it involves multiplying one less integer.
Compose solutions to simpler problems: If we assume we have the solution to factorial(n-1) we can get the solution to factorial(n) by multiplying by n.
Solve the simplest problem: By definition, factorial(0) = 1.

### Writing Recursive Functions in C++

A straightforward translation of the abstract definition of Factorial:
```  int Factorial (int n) {
if (n ==0)return 1;
else return n * Factorial (n - 1);
}
```

### Other Examples

We will write recursive definitions for these in class.
Count ( e list):
returns the number of times e occurs in list.
Decompose:
Compose:
Base Case:
Reverse (list):
returns reversed list.
Decompose:
Compose:
Base Case:
```  void Reverse () {
char ch;
cin.get(ch);
if (ch != '\n\') {
Reverse();
cout.put(ch);
}
}
```

## Runtime Implementation of Recursion

In the above definition, Factorial(n) calls Factorial(n-1). Suppose we allocated a single memory location for n. What would go wrong?

How does the compiler arrange to keep track of the value of n?

### Function Calls

Whenever a new function is called we need to keep track of
• Values for parameters to the function (or locations if call by reference).
• Values for local variables.
• Return address where execution continues in caller after return.
The compiler could permanently allocate memory for all these items for each defined function. Why is this a bad idea?

It is inefficient, and it does not support recursion. Instead, the compiler arranges to dynamically allocate the memory needed to store this information. New memory is allocated temporarily when a function is called, and released when it returns.

What data structure is appropriate for organizing this dynamically allocated memory?

### Runtime Stack

The answer is clear if we consider the fact that the most recent function will always exit before its caller exits. In other words, last in, first out.

The compiler arranges to store the information on a runtime stack. Each function's record on the stack is called an activation record or stack frame.

In addition to storing the information listed in the previous section (parameters, local values, and return address), each activation record also has the following.

• Pointer to caller's activation record (why?)
• Location for storing returned value.
The returned value is stacked first, before the rest of the activation record, so it will be available to the caller after the function exits. (When the stack is popped, the "top" pointer is updated to "remove" the stack frame from the logical stack, but it is still there physically long enough to use in the calling function.)

### Recursion and the Runtime Stack

Now we can see that when a function calls itself, it does not write over its own values. Each call produces a different instantiation of the function. (Will diagram example in class, similar to section 5.3.)

## Types and Uses of Recursion

### Tail Recursion

A tail recursive function is a recursive function in which the recursive call is the last statement executed in the function (if it is executed at all). For example:
```  void CountDownRecursive (int i) {
if (i >= 0) {
cout << i << ' ';
CountDownRecursive(i - 1);
}
}
```
The information in the activation record for the current call is not needed when the recursive call is made. Thus it can be written over in the recursive call, saving memory.

It is straightforward to rewrite tail recursive code as a loop. For example:

```  void CountDownIterative (int i) {
for ( ; i >= 0; i--)
cout << i << ' ';
}
```
This leads the textbook author to say that there is no advantage of tail recursion in C++. However ...

A good compiler can translate tail recursive code into iterative code. (Many Lisp compilers do this.) With such a compiler, there is an advantage to using tail recursion for some functions. Recursive definitions are sometimes much clearer than iterative ones. However recursive calls are more expensive than iteration. With tail recursion we can have readable recursive code and an efficient iterative implementation at the same time.

### Nontail Recursion

The Reverse function provides an example of a function that is not tail recursive.
```void Reverse () {
char ch;
cin.get(ch);
if (ch != '\n\') {
Reverse();
cout.put(ch);
}
}
```
(Time permitting, we will trace the execution of this to see why it works.)

Definitions that are inherently non-tail recursive are more difficult to write iteratively. This is because one must implement an explicit stack to do the job that the runtime stack did in the recursive form. For example, using an array:

```  void IterativeReverse() {
char stack[80];
register int top = 0;
cin.get(stack[top]);
while(stack[top] != '\n')
cin.get(stack{++top]);
for (top -= 2; top >= 0; cout.put(stack[top--]));
}
```
```  void IterativeReverse2() {
int ch;
stack.Clear();
cin.get(ch);
while (ch != '\n') {
stack.Push(ch);
cin.get(ch);
}
while (!stack.IsEmpty())
cout.put(stack.Pop());
}
```
In C++ the IterativeReverse implementation is the most efficient, but is more difficult to understand and maintain than the recursive one.

### Indirect Recursion

Functions can be recursive (call themselves) indirectly, that is via other functions: f can call g which calls f. An example is parsing expressions. Suppose you have a parser for each type of subexpression, and have an expression "3 + (2 * (4 + 4))". The function that processes "+" expressions would call that for "*", which in turn would call the first.

### Nested Recursion

A recursive call can also be given an argument which includes another recursive call. An example is Ackermann's function, a function that grows horrendeously fast. (For example, A(4,1) far exceeds the estimated number of atoms in the universe.)
```  A(n,m) = m+1              if n = 0
A(n-1,m)         if n > 0 and m = 0
A(n-1, A(n,m-1)) otherwise.
```
This is an example of a function that is much easier to write recursively: It has been proven that no equivalent definitions using arithmetical operators +, -, *, /, and ^ exits. Unfortunately a straightforward recursive computation is not even O(2^n) in time or space.

Nested recursion is a special kind of double recursion, where a recursive definition refers to itself more than once.

### Avoiding Unnecessary Recursion

Sometimes a straightforward recursive definition is inefficient in ways that can be avoided (unlike Ackerman's function).

The Fibonacci numbers are a sequence of numbers where the nth number in the sequence is defined as follows:

```  Fib(n) = n                   if n < 2.
Fib(n-2) + Fib(n-1) otherwise.
```
This definition can be written in C++ as follows:
```  int Fib (int n) {
if (n < 2)
return n;
else
return Fib(n-2) + Fib(n-1);
}
```
This definition is very inefficient. (In class we'll make this point with figure 5.6 from the text.) A more efficient iterative definition is:
```  int InterativeFib (int n) {
if (n < 2)
return n;
else {
register int i = 2, tmp, current = 1, last = 0;
for ( ; i <= n; ++i) {
tmp = current;
current += last;
last = tmp;
}
return current;
}
}
```
(A register declaration tells the compiler that the variables will be heavily used, so should be allocated in registers if possible.)

Sometimes there are different ways to write recursive definitions, one being more efficient than the other. This is the point of the extra credit problem in the homework.

## Backtracking

Recursion makes it easy to implement problem solving techniques in which one searches for possible solutions and backtracks when an attempted solution fails to work out.

The solution to many problems consist of a number of interacting (mutually dependent) choices. Some example problems include:

• The 8-queens problem described in the text.
• Deciding what move to make in Chess.
• Parsing sentences or expressions in an ambiguous language. "The horse raced past the barn fell."
• Planning a sequence of actions to achieve a goal.
• Traveling salesman problem: visiting cities in an order that minimizes distance.
Some choices made early during problem solving might not be compatible with other choices made later. When this happens it may be necessary to back up to the earlier choice point and try another option (for example, place the first queen on a different square; consider a different move in Chess; assign a word or sentence constituent to a different syntactic category; go to a different city first).

Backtracking is this process of backing up and trying other choices. It is easily implemented with recursion because:

• The run-time stack takes care of keeping track of the choices that got us to a given point and the remaining alternatives
• Upon failure we can get to the previous choice point simply by returning a failure code from the recursive call.
I will illustrate the general idea of backtracking by demonstrating the execution sequence on the 8 Queens problem. We will not have time to go into detail on this, so please read the text.

## Homework

Due Feb. 24th (which is also exam day).

1. Problem 1 of page 131.

2. Problem 2 of page 131. You may write pseudocode, C++, or another language.

3. Problems 3 and 4 of page 131. (A static variable is allocated just one permanent location in memory, i.e., is not on the runtime stack. Hence the same memory location is used each call.) Use the input line "abc\n" (that's the character a, followed by b, followed by c, and a newline). In addition to the information asked for in the textbook, write a paragraph comparing the results of problems 3 and 4, and indicating the significance.

4. Problem 9 of page 133. The "binomial coefficient" gives the number of combinations of n things chosen k at a time. You may write pseudocode, C++, or another language.

About "n choose k" notation. In case you are not familiar with the notation of problem #9 page 133 (our problem 4 of HW 3): The parentheses with an "n" on top and a "k" on the bottom stands for a number -- in particular the number of different ways in which you can choose k things out of a set of n things. Your job is to write a recursive function that computes this number. n and k will be the two arguments to the function.

Example: 3 things {a, b, c}, taken 2 at a time: there are 3 ways to do it: {a, b}, {a, c}, {b, c}. (Order does not matter.)

Try drawing the recursive call tree for this computation. If your function is BC then

```  ->BC(3,2)
--->BC(2,1)
----->BC(1,0)
<-----1
----->BC(1,1)
<-----1
<---2
--->BC(2,2)
<---1
<-3
```

Extra credit: Do 18 p. 133, writing the program.