Previous Section
 < Free Open Study > 
Next Section


7.11 Tracing the Execution of Recursive Function Insert

Earlier we wrote a recursive Insert function that inserts a new node into a dynamically allocated linked list. To follow the execution of Insert, let's put addresses on the nodes in the list. In the following diagram, the number above a node is the base address of the node. The number beneath the next member is the address of the next data member only. The external pointer to the list is stored in location 010.

Click To expand

Here is the function template we will trace:

template<class ItemType>
void Insert(NodeType<ItemType>*& listPtr, ItemType item)
{
  if (listPtr == NULL || item < listPtr->info)
  {
    // Save current pointer.
    NodeType<ItemType>* tempPtr = listPtr;
    // Get new node.
    listPtr = new NodeType<ItemType>;
    listPtr->info = item;
    listPtr->next = tempPtr;
  }
  else Insert(listPtr->next, item);
}

Our trace must keep track of listPtr, item, and the return address. The local variable tempPtr also has a place in the activation record. Rather than give a specific return address, however, we use the convention that R0 is the return address from the nonrecursive call and R1 is the return address from the recursive call. We trace Insert(listData, item), where item is 11. Recall that the formal parameter listPtr is passed by reference and item is passed by value. Here is what the activation record looks like after the nonrecursive call:

Click To expand

As the code begins its execution, the value stored in the place named in listPtr (location 010) is examined (because listPtr is a reference parameter). This value is not NULL, so item is compared with the info data member of the node pointed to by location 010. Eleven is greater than 7, so the function is called again recursively.

Click To expand

The value stored in the place named in listPtr (that is, location 014) is not NULL and 11 is greater than 9, so the function is called again recursively.

Click To expand

The value stored in the place named in listPtr is not NULL but 11 is less than 13, so the then clause is executed and the following steps are performed. The value in the place named in listPtr is copied into tempPtr. The new operator is executed and the address of a node of type NodeType is stored into the place named in listPtr. The stack now looks as follows assuming that the address of the new node is 028:

Click To expand

listPtr has not changed! Didn't we just store the address 028 there? No, we stored 028 into the place named in listPtr: in location 018, the next member of the previous node. Our list now looks like this:

Click To expand

The next two statements store item into listPtr->info and tempPtr into listPtr-> next, completing the insertion.

Let's see what the activation records would look like at this point if we had passed listPtr as a value parameter:

Click To expand

When the new operator is executed, the address of a node of type NodeType is stored into listPtr-not the place named in listPtr. Therefore 028 is stored into the activation record member listPtr, not in the next data member of the preceding node as is the case when listPtr is a reference parameter. The next data member of the new node is set properly, but the pointer to the new node is stored in the activation record that is removed when the function exits. Thus the rest of the list is lost. In fact, if you use this incorrect version to build the list, the list is empty. (Can you explain why?)

Our recursive Insert function works properly because the first parameter is the address in memory of either the external pointer to the list or the next data member of a node in the list.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)