CS 3358 Recursion

This assignment has four parts pertaining to the recursion implementation. The parts of code are given in the .cpp and .h files. The places you need to fill out in the code are marked by // TODO.

In this assignment, you are asked to implement four recursive functions. Note that you are not allowed to use iterative implementations. You are generally expected to implement the functions whose headers are given in the code files, and you are not expected to implement additional helper functions to implement them.

Part 1

In mypow1.cpp, implement the recursive function Pow to compute the value of a power function xⁿ based on the basic recursion method that you learned from class, where the inputs are a number x and an integer n >= 0, and the output is the value of xⁿ. Note that the basic recursion method uses the definition, i.e., xⁿ = x*x^n-1 for n >= 1 and xⁿ = 1 for n = 1 and leads to the O(n) run-time.

#include < iostream >

using namespace std;

double Pow(double x, int n)
{
// TODO
}

int main()
{
cout << "To calculate x^n..." << endl;

double x;
int n;
cout << "Please enter x: ";
cin >> x;
cout << "Please enter n: ";
cin >> n;

if(x == 0) {
if (n > 0) {
cout << 0 << endl;
} else {
cout << "x^n is not defined." < }
} else {
cout << Pow(x,n) << endl;
}

return 0;
}

Part 2

In mypow2.cpp, implement the recursive function ImprovedPow to compute the value of xⁿ based on the improved recursion method using repeated squaring that you learned from class, where the inputs are a number x and an integer n >= 0, and the output is the value of xⁿ. Note that the improved recursion method leads to the O(log n) run-time.

#include < iostream >

using namespace std;

double ImprovedPow(double x, int n)
{
// TODO
}

int main()
{
cout << "To calculate x^n..." << endl;

double x;
int n;
cout << "Please enter x: ";
cin >> x;
cout << "Please enter n: ";
cin >> n;

if(x == 0) {
if (n > 0) {
cout << 0 << endl;
} else {
cout << "x^n is not defined." < }
} else {
cout << ImprovedPow(x,n) << endl;
}

return 0;
}

Part 3

In poweroftwo.cpp, implement the recursive function CheckPowerOfTwo to check if a given non-negative integer n is a power of 2. Return true if it is a power of 2. Otherwise, return false.

#include < iostream >

using namespace std;

bool CheckPowerOfTwo(int n)
{
// TODO
}

int main() {

int val;
cout << "Enter an integer (0,1,...): ";
cin >> val;

if (CheckPowerOfTwo(val)) {
cout << "Power of two: true";
} else {
cout << "Power of two: false";
}

return 0;
}

Part 4

In listnode.h, implement two member functions of the class ListNode such as the destructor and the function AddNode (i.e., appending a node to the end of the list), and in mergetest.cpp, complete the implementation of the function MergeLists for the following problem: Give two sorted linked lists, merge them as a single sorted list. It should be done by joining together the nodes of the lists. The following is an example.

Two sorted lists: see image.

Merged list: see image.

#ifndef _LISTNODE_H_
#define _LISTNODE_H_

using namespace std;

struct Node {
int value;
Node *next;
};

class ListNode{
public:
ListNode() { head = nullptr; } // Constructor
~ListNode(); // Destructor
Node* GetHeadNode(); // Get the first node in the list
void Display();
void AddNode(int x); // Append a node the end of the list

private:
Node* head;
};

// Destructor
ListNode::~ListNode() {
// TODO
}

// Append a node to the end of the list
void ListNode::AddNode(int x) {
// TODO
}


// Return the head node pointer
Node* ListNode::GetHeadNode() {
return head;
}

// Display all the elements in the linked list
void ListNode::Display() {
if (head == nullptr) {
cout << "List is empty" << endl;
} else {
Node *current = head;
while (current != nullptr) {
cout << current->value << ' ';
current = current->next;
}
}
cout << endl;
}

#endif

#include < iostream >
#include "listnode.h"

using namespace std;

Node* MergeLists(Node* head1, Node* head2) {
if (head1 == NULL)
return head2;

if (head2 == NULL)
return head1;

Node* node = NULL;

if (head1->value <= head2->value)
{
node = head1;
node->next = MergeLists(head1->next, head2);
}
else
{
node = head2;
node->next = MergeLists(head1, head2->next);
}

return node;
}

int main() {
// Create two sorted lists
ListNode list1;
ListNode list2;

int val;

// Prompt the user to populate the lists
cout << "Type in an integer to insert to list1, e.g., 1,2,3,... (-1 to quit): ";
do {
cin >> val;
if (val != -1) {
list1.AddNode(val);
}
}
while(val != -1);

cout << "Type in an integer to insert to list2, e.g., 1,2,3,... (-1 to quit): ";
do {
cin >> val;
if (val != -1) {
list2.AddNode(val);
}
}
while(val != -1);


// Display the lists
cout << "List 1: ";
list1.Display();
cout << "List 2: ";
list2.Display();

// Merge two lists
Node* merge_list = MergeLists(list1.GetHeadNode(), list2.GetHeadNode());

// Display the merged list
Node *current = merge_list;
cout << "Merge List: ";
while (current != nullptr) {
cout << current->value << " ";
current = current->next;
}

return 0;
}