Question

3. (20 points) Write a C++ recursive function that finds the maximum value in an array (or vector) of integers without using any loops. (a) Test your function using different input arrays. Include the code. i. ii. (b) Write a recurrence relation that represents your algorithm. i. T(n) = T(n-1) + O(1) (c) Solve the recurrence relation and obtain the running time of the algorithm in Big-O notation.

Answer 1

Answer:

Following are the code to this question:

In option (i):

#include <iostream>//defining header file

using namespace std;

int findMax(int B[], int x)//defining recursive method findMax

{

if (x == 1)//defining condition when value of n==1

return B[0];//return array first element

return max(B[x-1], findMax(B, x-1)); // calling recursive method inside max method and return value

}

int main() //defining main method  

{

int B[] = {12, 24, 55, 60, 50, 30, 29};//defining array B

int x= 7;//defining integer variable and assign a value

cout << "Maximum element value of the array is: "<<findMax(B, x)<<endl;//calling method findMax and print value

return 0;

}

Output:

Maximum element value of the array is: 60

In option (ii):

$\Rightarrow \ T(n) = 1 + T(n-1)\\\Rightarrow 1 + 1 + T(n-2)\\ \Rightarrow 1 + 1 + 1 + ... n \ times \\\Rightarrow O(n)$

Explanation:

In the above-given program a recursive method "findMax" is defined, which accepts an array "B" and an integer variable "n" in its parameter, inside the method a conditional statement is used that, checks value of x equal to 1.

• If the above condition is true it will return the first element of the array and find the max number.
• Inside the main method, an array B is declared that assigns some values and an integer variable is declared, that also assigns some values, in the last step print method is used that pass value in method and prints its return value.
• In the option (ii) we calculate the Big-O notation algorithm value.