How can i do this function using recursion ?

[Rooro]

For the List class, add a Boolean-valued function that determines whether the data items in the linked list are arranged in ascending order.

How can i do this using recursion

[sicarie]

For the List class, add a Boolean-valued function that determines whether the data items in the linked list are arranged in ascending order.

How can i do this using recursion

Call the same method inside the method until you finish the ordering.

What do you have so far?

[sicarie]

Here's a bit more on recursion:

http://personal.vsnl.com/erwin/recursion.htm

[Rooro]

Thanks sicarie for your reply and also for the link ....



for example if i have this :



bool list::isOrdered () const

{

Node *ptr = first ; Node *following;

bool isOrdered = true;

if(mysize >=2 )

{

following = ptr->next;

while (following !=Null && isOrdered)

{isOrdered=(ptr->data->following->data);

ptr=following;

following = following->next;}

}
return isOrdered;

}



how can i do it with recursion ?

it is little confusing for me :(

[sicarie]

Yeah, recursion is one of the trickier subjects to understand.

I'm going to warn you right now, I've only written two or three programs that used very light recursion, so if someone else wants to jump in here if they feel they have a better handle, they're more than welcome. And with the apology that I'm probably going to stumble through it a little bit as this is the one concept I have yet to try to explain to someone, I'll outline how I would go about it.

These three things are needed for recursion.
1. A simple base case which we have a solution for and a return value.
Ordered list. With recursion, the isOrdered() method base case is going to be either the tail or last element, or even possibly the head or beginning - if it goes all the wya through first, and then orders on it's way back out, and returns ... the first value?

2. A way of getting our problem closer to the base case. I.e. a way to chop out part of the problem to get a somewhat simpler problem.
We're ordering by 'mysize' so (if it is ascending order), I would start at the beginning, take a value, and test it agains the next. If it is larger than the next, swap the two.

3. A recursive call which passes the simpler problem back into the function.
I think it would be easiest to keep track of a large value, whichever is the largest, so pass the location of the larger of the two back to the function.

So we're going to take a list.
Get the first element
Check it against the next
if it is bigger
swap and pass the pointer to the first (now the second) to isOrdered again
else,
send the second to isOrdered

Somehow I think that algorithm is deficient, it can put a node at the end, but I'm not sure it will get the rest. What do you think?

[Rooro]

Yeah, recursion is one of the trickier subjects to understand.

I'm going to warn you right now, I've only written two or three programs that used very light recursion, so if someone else wants to jump in here if they feel they have a better handle, they're more than welcome. And with the apology that I'm probably going to stumble through it a little bit as this is the one concept I have yet to try to explain to someone, I'll outline how I would go about it.

These three things are needed for recursion.
1. A simple base case which we have a solution for and a return value.
Ordered list. With recursion, the isOrdered() method base case is going to be either the tail or last element, or even possibly the head or beginning - if it goes all the wya through first, and then orders on it's way back out, and returns ... the first value?

2. A way of getting our problem closer to the base case. I.e. a way to chop out part of the problem to get a somewhat simpler problem.
We're ordering by 'mysize' so (if it is ascending order), I would start at the beginning, take a value, and test it agains the next. If it is larger than the next, swap the two.

3. A recursive call which passes the simpler problem back into the function.
I think it would be easiest to keep track of a large value, whichever is the largest, so pass the location of the larger of the two back to the function.

So we're going to take a list.
Get the first element
Check it against the next
if it is bigger
swap and pass the pointer to the first (now the second) to isOrdered again
else,
send the second to isOrdered

Somehow I think that algorithm is deficient, it can put a node at the end, but I'm not sure it will get the rest. What do you think?

sicarie I will try ..and tell you what I will have : )


Thanks a lot ...