Stuck on recursion

[decoy98]

Hello, I am looking to implement a method in my class that uses recursion to find the largest number. The idea is finding a midpoint value where I can start comparison and divide the array into two halves. Once the left and right half has finished doing the instruction, the code should return to the base case. Here is what I have so far...

RecursionArray.h

#include <sstream>

using namespace std;

#ifndef RECURSIONARRAY_H_
#define RECURSIONARRAY_H_

class RecursionArray {
public:
	RecursionArray();
	virtual ~RecursionArray();
	void input();
	int getLargestNum(int size, int partition_head, int partition_tail) const;

	friend ostream & operator << (ostream& output, RecursionArray& rhs);
private:
	int nums[100];
};

#endif /* RECURSIONARRAY_H_ */

RecursionArray.cpp

#include <iostream>
#include <sstream>
#include "RecursionArray.h"
using namespace std;

void RecursionArray::input() {
	int i = 0;
	cout << "Please enter some integers [MAX: 100], type \"x\" to proceed: " << endl;
	while (i < 100) {
		cin >> nums[i];
		i++;
	}
}

int RecursionArray::getLargestNum(int size, int partition_head, int partition_tail) const {
	//	if (n==0)
	//	return -infinity;
	// 5 7 55 77 52 80 99 26 90
	// 77 55 5 99 90
	// 77 5 99
	// 99
	int middle = 0;
	int largest_num = 0;
	if (partition_head >= partition_tail) {	// if there is 1 element
		return nums[0];	// return the only element
	}
	else {
		middle = (partition_tail-partition_head)/2;
		getLargestNum(size, partition_head,middle);
		getLargestNum(size, middle+1,partition_tail);

		// Do some instructions here to get the max number
	}
}

ostream& operator<<(ostream& output, RecursionArray& rhs) {
	output << "Recursion Array:" << endl;
	for (int i=0;i < 100; i++) {
		output << rhs.nums[i] << " ";
		if (i == 50)
			output << "\n";
	}
	output << endl;
	return output;
}

[dhayden]

When RecursionArray::input returns, you lose the knowledge of now may items were input. I think you need to store the size as a member of RecursionArray, or better yet, store the items in a std::vector<> and let it take care of the details for you.

Line 40: you don't need to pass in the size.

Line 50. Here you've reduced the partition so a single element whose index is partition_head. The largest value in that partition is (drum roll....) the value at partition_head :). So return nums[partition_head], not nums[0].

Line 53. if partition_head is 10 and partition_tail is 20, then you compute middle as (15-10)/2, which equals 5. You want to get 15 instead. So review how to compute the middle of two values.

Lines 54 & 55. You'll want to remember the return values, so make these:

		int leftMax = getLargestNum(size, partition_head,middle);
		int rightMax = getLargestNum(size, middle+1,partition_tail);

This gives you the maximum value in each half of your partition. So the max value of the whole partition is just the maximum of these two values. That's what you want to put at line 57.