Skip to main content

Welcome to Programming and Data Structures

Andrew Scholer

Section 28.10 A Partial Recursive Traversal

What if we want to implement SimpleLinkedList::retrieveAt(int i)?
🔗
Our base case no longer can be “hit a null pointer”. Instead, we need to stop once we have advanced a certain distance in the linked list. This means that we need to communicate through the call stack how far we are going. Any time we want to pass information from one call to the next, we need an extra parameter. In this case that extra information is “how many more steps”.
🔗
int recursiveRetrieveAt(ListNode* current, int stepsLeft);
When we call the member function retrieveAt, we will pass the head pointer and the index requested:
🔗
int SimpleLinkedList::retrieveAt(int index) {
    return recursiveRetrieveAt(head, index);
}
The recursive function will then check to see if stepsLeft is zero. If it is, we are at the requested index and can return the data in the current node. If not, we make a recursive call, passing the next pointer and decrementing stepsLeft by one. (We are one step closer to the answer.) Whatever answer comes back, we just return back to our caller.
🔗
int recursiveRetrieveAt(ListNode* current, int stepsLeft) {
    // Missing : if current == nullptr throw exception

    if(stepsLeft == 0)
        return current->data;
    else {
        return recursiveRetrieveAt(current->next, stepsLeft - 1);
    }
}

Insight 28.10.1.

Sometimes recursion is a process of “I don’t know the answer, but I can ask someone else who will know”. In that case, no call but the base case contributes anything to the answer, they all just pass along the answer once it is found.
🔗
🔗
A call to retrieveAt(2) on a list with the values 6, 10, 3 would produce this series of calls and returns:
  • SimpleLinkedList::retrieveAt(2) calls recursiveRetrieveAt(head, 2) (passes the 6 node as the parameter)
    🔗
  • recursiveRetrieveAt({6 node}, 2) calls recursiveRetrieveAt(current->next, 1) (passes the 10 node as the parameter)
    🔗
  • recursiveRetrieveAt({10 node}, 1) calls recursiveRetrieveAt(current->next, 0) (passes the 3 node as the parameter)
    🔗
  • recursiveRetrieveAt({3 node}, 0) sees that stepsLeft is zero and returns 3
    🔗
  • The call in the 10 node receives the 3 and returns it
    🔗
  • The call in the 6 node receives the 3 and returns it
    🔗
  • SimpleLinkedList::retrieveAt receives the 3 and returns it to the caller
    🔗
🔗
Listing 28.10.1.
🔗

Checkpoint 28.10.1.

If we call the printRange function below with a list containing 5, 10, 15, 20, 25 and parameters (head, 1, 3), organize the series of function calls that will be made. You will not use all the blocks.
🔗
void printRange(ListNode* current, int stepsToStart, int stepsToEnd) {
    if(current == nullptr || stepsToEnd < 0) {
        return;
    }
    if(stepsToStart < 1) {
        cout << current->data << endl;
    }
    printRange(current->next, stepsToStart - 1, stepsToEnd - 1);
}
Hint.
The base case will be a call, so it should be in the list (and the last block).
🔗
🔗
🔗

Checkpoint 28.10.2.

In the printRange function, what will the current == nullptr part of the base case do?
🔗
void printRange(ListNode* current, int stepsToStart, int stepsToEnd) {
    if(current == nullptr || stepsToEnd < 0) {
        return;
    }
    if(stepsToStart < 1) {
        cout << current->data << endl;
    }
    printRange(current->next, stepsToStart - 1, stepsToEnd - 1);
}
  • It will stop recursion if the indexes are too large.
  • It will stop recursion when we are done with the items to be printed.
  • It will handle the case where the start index is after the end index.
🔗
You have attempted of activities on this page.
🔗
PrevTopNext