• ### What is your GameDev Story?

#### Archived

This topic is now archived and is closed to further replies.

# need C++ help with recursion

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

## Recommended Posts

i need to write a program that is able to find the biggest number in a list of numbers. I already wrote the program without using recursion, but i need to use recursion to do that problem. heres what i have so far. any help, like an example or some sample code would help me out alot. or even some ideas, thanks. //*********************** Preprocessor Directives ********************* #include <iostream.h> #include <iomanip.h> //********************************************************************* const int MAX = 50; typedef int LIST_I[MAX]; //********************************************************************* void main() { LIST_I num; int ct, tot, max, wait; cout << "Enter the total amount of numbers in the list (max = 50): " ; cin >> tot; for (ct = 0; ct < tot; ++ct) { cout << "Enter a number: " ; cin >> num[ct]; } max = num[0]; for (ct = 1; ct < tot; ++ct) { if (num[ct] > max) max = num[ct]; } cout << "The largest number in the list is " << max << endl;

##### Share on other sites
Recursion means you have a function that calls itself until some end condition.

So create a FindMax function that takes the index to start at. That FindMax function should call FindMax again with a different index, and compare the result to figure out the max. There should be some sort of end condition based on the input that will cause FindMax to return without calling FindMax again.

I could tell you more, but then I''d just be doing your homework for you.

##### Share on other sites
Look here

One way would be with a simple divide and conquer method: Write a function that returns the max number in a list, this finds the max number by spliting it into two and calling itself etc. until it gets a length of one, and returns that. Neat, simple and reasonably elegent. I''ll let you figure out the details on your own..

##### Share on other sites
You can just use tail-end recursion to replicate your loop, or you could use an algorithm that is naturally recursive. If I were you, I''d try both as a learning experience.

Tail end recursion means changing this:

  for(int i = 0; i < 10; i++){    cout << i << endl;}

...into this:

  void foo(int x){   cout << x;   if(x < 10)       foo(x+1);}

Tail end recursion isn''t as efficient as a loop, but it helps to demonstrate one way to use recursion. More efficient uses of recursion are harder to replicate in a loop.

I''ll give you one idea off the top of my head for a recursive algorithm to find the largest element in an array. The function works like this:

- If the array only has one element, it returns that value. After all, if a list contains only one number, isn''t that one number the biggest one in the list?
- If the array is larger than one element, it splits the array in half and calls itself on each half. It returns the larger of these two numbers.

Let''s step through it. You have this array: 10, 5, 7, 2, 12, 5, 9, 1. First I''ll diagram what happens as a tree.

What the function gets:         10, 5, 7, 2, 12, 5, 9, 1            /                   \    10, 5, 7, 2               12, 5, 9, 1     /        \                 /        \  10, 5      7, 2           12, 5       9, 1   /  \      /  \            /  \       /  \  10  5      7  2           12   5     9    1What the function returns:                               12                         ______/\_____                        /             \                      10              12                     /   \           /  \                   10     7        12    9                   / \   / \       / \  / \                  10 5  7  2      12 5  9 1

I hope that helps. Basically, when designing a recursive algorithm, you break a problem down into smaller parts. It''s called the "divide and conquer" strategy.

What I just gave you probably isn''t the only way to recursively determine the largest element in an array. But it''s one way, and, hopefully, it''s easy to understand. I hope this helped.

##### Share on other sites
Damn, OrangyTang, you beat me to it!

##### Share on other sites
all you have to do is imagine you had a function already that worked.

for example you might imagine you have a function and you pass it an array and tell it how long the array is and it will return the maximum number in the array.

now imagine you're coding a similar function but for an array that is one bigger. the easiest way to do it would be to look at the end number in the array, pass the rest of the array to the function that works with an array one smaller and then just compare the result with the end number.

return the biggest one of the two.

what you find is the two functions are the same. you implement one in terms of a similar but smaller request.

that's the magic of recursion.

so roughly (ie I haven't checked this)

edit: not doing homework for you

also use standard headers <iostream> instead of non standard, very old, out of date by at least eight years, iostream.h etc.

[edited by - petewood on December 2, 2002 5:04:54 PM]

##### Share on other sites
eh, im lost on this. heres my sad attemt at recursion, it won''t even compile cause i got 4 errors that i can''t get rid of. I know this is pretty simple for u guys and this is due tommorow for me. I really did give a good attempt about 2 hrs yesteday and today and I just can''t grasp it. I can understand and can walkthough the similer ones like the one TerranFury posted, but i just cant'' get this one. I was wondering if someone could help me out some more. maybe on ICQ or IM, 34710948 and Omicron005. Im willing to pay, \$25 through paypal, if someone can tutor me though it. I really want to understand how to do this.

//*********************************************************************
const int MAX = 50;

typedef int LIST_I[MAX];

//*********************************************************************
void get_max(int& tot, LIST_I num);

//*********************************************************************
void main()
{
LIST_I num;

int ct,
tot,
max = 0,
wait;

cout << "Enter the total amount of numbers in the list (max = 50): " ;
cin >> tot;

for (ct = 0; ct < tot; ++ct) {
cout << "Enter a number: " ;
cin >> num[ct]; }

max = get_max(tot, num);

cout << "The largest number in the list is " << max << endl;

cout << "WAIT";
cin >> wait;
}

//*********************************************************************
void get_max(int& tot, LIST_I num)
{
if (tot==1)
return num[tot];
else
if (num[tot] < get_max(tot-1, num) )
return num[tot];
}

##### Share on other sites
Finding the largest number is pretty straight forward:

1. Store last item as Big Value
2. Compare Big Value to all values in list
a. when an list item is bigger then Big Value store that value into Big Value

Need to know

Number of Items in List
Big Value (initialize with last item in list)

            // This Big Value finder does not assume the list is sorted in any order// Warning: This will only work on small lists 15(this is just my guess more then likely you can use it on larger lists) or less items//  anymore than that you might blow the stackint BigValue(int BigValue, int *list, int items){ // One less item to check   items--; // Enable the if statement if you what to ensure the stack doesn't bust // Depth checker: Don't process this list if it has over 15 items//   if(items>14) return(BigValue); //  Once items is less than 0 you have checked all items in the list   if(items<0) return(BigValue); // Test if this item is larger the Big Value   if(list[items]>BigValue) BigValue = list[items];   // Check another item   return(BigValue(BigValue, list, items));}// This is how to use it in your codemax = BigValue(num[tot-1],num,tot);

I believe this is what you need.
I hope someone else can explain it or correct it if its wrong.

Good Luck!

Sorry, forgot to return the BigValue.

[edited by - CodeJunkie on December 3, 2002 6:11:39 PM]

Oops didn't need to use a pointer for BigValue. Now that would cause interesting side effects.

[edited by - CodeJunkie on December 3, 2002 9:15:33 PM]

Finally, made a working version! (had a problem with returning the value correctly) How is your's coming Omicron?

[edited by - CodeJunkie on December 3, 2002 9:56:09 PM]

There you go that should do the job. btw haven't got a clue how large a list you could use this on.

[edited by - CodeJunkie on December 3, 2002 10:44:38 PM]

##### Share on other sites
On a side note, you should be including iostream & iomanip and not iostream.h & iomanip.h, as they are deprecated.

[edited by - Synapse on December 3, 2002 9:40:33 PM]

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 10
• 11
• 13
• 9
• 11
• ### Forum Statistics

• Total Topics
634087
• Total Posts
3015444
×