PLEASE HELP ME IN Recursion

[cute cat]

can you help me!!

I have assignment that told me to write a function 'CheckSmaller' that takes two linked list as input arguments. These linked list contain numbers like this:

num1->3->5->2->NULL (assuming that num1 is pointing to number 352)
num2->4->3->9->1->NULL (assuming that num2 is pointing to number 4391)

The function CheckSmaller should return 1 if num1 points to a linked list which represents a smaller number than the number pointed to by num2 linked list. Otherwise, it returns -1. If both linked list point to exactly the same number, CheckSmaller returns a 0.

int CheckSmaller(Node* num1, Node* num2);

Notice that if two linked lists are:

num1->8->4->2->NULL (assuming that number 1 is 842) and
num2->8->4->3->NULL (assuming that number 2 is 843)
then your function should return 1 since 842 is smaller than 843.

and I want to use Recursion for this function

THANK YOU

[Narue]

I wouldn't recommend recursion for this problem, but you also didn't ask a question. You just posted your requirements, which strongly suggests that by "help" you really mean "do it for me". :icon_rolleyes:

[cute cat]

you are right somehow but I didn't mean do it for me if you can just tell the steps
that I have to do it in the recursion that it is fine
whoever thank you for reply and the one who told me to use recursion in this case is my doctor

[Narue]

if you can just tell the steps

How is that different from "do it for me"? Why don't you try solving the problem yourself first, then post your code to prove you've made an honest attempt.

[cute cat]

ok I will be honest and I will tell you why I am doing that. The reason is I don't know the recursion well actually I understand the link list but for the recursion I just memorize the functions that the doctor gave us in the note so that when he gave us an assignment which involves a new idea ...here I thought If there is anybody in this website could learn me how to do it...
anyway you are completely right but please don't say that I didn't try do it by myself this topic is very difficult and I tried many times on my papers to get the answer....
nonetheless thank you again for your reply and I promise you that I will not write any thread again
bye

[Narue]

The reason is I don't know the recursion well

If you came in here asking pointed questions to aid your understanding of recursion, you'd probably receive a lot of help. But by asking for the solution to your problem with no proof of effort on your part, you deserved exactly what you got.

I promise you that I will not write any thread again

How childish. If you want to run away with your tail between your legs because someone called you on your attempt at cheating on an assignment, guess what? Nobody cares and you won't be missed. You can still turn around and do things the right way and I'll help. Or you can be a whiny baby. Your choice.

[prvnkmr194]

I am not give you code but I would like to give you some hints for coding .......
As I understand your problem, you have 2 link list of integer type which store single digit as one node right ..then
Your First step is to store these node into single variable ....for example..
num1->4->8->2->NULL as n1=482
then compare both value by using. But it have limitation, if your digit cross the limitation of datatype then will not work .........
If you have large number of node then free to ask for help.......

[cute cat]

If you came in here asking pointed questions to aid your understanding of recursion, you'd probably receive a lot of help. But by asking for the solution to your problem with no proof of effort on your part, you deserved exactly what you got.

I got it ...

How childish. If you want to run away with your tail between your legs because someone called you on your attempt at cheating on an assignment, guess what? Nobody cares and you won't be missed. You can still turn around and do things the right way and I'll help. Or you can be a whiny baby. Your choice.

I didn't act like a child so please don't say whatever you want and I am here to show you my attempts but I know already it isn't right or there is mistake somewhere whoever this is the a prove that I did it on myself so retreat from your words ....

[Narue]

I am here to show you my attempts

Then please do so.

[cute cat]

thank you very much prvnkmr194 I did my best so I would like to see what I wrote...

#inculde<iostream>
using namespace std;
class Node
{
public:
int value;
Node*next;
Node();
Node(int v);
};
Node::Node()
{
value=0;
next=NULL;
}
Node::Node(int v)
{
value=v;
next=NULL;
}
int Length(Node*h)//this is the function to count the length
{
if(!h)
return0;
return 1+length(h->next);
}
bool compare(Node*h1,Node*h2)
{
if(length(h1)==length(h2))
return 0;
else
if(length(h1)>length(2))
return 1;
}

and here I stop it...mmmm I know I miss many things
also I didn't complete my program until the end but this is what I understand from this assignment

THANK YOU..

[Narue]

The base case is really the hardest part of this, because you need to consider three different situations:

1. Both numbers are the same length, thus num1 and num2 are null.
2. num1 is shorter than num2, which makes num1 null and num2 not null.
3. num2 is shorter than num1, the reverse of situation #2.

In situation #1, the numbers compare as equal, but it's a temporary state because you're at the end of the list. Rolling back up the recursion chain could produce a difference on one of the digits further to the left. In situation #2, you have a true base case and can simply return +1 all the way back up. Likewise with situation #3, except the return value is -1.

If the return value is 0, just make a comparison of the current digits and return it. It's very important to remember that recursion is a wave you have no choice but to ride. All the way down, then all the way back up. For example, traversing a list looks like this:

#include <iostream>
#include <iomanip>

struct Node {
    int digit;
    Node *next;

