CS210 Lab: Recursion
Prelab Questions:
For a review of relevant topics click
here.
Highlights of This Lab:
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:
 general (recursive) casethe 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)
 base casethe 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 * (n1) * (n2) * ... * 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 * (n1)!
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 (n1)!
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 (n1);
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 reachedthat 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)
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)
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:
 Problems in mathematics
 For instance, calculating factorials or exponents
 Computer graphics
 Compiler design
 Artificial intelligence
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 : ";
writeSub(head);
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".
writeSub(head)
↓ RECURSIVE STEP
Output 'a' writeSub(p>next)
↓ RECURSIVE STEP
Output 'b' writeSub(p>next)
↓ RECURSIVE STEP
Output 'c' writeSub(p>next)
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.
{
insertEndSub(head,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:
InsertEndSub(head,'!')
↓ 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.
 In the first part, you will answer questions related to the code given in
Section 2.
 In the second part, you will download the functioning code and implement
additional recursive functions.
Part 1
Answer the following questions on a piece of paper, then scan it or take a photo of it, call it recursion_part1.pdf or recursion_part1.png:
 Although, it is not explicitly stated, what is the base case for
writeSub()?
 What is the base case for insertEndSub()?
 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.
Your primary tasks for this exercise are:
 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 



4. Postlab Exercises
For postlab exercices, click here.
Copyright: Department of Computer Science, University of Regina.