Sign in to follow this  

Understanding Recursion

This topic is 3115 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am working out of a C++ book and I ran across a problem that I wasn't quite sure how they wanted me to solve and so I looked at the answer key that came with the book and it give me this code as an answer to finding the minimum number from a set of numbers.
int recursiveMinimum(const int a[], int low, int high)
{
	if(low == high)
	{
		cout << "Returning " << a[low] << endl;
		return a[low];
	}

	cout << "Making recursive call with low = " << low + 1 << " and high = " << high << endl;

	int min = recursiveMinimum(a, low + 1, high);
	
	cout << "Min variable " << min << endl;

	return ( (a[low] < min) ? a[low] : min);
}

The cout statements were to help me follow flow of the recursive program and they appear as follows:
Quote:
9 2 16 10 17 12 19 19 2 5 Making recursive call with low = 1 and high = 9 Making recursive call with low = 2 and high = 9 Making recursive call with low = 3 and high = 9 Making recursive call with low = 4 and high = 9 Making recursive call with low = 5 and high = 9 Making recursive call with low = 6 and high = 9 Making recursive call with low = 7 and high = 9 Making recursive call with low = 8 and high = 9 Making recursive call with low = 9 and high = 9 Returning 5 Min variable 5 Min variable 2 Min variable 2 Min variable 2 Min variable 2 Min variable 2 Min variable 2 Min variable 2 Min variable 2 Smallest number is 2
I understand up to Returning 5 variable and the first Min variable 5 statement however after that I get a little lost as to what the recursion is doing. If anyone can help me follow this better that would be great. Thanks.

Share this post


Link to post
Share on other sites
Have you tried to step through the code with a debugger? Recursion might seem difficult and complicated at first, but if you get used to it it becomes easier.

So recursiveMinimum() is calling itself over and over again with all of its arguments unchanged except for its low argument, that is incremented with every call, i.e. the deeper the recursion, the higher is low.

The last recursive call to recursiveMinimum() (where low = high = 9) returns the last integer stored in a[] (i.e. a[9] = 5). After the function returns, execution resumes in the penultimate call of recursiveMinimum() at the line where the last recursive call was made. The penultimate call to recursiveMinimum() (where low = 8) takes the returned value, stores it in "min" and compares it against the value stored in a[] at the index 8 and returns the smaller of both values. Then, one level higher in the recursion, this value gets compared against the value a[] at the index 7. This goes on until the programm reaches the first call of recursiveMinimum() and on this way it is alway returning the smallest value in a[] until then (from behind).

So basically what this code does is to take the last two values stored in a[], keeps the the smaller one of the two and discards the bigger one. Then it compares the value it kept agains the third value from behind and keeps the smaller one and compares it against fourth value from behind and keeps the smaller one of both and so on until it reaches the first value.

I hope this helped and I made myself clear, feel free to ask of anything is still unclear.

Share this post


Link to post
Share on other sites
From what it sounds like you're generally there, there's only 2-3 more lines that seem to be confusing. I'll skip the first part up until that Returning 5.

So when it hits the last item, low == high (both set at 9). So it calls this:


if(low == high)
{
cout << "Returning " << a[low] << endl;
return a[low];
}



That shows the "Returning 5" (a[9] = 5). It returns 5 and goes to the previous recursive call where low = 8, high = 9, thus changing:


int min = recursiveMinimum(a, low + 1, high);



Into:


int min = 5;



By the next line we obviously simply print "Min variable 5". Next is the tricky line:


return ( (a[low] < min) ? a[low] : min);



This is basically:


if (a[low] < min)
{
return a[low];
}

//If it ISN'T less then..
return min;



Currently our variables are: low = 8, high = 9, min = 5. So a[low] = a[8] = 2. So, we return 2 to the previous iteration of the function again setting min, but setting min = 2;

From there on out it basically checks every single item in that list against 2 to see if the item is smaller than 2.

Hopefully this helps!

Share this post


Link to post
Share on other sites

This topic is 3115 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this