Question

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.

--------------------------------------

sry mixed 2 questions!

Answer 1

#include <iostream>
using namespace std;

int recursiveLinearSearch(int array[],int key, const int size, bool & methodStatus)
{
    int count=size;
    if(size<0)
    {
        methodStatus=false;
        return 5000;
    }
    if(size==key)
    {
        methodStatus=true;
        return (5000-size);
    }
    count--;
    recursiveLinearSearch(array,key,count,methodStatus);
}

int main()
{
    int arr[5000];
    for(int i=0;i<5000;i++)
    {
        arr[i]=i;
    }
    bool methodStatus;
    int key=20000;
    int size=5000;
    int count=recursiveLinearSearch(arr,key,size,methodStatus);
    cout<<" Total calls: "<<count<<" Key: "<<key<<" methodStatus: "<<methodStatus<<endl;
    key=4000;
    count=recursiveLinearSearch(arr,key,size,methodStatus);
    cout<<" Total calls: "<<count<<" Key: "<<key<<" methodStatus: "<<methodStatus;
}

The methodstatus 0 means not found and 1 means found. The recursive function works from size n to 0;

I hope it helps.