• Advertisement

Archived

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

need C++ help with recursion

This topic is 5556 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 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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 1


What 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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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

List Address
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 stack


int 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 code

max = 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!

[edit]
Sorry, forgot to return the BigValue.

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

[edit]
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]

[edit]
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]

[edit]
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 this post


Link to post
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]

Share this post


Link to post
Share on other sites
well i finally got it working. i first tried using the example that codejunkie posted, although i used an array instead of pointers, cause im not too good with pointers either. but i was getting crazy answers for the max, like 69392734. even though my numbers were like 5,7,9,3,4. but i also posted at another programming forum and someone was able to help me out. i posted both codes below. also thanx for all the help, it was very usefull.

heres the code that wasn't working


int get_max(int bigv, int tot, LIST_I num)
{
if (tot <0 )
return bigv;
if (num[tot]> bigv)
bigv = num[tot];
get_max(bigv, tot-1, num);
return bigv;

}


and heres the code that i ended up using


int get_min(int tot, LIST_I num)
{
if (tot==1)
return num[0];
else
{
int left = get_min(tot/2, num);
int right = get_min(tot-(tot/2), num+(tot/2) );
if(left < right)
return left;
else
return right;
}
}



[edited by - Omicron on December 4, 2002 1:18:56 AM]

Share this post


Link to post
Share on other sites
Yeah, i figured it out what was wrong before you posted.

int get_max(int bigv, int tot, LIST_I num)
{
//if (tot <0 ) return bigv; *forget the deincrement*
if (--tot <0 ) return bigv;
if (num[tot]> bigv) bigv = num[tot];
return(get_max(bigv, tot, num)); // this what i didn't do right in the first place
}

Thanks!

[edit]
Should have read the code all the way after pasting it. Forgot to deincremet tot. Man!!!

[edited by - CodeJunkie on December 4, 2002 3:08:56 AM]

Share this post


Link to post
Share on other sites

  • Advertisement