CS210 Lab: Recursion

Lab Exercise:

Click the little computer above for a detailed description.
For this excercise you will be asked to implement recursion to travel through a linked list while performing certain functions.

1. Definition of a Recursion

Recursive functions are functions that call themselves. There are two main parts to recursive functions:
1. general (recursive) case--the case for which the solution is expressed in terms of a smaller version of itself. In other words, here, the problem space is made smaller and smaller. (the smaller problem space is sent to the calling function)
2. base case--the case for which the solution can be stated nonrecursively. Here, a solid solution is found.
Let's take an example of recursion using the factorial for a positive integer.

n factorial can be represented by:
n!=n * (n-1) * (n-2) * ... * 1

For instance, 4! can be written as
4 * 3 * 2 * 1
By regrouping this, you can get: 4 * (3 * 2 * 1). Note that 3!=3 * 2 * 1, and by substitution, you can represent 4! by
4 * (3!)

You can generalize this reasoning to form the following recursive definition of factorial:
n!=n * (n-1)!
where 0! is 1. Using this, you can evaluate 4! with the following sequence of computations:

4!=4 * (3!)
=4 * (3 * (2!))
=4 * (3 * (2 * (1!)))
=4 * (3 * (2 * (1 * (0!))))
=4 * (3 * (2 * (1 * (1))))
The first four steps in this computation are recursive, with n! being evaluated in terms of (n - 1)!. The final step (0!=1) is not recursive. This demonstates the two main parts of recursive functions:
n! = {  1 if n = 0 (base case) n * (n - 1)! if n > 0 (recursive step)
Notice that in the recursive step, you are dealing with a smaller and smaller problem space by calculating (n-1)!

This factorial function can be represented by the following code:

```long factorial (int n)
// Computes n! using recursion.
{
long result;  // Result returned

if ( n == 0 )
result = 1;
else
result = n * factorial (n-1);
return result;
}
```
Let's look at the call factorial(4) . Because 4 is not equal to 0 (the base case), the factorial() function calls factorial(3). The recursive calls continue until the base case is reached--that is, until n equals 0.
factorial(4)
↓ RECURSIVE STEP
4 * factorial (3)
↓ RECURSIVE STEP
3 * factorial (2)
↓ RECURSIVE STEP
2 * factorial (1)
↓ RECURSIVE STEP
1 * factorial (0)
↓ BASE CASE
1
The calls to factorial() are evaluated in reverse order. The evaluation process continues until the value 24 is returned by the call factorial (4).
factorial(4)
↑ RESULT 24
4 * factorial (3)
↑ RESULT 6
3 * factorial (2)
↑ RESULT 2
2 * factorial (1)
↑ RESULT 1
1 * factorial (0)
↑ RESULT 1
1
The calls to factorial() are evaluated in reverse order.

1.1 Applications of a Recursion

Recursive functions provide an elegant way of describing and implementing the solutions to a wide range of problems, including:
Recursion is good for algorithms or programs that require backtracking.

You can also apply recursion to linked lists.

2. Application: Using Recursion for Travelling through Linked Lists

The following section describes two recursive routines that can be used for printing linked lists and for inserting data at the end of the list. Later, in the lab exercise, you will answer questions about these routines and use the ideas gained from this section to implement other linked list routines.

The following pair of functions traverse a linked list, and print out the data items along the way.

```template < class DT >
void List<DT>:: write () const

// Outputs the data in a list from beginning to end. Assumes that
// objects of type DT can be output to the cout stream.

{
cout << "List : ";
cout << endl;
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template < class DT >
void List<DT>:: writeSub ( ListNode<DT> *p ) const

// Recursive partner of the write() function. Processes the sublist
// that begins with the node pointed to by p.

{
if ( p != 0 )
{
cout << p->dataItem;      // Output data
writeSub(p->next);    // Continue with next node
}
}
```
The purpose of write() is to call the recursive function writeSub() sending it the head of the linked list. With a linked list of the characters (as below), the following sequence of calls will occur resulting in the output: "abc".

↓ RECURSIVE STEP
Output 'a'     writeSub(p->next)
↓ RECURSIVE STEP
Output 'b'     writeSub(p->next)
↓ RECURSIVE STEP
Output 'c'     writeSub(p->next)
↓ BASE CASE
No output

Another example would be inserting nodes to the end of a linked list. The following pair functions do that.
```template < class DT >
void List<DT>:: insertEnd ( const DT &newDataItem )

// Inserts newDataItem at the end of a list. Moves the cursor to
// newDataItem.

{
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template < class DT >
void List<DT>:: insertEndSub ( ListNode<DT> *&p,
const DT &newDataItem )

// Recursive partner of the insertEnd() function. Processes the
// sublist that begins with the node pointed to by p.

{
if ( p != 0 )
insertEndSub(p->next,newDataItem);    // Continue searching for
else                                     // end of list
{
p = new ListNode<DT>(newDataItem,0);  // Insert new node
cursor = p;                           // Move cursor
}
}
```
The insertEnd() function initiates the insertion process, but the work is really done by the insertEndSub() recursive function. Calling the insertEnd to insert a '!' at the end of the following list of characters would result in the following calls:

↓ RECURSIVE STEP
InsertEndSub(p->next,'!')
↓ RECURSIVE STEP
InsertEndSub(p->next,'!')
↓ RECURSIVE STEP
InsertEndSub(p->next,'!')
↓ BASE CASE
Create a new node containing '!'
On the last call, p is null and the statement
p = new ListNode<DT>(newDataItem,0); // Insert new node
is executed to create a new node containing the character '!'. The address of this node is assigned to p so the the last node in the list (containing 'c') points to the new node. The following list is produced:

3. Lab Exercise

There are two Parts to this exercise.
1. In the first part, you will answer questions related to the code given in Section 2.

Part 1

1. Although, it is not explicitly stated, what is the base case for writeSub()?
2. What is the base case for insertEndSub()?
3. If you wanted to print the list backwards, how would you modify writeSub()? Why?

Part 2

• Get the files:
```Click here
To get the zipped files for this exercise
```
• Extract all of the files. Double click on Recursion.sln. This will open up the project. There are two files used in this program:
• listrec.h contains the implementation of the linked list class
• recursion.cpp -- the main program. This contains the calls to test the linked list member functions. Including the recursive ones.

1. Alter the writeSub() function so that it prints the list in reverse.

Steps include:

• Try to run this program. You should get the prompt:
Enter a list of characters :

Now, type "abc" and enter. You will get the following output:

```Enter a list of characters : abc
a b [c]
List : abc
List : abc!
a b c [!]
Press any key to continue
```

• Now, modify the writeSub() function (in the listrec.h file) so that it prints in reverse. Build and Run your program, you should get the following output:
```Enter a list of characters : abc
a b [c]
List : cba
List : !cba
a b c [!]
Press any key to continue
```
Hint: If you don't get this output, try Rebuild All from the Build Menu.

• Next, create a new recursive function that will insert the character 'a' immediately before each occurence of the character 'b'. The cursor will not change.
• add code in the listrec.h file for aBeforeb() and aBeforebSub(). The function prototypes exist, you have to add code to get them running.

• Activate the call to the aBeforeb() function (in the recursion.cpp file) by uncommenting the lines:
// testList.aBeforeb();
// testList.showStructure();

• Build and run the executable.
Your output will look like this:
```Enter a list of characters : abc
a b [c]
List : cba
List : !cba
a a b c [!]
Press any key to continue
```

• Prepare a test plan for this function that includes list containing the character 'b' at the beginning, middle, and end. A test plan form follows.

• Execute your test plan. If you discover mistakes in your implementation of the aBeforeb() function, correct them and execute your test plan again.

Test Plan for the aBeforeb Operation
Test Case       List         Expected Result     Checked
b in beginning
b in middle
b at end
multiple b's