8 Replies - 4830 Views - Last Post: 31 December 2010 - 02:53 AM Rate Topic: -----

#1 FoxDie   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 30-December 10

Compare 2 linked lists using Reverse Recursion

Posted 30 December 2010 - 08:10 AM

I'm a beginer in using Recursion, and I need some tips. I'm using C++ for my program.
My program ask for two numbers, then see with one is bigger.

In details:
My program will ask the user to enter two numbers of any size, then I will take each digit of the first and second number, and insert it in one node of a linked list. It will appear like this:
first number = 123456789
second number = 567891234

head1->9->8->7->6->5->4->3->2->1
head2->4->3->2->1->9->8->7->6->5

Then, I will compare the two numbers, and should return 0 if head1 > head2, return 0 if head1 < head2, and return nothing if they are equal.

Don't ask me to revirse the order of entering each digit into the linked list. I just need it that way for another pourpse.

Anyway at first, I made a code to compare the 2 linked lists using Recursion normally, and here it:
bool ChckWhoNum(Node*he1,Node*he2)
{
	bool res;
	if ((!he1) || (!he2))
		res=0;

	else
	{
		if(he2->value>he1->value)
			res=1;
		else if (he2->value<he1->value)
			res=0;
		else if(he2->value==he1->value)
			ChckWhoNum(he1->next,he2->next);
	}
	return res;
}

In my case, i need to do it in revise order. Instead of checking the linked list from the start(left) to end(right). I wanna make from the end"left" to the start"right".
I've tried a couple of time, but I always end up having a problem with the stoping condition..

I believe that I should have 2 stoping condition to make it work in my humble opinion. And currently I can't figure out the second condition. Here is my code:
bool ChckWhoNum(Node*he1,Node*he2)
{
	bool res;
	if ((!he1) || (!he2))
		res=0;

	ChckWhoNum(he1->next,he2->next);

	if(he2->value>he1->value)
		{
			cout<<"head2 > head1\n";
			res=1;
		}
	else if (he2->value<he1->value)
		{
			cout<<"head1 > head2\n";
			res=0;
		}
}


I hope you got my point, and this could be possible.


Waiting for your response....

Is This A Good Question/Topic? 0
  • +

Replies To: Compare 2 linked lists using Reverse Recursion

#2 -shadow-   User is offline

  • D.I.C Head
  • member icon

Reputation: 17
  • View blog
  • Posts: 204
  • Joined: 18-November 10

Re: Compare 2 linked lists using Reverse Recursion

Posted 30 December 2010 - 10:29 AM

use head1 == head2 as your base case

say head1 = 1, 5, 2, 2, 8, 3
and head2 = 1, 5, 2, 2, 8, 4

compare them backwards
3 < 4 so set a variable to keep track that head2 is greater than head1
8 = 8 so skip it
2 = 2
2 = 2
5 = 5
1 = 1
now we've reached the beginning and head2 is greater than head1

now look at another example

head1 = 2, 4, 3, 8, 5, 0
head2 = 1, 2, 4, 8, 5, 1

0 < 1 so head 2 is greater than head1
5 = 5 so do nothing
8 = 8
3 < 4 so head 2 is still greater
4 > 2 so now head 1 is greater
2 > 1 so head 1 is still greater

end result is that head1 is the greater number.

Hope this helps
~Wes
Was This Post Helpful? 1
  • +
  • -

#3 Slumdog   User is offline

  • D.I.C Head

Reputation: 34
  • View blog
  • Posts: 116
  • Joined: 26-November 10

Re: Compare 2 linked lists using Reverse Recursion

Posted 30 December 2010 - 12:51 PM

http://myjntunotes.b...nked-lists.html
Was This Post Helpful? 0
  • +
  • -

#4 FoxDie   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 30-December 10

Re: Compare 2 linked lists using Reverse Recursion

Posted 30 December 2010 - 02:41 PM

Hello -shadow-
I really appreciated your input, but I think you are not getting the whole picture or I didn't understand.

I purposely had put the numbers in reverse order into the linked list.
For example:
Num1=44543
Num2=45333

Here: Num2>Num1...

In the linked list I inserted the numbers in reverse order for some reasons.
Head1= 3,4,5,4,4
Head2= 3,3,3,5,4

Now, typically I should start comparing from the end 'right' to the last 'left'.

In this case:
4=4 nothing
4<5 return true
Here I should stop, but I doubt there is anyway to break the Recursion. But, there might be a way if I put a stoping condition that keep returning the same value I need with continue comparing.


Hello Slumdog
Thanks for the link, but I already did my part in that if you read carefully.
Was This Post Helpful? 0
  • +
  • -

#5 mojo666   User is offline

  • D.I.C Addict
  • member icon

Reputation: 409
  • View blog
  • Posts: 883
  • Joined: 27-June 09

Re: Compare 2 linked lists using Reverse Recursion

Posted 30 December 2010 - 03:04 PM

Quote