    Node(int digit, Node *next)
        : digit(digit), next(next)
    {}
};

Node *generate_number(const char *s)
{
    Node *head = 0;
    Node *tail = 0;

    while (*s != '\0') {
        Node *node = new Node(*s++ - '0', 0);

        if (head == 0)
            head = tail = node;
        else
            tail = tail->next = node;
    }

    return head;
}

std::ostream& operator<<(std::ostream& out, Node *head)
{
    while (head != 0) {
        out<< head->digit;
        head = head->next;
    }

    return out;
}

void traverse(Node *node, int level)
{
    char digit = node != 0 ? node->digit + '0' : '~';

    // Going down to the base case
    std::cout<< std::setw(level * 4) << digit <<'\n';
    
    if (node != 0)
        traverse(node->next, level + 1);

    // Back up to the original call
    std::cout<< std::setw(level * 4) << digit <<'\n';
}

int main()
{
    traverse(generate_number("12345"), 0);
}

[cute cat]

First of all thank you Narue for your aid I thought you just make fun of me but you are actually not so that I am sorry if I wrote something bad to you...
and may I ask you part part
you said that there are 3 cases right
1)return null if they both have the same lenght
2)return 1 if num1 is shorter than num2
3)return any value except -1((that what do you mean..?))

and is struct different from class because we just took class

could you please explain why you did that here

#
Node *generate_number(const char *s)
#
{
#
Node *head = 0;
#
Node *tail = 0;
#

#
while (*s != '\0') {
#
Node *node = new Node(*s++ - '0', 0);
#

#
if (head == 0)
#
head = tail = node;
#
else
#
tail = tail->next = node;
#
}
#

#
return head;
#
}

and for this function

#
std::ostream& operator<<(std::ostream& out, Node *head)
#
{
#
while (head != 0) {
#
out<< head->digit;
#
head = head->next;
#
}
#

#
return out;
#
}
#

can we write it like this

void print(Node*h)
{
if(!h)
return;
print(h->next);
cout<<h->digit;
}

mmm and for the last function I didn't really get it..sorry
in the end thank you to spend a lot of time to write this code ..(^_^)

[Narue]

you said that there are 3 cases right
1)return null if they both have the same lenght
2)return 1 if num1 is shorter than num2
3)return any value except -1((that what do you mean..?))

Here are the three cases with examples:

1. 123 and 456 have the same length, so you use the first mismatch (3 and 6). 123 and 123 have the same length but no mismatch, so 0 would be returned all the way back up the recursion chain. A more interesting example is 123 and 523. 3 and 2 match, which is why you need to do comparisons back up the chain.
2. 352 is shorter than 4391, so you don't need to do any comparisons. The result is guaranteed to be 1.
3. 1234 is longer than 543, so you don't need to do any comparisons. The result is guaranteed to be -1.

and is struct different from class because we just took class

The only difference is default accessibility. classes are private by default, and structs are public. The following is an equivalent class:

class Node {
public:
    int digit;
    Node *next;
 
    Node(int digit, Node *next)
        : digit(digit), next(next)
    {}
};

could you please explain why you did that here

It's easier to build numbers quickly with a list generating function.

can we write it like this

You can, but it's not equivalent. With your function the list is printed in reverse. You can flip it like so:

void print(Node*h)
{
    if(!h)
        return;

    std::cout<<h->digit;
    print(h->next);
}

mmm and for the last function I didn't really get it..sorry

It only illustrative for the in and out nature of recursion. For each recursive function call, there's a corresponding rollback. So you end up visiting each instance of the function call twice.

in the end thank you to spend a lot of time to write this code ..(^_^)

No biggie, it only took up a spare five minutes. I also wrote your CheckSmaller function, but removed it for the post because I won't do all of your work for you.

[Celtrix]

@cute cat we don't mean to be mean we simply ask that you show us your best we' re not going to make fun or be rude we just want to see what you have so far and we will point you in the right direction. It's just that as a by product of years gone by that a few bad apples tried to get free code and pass it off as there own as if they wrote the whole thing I believe your intentions are pure and I would help if I could but I don't know jack about linked list as every attempt on my part to understand the concepts and pitfalls is just a complete failure. I can however try to help with recursion just give me a little bit I'm typing this on my iPod. Ignore that last bit if narue helped you I'm sure you can work it out however if you need further assistance just ask me

[cute cat]

thank you very much Narue for your explain
Here are the three cases with examples:

1. 123 and 456 have the same length, so you use the first mismatch (3 and 6). 123 and 123 have the same length but no mismatch, so 0 would be returned all the way back up the recursion chain. A more interesting example is 123 and 523. 3 and 2 match, which is why you need to do comparisons back up the chain.
2. 352 is shorter than 4391, so you don't need to do any comparisons. The result is guaranteed to be 1.
3. 1234 is longer than 543, so you don't need to do any comparisons. The result is guaranteed to be -1.

I wrote CheckSmaller function from what you explained

