Public Group

# Understanding Recursion

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

## 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 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 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 on other sites
If you understand recursion:

If you do not understand recursion:

-- open this link in new window.

##### Share on other sites
Quote:
 Original post by AntheusIf you understand recursion:-- close your browserIf you do not understand recursion:-- open this link in new window.

Lol, that was funny, man.

1. 1
2. 2
3. 3
Rutin
21
4. 4
5. 5

• 14
• 30
• 13
• 11
• 11
• ### Forum Statistics

• Total Topics
631778
• Total Posts
3002308
×