Question & Answer: C++ code: Recursion vs Iterative functions……

C++ code:

Recursion vs Iterative functions.

For this assignment you will make a Recursion class with two recursive member functions.

a) Implement overloaded member functions called binSearchRec the recursive binSearchRec algorithm presented in this chapter, starting on page 68 for an array of vehicles. Use a vector instead of an array.

– Sort by year then call a recursive function to do a binary search which lists out the make, model and year for the first year found (or report accordingly) that matches the for a user input.

then

– Sort by make then call a recursive function to do a binary search which lists out the make, model and year for the first year found (or report accordingly) that matches the for a user input.

then

– Sort by model then call a recursive function to do a binary search which lists out the make, model and year for the first year found (or report accordingly) that matches the for a user input.

Read in the vehicles from a vehicle file (vehiclein.txt) that has a year, make, and model. Each vehicle is separated with a | (straight bar) on it’s own line. (Note that make and models might have spaces in them)

b) Implement a member function with the same functional requirements, except instead of a recursive member function, use an iterative (non-recursive) binarySearchIter. Your iterative function (with loops instead of recursion) should produce the same results as your recursive function. You can place this member function in your recursion.h and recursion.cpp files.

You will need 4 files: main.cpp, recursion.cpp, recursion.h and vehiclein.txt plus your readme.txt and makefile all zipped together

vehiclein.txt file:

2010

Ford

Escape

2014

BMW

328xi

2014

BMW

428xi

2012

Ford

Fusion SE

2014

Lamborghini

Gallardo

pg 68:

Expert Answer

Solution===================

main.cpp====

#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include <algorithm>
#include “recursion.h”

using namespace std;

vector<Vehicle> allVehicles;

//Sorting comparators////////////////////////
bool sortByYear(Vehicle v1, Vehicle v2){
return v1.year<v2.year;
}

bool sortByMake(Vehicle v1, Vehicle v2){
return v1.make<v2.make;
}

bool sortByModel(Vehicle v1, Vehicle v2){
return v1.model<v2.model;
}
/////////////////////////////////////////////

//For displaying content of the whole vector
void displayVectorContents(){
for(auto &v : allVehicles){
cout<<v.year<<“, “<<v.make<<“, “<<v.model<<endl;
}
}

//File to vector
void populateAllVehiclesFromFile(){

ifstream inFile(“vehiclein.txt”);
string data;

while (inFile.good()) {

Vehicle v;

getline(inFile, data);
v.year=stoi(data);

getline(inFile, data);
v.make=data;

getline(inFile, data);
v.model=data;

getline(inFile, data);

allVehicles.push_back(v);

}

inFile.close();

}

int main(int argc, char** argv) {

cout<<“Vector contents: “<<endl;
populateAllVehiclesFromFile();
displayVectorContents();

sort (allVehicles.begin(), allVehicles.end(), sortByYear);
cout<<“n Vector after being sorted by Year”<<endl;
displayVectorContents();

cout<<“Searching 2014, Recursively: “<<endl;
binSearchRecYear(allVehicles,2014,0,4);
cout<<“Iteratively: “<<endl;
binSearchIterYear(allVehicles,2014,0,4);

sort (allVehicles.begin(), allVehicles.end(), sortByMake);
cout<<“nn Vector after being sorted by Make”<<endl;
displayVectorContents();

cout<<“Searching BMW, Recursively: “<<endl;
binSearchRecMake(allVehicles,”BMW”,0,4);
cout<<“Iteratively: “<<endl;
binSearchIterMake(allVehicles,”BMW”,0,4);

sort (allVehicles.begin(), allVehicles.end(), sortByModel);
cout<<“nn Vector after being sorted by Model”<<endl;
displayVectorContents();

cout<<“Searching Fusion SE, Recursively: “<<endl;
binSearchRecModel(allVehicles,”Fusion SE”,0,4);
cout<<“Iteratively: “<<endl;
binSearchIterModel(allVehicles,”Fusion SE”,0,4);

return 0;
}

recursion.h============================

#include <vector>
#include <string>
#include <iostream>
using namespace std;

struct Vehicle{
int year;
string make;
string model;
};

void binSearchRecYear(vector<Vehicle> v,int year,int first,int last);
void binSearchRecMake(vector<Vehicle> v,string make,int first,int last);
void binSearchRecModel(vector<Vehicle> v,string model,int first,int last);

void binSearchIterYear(vector<Vehicle> v,int year,int first,int last);
void binSearchIterMake(vector<Vehicle> v,string make,int first,int last);
void binSearchIterModel(vector<Vehicle> v,string model,int first,int last);

recursion.cpp==============================

#include “recursion.h”

///All recursive binary search function////////////////////
void binSearchRecYear(vector<Vehicle> v,int year,int first,int last){
int mid;

if(first > last){
cout<<“Vehicle not found”;
}else{
mid = (first+last)/2;

if(v[mid].year==year){
cout<<“Found at index “<<mid<<endl;
return;
}else if(v[mid].year>year){
binSearchRecYear(v,year,first,mid-1);
}else{
binSearchRecYear(v,year,mid+1,last);
}
}
}

void binSearchRecMake(vector<Vehicle> v,string make,int first,int last){
int mid;

if(first > last){
cout<<“Vehicle not found”;
}else{
mid = (first+last)/2;

if(v[mid].make==make){
cout<<“Found at index “<<mid<<endl;
return;
}else if(v[mid].make>make){
binSearchRecMake(v,make,first,mid-1);
}else{
binSearchRecMake(v,make,mid+1,last);
}
}
}

void binSearchRecModel(vector<Vehicle> v,string model,int first,int last){
int mid;

if(first > last){
cout<<“Vehicle not found”;
}else{
mid = (first+last)/2;

if(v[mid].model==model){
cout<<“Found at index “<<mid<<endl;
return;
}else if(v[mid].model>model){
binSearchRecModel(v,model,first,mid-1);
}else{
binSearchRecModel(v,model,mid+1,last);
}
}
}

/////////////////////////////////////////////////////////////////

////////All iterative///////////////////////////////////////////
void binSearchIterYear(vector<Vehicle> v,int year,int first,int last){
int mid;

while(first <= last){
mid = (first+last)/2;

if(v[mid].year==year){
cout<<“Found at index “<<mid<<endl;
return;
}else if(v[mid].year>year){
last=mid-1;
}else{
first=mid+1;
}
}
cout<<“Vehicle not found”;
}

void binSearchIterMake(vector<Vehicle> v,string make,int first,int last){
int mid;

while(first <= last){
mid = (first+last)/2;

if(v[mid].make==make){
cout<<“Found at index “<<mid<<endl;
return;
}else if(v[mid].make>make){
last=mid-1;
}else{
first=mid+1;
}
}
cout<<“Vehicle not found”;
}

void binSearchIterModel(vector<Vehicle> v,string model,int first,int last){
int mid;

while(first <= last){
mid = (first+last)/2;

if(v[mid].model==model){
cout<<“Found at index “<<mid<<endl;
return;
}else if(v[mid].model>model){
last=mid-1;
}else{
first=mid+1;
}
}
cout<<“Vehicle not found”;
}

///////////////////////////////////////////////////////////////

Output==========================

Still stressed from student homework?

Get quality assistance from academic writers!

Order now