int CheckSmaller(Node*num1,Node*num2)
{
while(num1&&num2)
{
if(num1->value==num2->value)
num1=num1->next;
num2=num2->next;
return 0;
}
else
if(num->value<num2->value)
return 1;
else
return -1;
}

It is right it is right ....right?(^____^)

No biggie, it only took up a spare five minutes. I also wrote your CheckSmaller function, but removed it for the post because I won't do all of your work for you.

Oh really ...but anyway you spent those five minutes to explain to me so I am really grateful for what you did

thank you Celtrix for your comment

@cute cat we don't mean to be mean we simply ask that you show us your best we' re not going to make fun or be rude we just want to see what you have so far and we will point you in the right direction.

I feel shy from what you wrote and I actually was wrong in the first place so I am sorry about that

It's just that as a by product of years gone by that a few bad apples tried to get free code and pass it off as there own as if they wrote the whole thing

Is that so...?

I believe your intentions are pure and I would help if I could but I don't know jack about linked list as every attempt on my part to understand the concepts and pitfalls is just a complete failure. I can however try to help with recursion just give me a little bit I'm typing this on my iPod. Ignore that last bit if narue helped you I'm sure you can work it out however if you need further assistance just ask me

oh thank you very much Celtrix =^-^= you are really kind person but if I have a question I will try to solve it as much as I can then after that if I couldn't solve it I will post my question which contents my attempts
thank you again for all things^_^have a nice day
bye

[Narue]

It is right it is right ....right?(^____^)

It's not recursive, so I'd lean toward not right. ;)

[cute cat]

It's not recursive, so I'd lean toward not right.

so it will not called recursive if I used loop right?
it is really difficult but I wrote another function for CheckSmaller I would like to see it if you don't mind

int CheckSmaller(Node*num1,Node*num2)
{
if(num1->value<num2->value)
return 1;
else
return -1;
CheckSmaller(num1->value==num2->value)//I used the same name of the function in order to go to another node if they are equal and after see all values are same it will return 0
return 0;
}

is it right...?!

[arkoenig]

The recursive call to CheckSmaller (with the comment) will never be executed because either path of the if statement before it will return first. So I don't even need to read the rest of the code to see that it's wrong.

[Celtrix]

@cute cat if you return a value in a function recursion wont work because you have exited the function and as such it will continue with the next statement try storing the value in a variable

int CheckSmaller(Node*num1,Node*num2,int ret)
{
while(num1&&num2)
{
if(num1->value==num2->value)
num1=num1->next;
num2=num2->next;
ret=0;
}
else
if(num->value<num2->value)
EDIT:that was a no go I even tried to do a class based version unless I messed up somewhere I'll get back to you in a sec
ret=1;
else
ret=-1;

Then just pass a variable to it to retrieve the value
is
int x;
CheckSmaller(mynode1,mynode2,x);

That should work I haven't tested it my wifi on my pc is on the fritz so I have to use my iPod.

[cute cat]

I didn't really get it what you are trying to tell...I am sorry but could please see my another function because as Narue the first one is wrong...

[arkoenig]

Here are the three cases with examples:

1. 123 and 456 have the same length, so you use the first mismatch (3 and 6). 123 and 123 have the same length but no mismatch, so 0 would be returned all the way back up the recursion chain. A more interesting example is 123 and 523. 3 and 2 match, which is why you need to do comparisons back up the chain.
2. 352 is shorter than 4391, so you don't need to do any comparisons. The result is guaranteed to be 1.
3. 1234 is longer than 543, so you don't need to do any comparisons. The result is guaranteed to be -1.

I think this case analysis fails to take into account the case where the two lists have different lengths, but one or both of them has a leading zero.

For example, 352 is shorter than 0321, but it's bigger anyway.

[Narue]

I think this case analysis fails to take into account the case where the two lists have different lengths, but one or both of them has a leading zero.

That was intentional. Handling leading zeros would only complicate an algorithm that the OP is already totally overwhelmed in trying to create.

[Red Goose]

Here, I'll give you the logic, and I'll leave it to you to write the program:

For each digit, you need to check if one is bigger than the other, if it is, set a variable to define that string as the bigger one. This variable should only be assessable once, after which, it should no longer check for which one is bigger. This will allow you to check for the largest digit. For example : 19, 23. 23 Would be considered the bigger one, since the first digit accessed is larger on 23 than on 19. The "3" and "9" are ignored.

Next, check if both sets are on null. If they are, check if one is bigger than the other, using the previous variable, if neither is, then return 0. This works because both numbers hitting null at the same time means they're the same length, and if no digits were larger in any case, then they both must be the same number. For example: 198, 198. The previous variable would not return anything for any digit, since they're all equal. Once you reached null, it would be clear that there is no difference. Another example: 198, 197. 198 would be considered bigger since the last digits, "8", and "7", are not equal, and 8 is larger than 7.

Finally, check to see if either set reached null. If one does reach null, the other set must be the larger one. Example: 20, 197. 20 would reach null earlier, and thus, 197 must be the larger number.

Remember that you need to do this with recursion. If you don't know what that is, I suggest you check your text for an explanation. I will not do the programming for you.