I was coding the Linklist by using recursion function to find the maximum number in the LinkList. In the recursion function I was wondering why to use max = Rmax(p->next); to do the recursion instead of return Rmax(p->next).

The most confusing part is if we assign max to return value of recursion function what will the int type data max equal?

The confusing step was signed by ❓❓❓ in the code，please help me in understanding this.

Here are the code:

struct node
{
    int data;
    struct node*next;
}*first=NULL;

void Creat(int n)
{
    first = (struct node*)malloc(sizeof(struct node));
    first->data=0;
    first->next=NULL;
    struct node*temp_node,*control_p;
    control_p=first;
    
    for(int i = 1;i<n;i  )
    {
        temp_node = (struct node*)malloc(sizeof(struct node));
        
        control_p->next=temp_node;
        
        temp_node->data = i; 
        temp_node->next=NULL;
        
        control_p=temp_node;
    }
}

int recursionMaxLLN(struct node *p)
{
    
    int max = 0;
    
    if(p==NULL)
    {
        return -1;
    }
    else
    {
        max = recursionMaxLLN(p->next);//❓❓❓❓
        if(p->data>max)
                return p->data;
        else
            return max;
    }
}

int main()
{
    Creat(10); 
    printf("%d",recursionMaxLLN(first));
}

CodePudding user response：

See, we cannot directly return Rmax(p->next) since we need the comparison if(p->data>max) for finding maximum value. As far as the data type is concerned max is int and function return type is also an int, so we are using recursion to store data in max.

max will definitely contain the data of the node having a p pointer at that time. We are recursively traversing over the linked list and using basic comparison to find the maximum value.

CodePudding user response：

Taking the second question first ...

The most confusing part is if we assign max to return value of recursion function what will the int type data max equal?

When implementing a recursive function, one has to use the a priori assumption that a recursive call to that function does what it's supposed to do.

In this case, that means that the implementation of Rmax() assumes that Rmax(p->next) returns the maximum value of the nodes in the sublist headed by p->next. With use of that assumption, it ensures that it itself returns the the maximum value of the sublist headed by p. Doing that correctly ensures in turn that the assumption was valid.

I was wondering why to use max = Rmax(p->next); to do the recursion instead of return Rmax(p->next).

We assume that Rmax(p->next) returns the maximum value in the sublist headed by p->next. Sometimes that will be the maximum value of the list headed by p, but for some lists, the maximum value will instead be p->data. You cannot unconditionally return Rmax(p->data) because sometimes that's the wrong answer.

It is a bit misleading, then, to store that result in a variable named max, because it might not be the maximum of the list headed by p. You might be less confused if you renamed that variable to tail_max or max_of_tail_list or simply temp. Whatever you name the variable, you need it to hold on to the result of the recursive call so that you can determine whether to return that or p->data as the maximum of the whole list.