and return nothing if they are equal.

This is not possible. Your function must always return 0 or 1 since it is boolean. I think to accomplish what you need, you need to change your function to accomadate all 3 possibilities, which means it should probably not be bool.

Quote

In this case:
4=4 nothing
4<5 return true
Here I should stop, but I doubt there is anyway to break the Recursion. But, there might be a way if I put a stoping condition that keep returning the same value I need with continue comparing.


Since you are reading left to right, you cannot stop at 4<5 because you do not yet know that the first digits are equal. You need to recurse and store that result, then return your value accordingly.
bool ChckWhoNum(Node*he1,Node*he2)  
{  if(/*Terminating Conditions*/)
   {/*do stuff*/}
   else
   {
       bool Res=ChckWhoNum(he1->next,he2->next); //Res now represents the results of comparing higher digits
       if(/*Res indicates equal values*/)
       {
           if(he1>he2){return 1;}
           if(he1<he2){return 0;}
           if(he1==he2){return /*some value indicating that he1 = he2;}
       }
       else{return Res;}
   }
}


This post has been edited by mojo666: 30 December 2010 - 03:05 PM

Was This Post Helpful? 1
  • +
  • -

#6 FoxDie   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 30-December 10

Re: Compare 2 linked lists using Reverse Recursion

Posted 30 December 2010 - 03:47 PM

That's really true, but I just thought it might be happen. Anyway, I would return 0 if they are equal. My most concern is if head1<head2. But giving another thought, I might try and let it return 'int' instead.

Regarding the recurse action, you're right too. It will keep going, but as I said before, I need a condition to keep it storing the right result. Because if it keeps going, the result will be changed. I guess you understand what I mean.

For now, I'll try using the 'int' return. See what I can do about that.

Really thank you so much for your input.
Was This Post Helpful? 0
  • +
  • -

#7 FoxDie   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 30-December 10

Re: Compare 2 linked lists using Reverse Recursion

Posted 30 December 2010 - 04:50 PM

Wow :sadlike: you are really brilliant. Thank you so much.
I nearly gave up, but you saved me.
I can't thank you enough.

I changed your code to adapt the 'int' return, and pingo.....
Here it is, check it out if there is anything can be better. Overall it works perfectly, thanks to you for sure...

int ChckWhoNum(Node*he1,Node*he2)
{
	if(!he1)
		return 3;

	else
	{
		int Res=ChckWhoNum(he1->next,he2->next);

		if(Res==3)
		{
			if(he1->value>he2->value)
				return Res=0;

			else if(he1->value<he2->value)
				return Res=1;

			else if(he1->value==he2->value)
				return Res=3;
		}

		else
			return Res;
   }
	if(ChckWhoNum(he1,he2)==3)
		return 0;
}

Was This Post Helpful? 0
  • +
  • -

#8 mojo666   User is offline

  • D.I.C Addict
  • member icon

Reputation: 409
  • View blog
  • Posts: 883
  • Joined: 27-June 09

Re: Compare 2 linked lists using Reverse Recursion

Posted 30 December 2010 - 09:24 PM

No problem. The only major issue I see is with your terminating condition. It's fine if you can guarantee that the lists are always of equal size, but it might be better to account for different sized lists. Also, it's pretty standard to make compare functions return -1 when the first object is less than the second, 0 when they are equal, and 1 when the first object is greater than the second. This has the advantage of having some interesting mathematical shortcuts when using the function repeatedly, but for now there is no problem in keeping your 0,1,3 return values.

int ChckWhoNum(Node*he1,Node*he2)
{
    if(!he1&&!he2)//then he1 and he2 are the same length so they may be equal
        return 3;
    else if(!he1) //then we know he1<he2 since he2 is longer
        return 1;
    else if(!he2) //then we know he1>he2 since he1 is longer
        return 0;
    else
    {
        int Res=ChckWhoNum(he1->next,he2->next);
 
        if(Res==3)
        {
            if(he1->value>he2->value)
                return Res=0; 
            else if(he1->value<he2->value)
                return Res=1; 
            else if(he1->value==he2->value)
                return Res=3;
        } 
        else
            return Res;
   }
/*nothing past this line will ever get executed as the function returns in all possible conditions
    if(ChckWhoNum(he1,he2)==3)
        return 0;
You can delete this comment*/
}


Was This Post Helpful? 0
  • +
  • -

#9 FoxDie   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 30-December 10

Re: Compare 2 linked lists using Reverse Recursion

Posted 31 December 2010 - 02:53 AM

Aha good to know some standards. Thank you…
Well regarding the size, don't worry about that, cuz I have already made another function to check the size before it comes to this level. If the size are matching, then I'll come here and check the whole number. Otherwise, I will already know which one is bigger from the length of number.

Mmmmm, but you are really made an interesting and easier way to check in this size.
It never occured to me cuz I already made that function, but it absolute good to know.

Again and again, I really appreciated what did, and thank you so much.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1