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) 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)
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:
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 : ";
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)
↓ 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.
{
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 that 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 paper or in a text editor:
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?
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
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.
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
When you are finished, your program should:
Insert the char 'a' before any 'b' in the input without getting stuck
If there are multiple 'b's, your program must insert multiple 'a's
Your program must not drop or lose other parts of the input
