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:
  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:

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: 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. The calls to factorial() are evaluated in reverse order. The evaluation process continues until the value 24 is returned by the call factorial (4). 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->data;      // 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".


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:

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.
  2. In the second part, you will download the functioning code and implement additional recursive functions.

Part 1

Answer the following questions:
  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

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.

CS Dept Home Page
CS Dept Class Files
CS210 Class Files


Copyright: Department of Computer Science, University of Regina.