Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
This is a solution I came up with while trying to find a unique, extensible way to find the greatest value in a collection of integers. The real cool stuff here exists in the function get_greatest. I could have used a sorting algorithm and then returned the greatest value, but finding a recursive solution was a lot of fun. Very roughly speaking,…
/*
This is a solution I came up with while trying to find a unique, extensible way to find the greatest value in a collection of integers.
The real cool stuff here exists in the function get_greatest.
I could have used a sorting algorithm and then returned the greatest value, but finding a recursive solution was a lot of fun.
Very roughly speaking, the time complexity estimate is between O(n) and O(n^2).
Really the function runs as follows (each term is a new recursive scope): n + (n - 1) + (n - 2) + ... + (n - (n - 2)).
For example if n is 5: 5 + 4 + 3 + 2 = 14.
*/
#include <iostream>
using namespace std;
int max_of_four(int a, int b, int c, int d);
int get_greatest(int arr[], int sizeOf);
int main() {
int a, b, c, d;
cin >> a >> b >> c >> d;
int ans = max_of_four(a, b, c, d);
cout << ans;
return 0;
}
int max_of_four(int a, int b, int c, int d)
{
int arr[4] = { a, b, c, d };
return get_greatest(arr, 4);
}
int get_greatest(int arr[], int sizeOf)
{
// Base case
if (sizeOf == 1)
return arr[0];
// Recursive case
int* nxtArr = new int[sizeOf - 1];
int dntFillIndx;
if (arr[0] > arr[1])
dntFillIndx = 1;
else
dntFillIndx = 0;
int j = 0;
for (int i = 0; i < sizeOf; i++)
{
if (i == dntFillIndx)
continue;
nxtArr[j] = arr[i];
j++;
}
int greatest = get_greatest(nxtArr, sizeOf - 1);
delete [] nxtArr;
return greatest;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.