Question

Add a recursive Boolean function called checkRecurse to class IntegerLinkedList to check if any two consecutive integers in the linked list are equal (return true in this case, false otherwise). You may assume that the list is not empty.

A recursion “helper” function is already included in class IntegerLinkedList. You only need to write the recursive function.

For example, checkRecurseHelper() should return true for the linked list shown below. A main function (prob3.cpp) is given to you to add data values to the linked list and test your function. Other examples are given in the main function.

Note:

A non-recursive version of the function will get no credit. The function should not have any loops at all. Do not use any global variables. Do not add member variables to the class. Do not change the contents of the linked list.

Write the recursive function in IntegerLinkedList.cpp.

You can change the main function for your own testing. Your code will be tested with a similar main function.

*IntegerLinkedList.cpp

// ADD ANSWER TO THIS FILE

#include "IntegerLinkedList.h"

bool IntegerLinkedList::checkList() {
   // COMPLETE THIS FOR PROBLEM 2
}

bool IntegerLinkedList::checkRecurse (SNode *ptr) {
// COMPLETE THIS FOR PROBLEM 3

}

void IntegerLinkedList::addFront(int x) {
SNode *tmp = head;
   head = new SNode;
   head->next = tmp;
   head->elem = x;
}

// recursion helper function called from main for PROBLEM 3
bool IntegerLinkedList::checkRecurseHelper () {
return checkRecurse(head);
}

* IntegerLinkedList.h

#pragma once

class SNode {
public:
int elem;
SNode *next;
};

class IntegerLinkedList {
private:
SNode *head;
bool checkRecurse (SNode *ptr); // for Problem 3; Implement in IntegerLinkedList.cpp

public:
IntegerLinkedList(): head(nullptr) {}
void addFront(int x);

bool checkList(); // for Problem 2; Implement in IntegerLinkedList.cpp

// recursion helper function called from main for PROBLEM 3
bool checkRecurseHelper ();
};

* prob3.cpp

//
// EDIT THIS FILE ONLY FOR YOUR OWN TESTING
// WRITE YOUR CODE IN IntegerLinkedList.cpp
//

#include
#include
#include "IntegerLinkedList.h"

using std::string;
using std::cout;
using std::endl;
bool checkAnswer(const string &nameOfTest, bool received, bool expected);

int main() {
   cout << "Check if two consecutive elements are equal (RECURSIVE)" << endl;
   {
       IntegerLinkedList mylist;
       mylist.addFront(57);
       mylist.addFront(23);
       mylist.addFront(23);
       mylist.addFront(20);
       mylist.addFront(13);
       cout << "List: 13 -> 20 -> 23 -> 23 -> 57" << endl;
       checkAnswer("", mylist.checkRecurseHelper(), true);
}
{
       IntegerLinkedList mylist;
       mylist.addFront(5);
       mylist.addFront(10);
       mylist.addFront(23);
       mylist.addFront(17);
       mylist.addFront(23);
       cout << "List: 23 -> 17 -> 23 -> 10 -> 5" << endl;
       checkAnswer("", mylist.checkRecurseHelper(), false);
}
{
       IntegerLinkedList mylist;
       mylist.addFront(17);
       mylist.addFront(17);
       mylist.addFront(25);
       mylist.addFront(10);
       mylist.addFront(5);
       cout << "List: 5 -> 10 -> 25 -> 17 -> 17" << endl;
       checkAnswer("", mylist.checkRecurseHelper(), true);
}
   {
       IntegerLinkedList mylist;
       mylist.addFront(17);
       cout << "List: 17" << endl;
       checkAnswer("", mylist.checkRecurseHelper(), false);
}
   // system("pause"); // comment/uncomment if needed
}

bool checkAnswer(const string &nameOfTest, bool received, bool expected) {
       if (received == expected) {
               cout << "PASSED " << nameOfTest << ": expected and received " << received << endl;
               return true;
       }
       cout << "FAILED " << nameOfTest << ": expected " << expected << " but received " << received << endl;
       return false;
}

Answer 1

For this, we can forumulate our recursive function IntegerLinkedList::checkRecurse (SNode *ptr) as follows.

Base case 1: if ptr is NULL, result is obviously false

Base case 2 : if ptr is not NULL and ptr->next is also NULL, we return true if ptr->elem is equal to ptr->next->elem

Recursive case: Else, we can call the same function recursively with ptr->next as argumement

This formulation nicely translates to code. Following is the code of IntegerLinkedList.cpp

---- code begin ----

 #include "IntegerLinkedList.h" bool IntegerLinkedList::checkList() { // COMPLETE THIS FOR PROBLEM 2 } bool IntegerLinkedList::checkRecurse (SNode *ptr) { // COMPLETE THIS FOR PROBLEM 3 if (!ptr) return false; if (ptr->next && ptr->elem == ptr->next->elem) return true; return checkRecurse(ptr->next); } void IntegerLinkedList::addFront(int x) { SNode *tmp = head; head = new SNode; head->next = tmp; head->elem = x; } // recursion helper function called from main for PROBLEM 3 bool IntegerLinkedList::checkRecurseHelper () { return checkRecurse(head); }

 ---- code end ------ 

Also, iostream has to be added to include of prob3.cpp.

Output: