In: Computer Science
please do it in C++, will up vote!! please add snap shots of result and explanation.
You are to create a recursive function to perform a linear search through an array.
How Program Works
Program has array size of 5000
Load values into the array, equal to its index value. Index 5 has value 5, index 123 has value 123.
Pass array, key, and size to the recursive function:
int recursiveLinearSearch(int array[],int key, const int size, bool & methodStatus)
User enters key to search for, recursive function calls itself until the key is found (methodStatus is true), print out the key and number of function calls when control is returned to the main
Handle situation of key not found (return number of function calls AND methodStatus of false) – print not found message and number of calls in the main
Function returns a count of how many recursive calls were made
Value returned is the number of calls made to that point, that is, when item is found the value returned is 1 with preceding functions adding 1 to the return value until the actual number of recursive function calls are counted).
Determine smallest key value that causes stack-overflow to occur, even if you need to make array larger than 5000.
Test cases need to include, biggest possible key value, “not found” message, and a stack overflow condition.
#include <bits/stdc++.h>
using namespace std;
bool fun(int arr[], int i,int key, const int size, int &count){
if(i==size){
return false;
}
if(arr[i]==key){
return true;
}
count++;
fun(arr,i+1,key,size,count);
}
int recursiveLinearSearch(int arr[],int key, const int size, bool & methodStatus){
int count=0;
if(fun(arr,0,key,size,count))
{
methodStatus=true;
}
return count;
}
int main()
{
const int size=10000000;
int arr[size];
memset(arr,0,sizeof(arr)); // flush junk values
for(int i=0;i<=size-1;i++)
arr[i]=i;
int key;
bool methodStatus=false;
cout<<"Enter key\n";
cin>>key;
int ans=recursiveLinearSearch(arr,key,size, methodStatus);
if(methodStatus)
cout<<"Key "<<key<<" is present and number of calls made: "<<ans<<endl;
else
cout<<"Key "<<key<<" is not present and number of calls made: "<<ans<<endl;
return 0;
}
Smallest key value to my system came as 2599000. You might have to check yours.
Kindly upvote. ?