Find the max of a list using recursion

Question

Hi i needed to find the max int of a list using recursion, I have done it this way I'd like to know if you think is a good way, and I have a couple of questions:

int trovaMassimo(node_t *head){

    int e;
    if(head == NULL){//this can happen just the first time right?
        printf("Lista vuota\n");
        exit(1);
    }

    if(head->next == NULL)
        return head->val;

    e = trovaMassimo(head->next); //what will be assigned to e? doing this way doesn't e get modified all times till the last value? if yes isn't useless that if right under?

    if ( e < head->val )
        return head->val;
    else
        return e;
}

```

Answer 1

You have a portability bug, because names ending in _t are reserved for future Standard Library types. Rename node_t, perhaps to Node.

---

This kind of recursion is problematic, because it can't be transformed into iterative form by the compiler. It needs to keep each call's e value until all the inner recursive calls have completed, before it can do the comparison.

If you can, strive to make your function tail-recursive, which means that it's in the form:

ResultType function(args) {
    ...
    return function(other_args);
}

To make a non-tail recursive function into a tail-recursive one, you generally need to pass the current state into the recursive call.

Here, I'd actually split the function into two: a recursive function to find the node_t with largest value (or NULL if the list is empty), and a wrapper function to call it with the right parameters, extract the result, and handle errors:

/* untested */

static const Node *find_node_max(Node *list, Node *best_so_far)
{
    if (!list) {
       return best_so_far;
    }
    if (!best_so_far || list->val > best_so_far->val) {
        best_so_far = list;
    }
    return find_node_max(list->next, best_so_far);
}

int trovaMassimo(const Node *head) {
    const Node *n = find_node_max(head, NULL);
    if (!n) {
        /* empty list - N.B. message to stderr, not stdout */
        fputs("Lista vuota\n", stderr);
        exit(1);   /* not good in library code */
    }
    return n->val;
}

Answer 2

By

doesn't e get modified all times

I think you are asking why e retains its original value even after it gets changed by recursive calls.

Part of the misunderstanding is the way e is defined:

int e;

If you had instead said:

static int e;

then yes, every time the value gets changed in a recursive call, the value in the calling function will also get changed. With static storage there is only a single instance of e. Defining it that way would indeed have produced incorrect results.

If you had instead said:

auto int e;

then no, the recursive calls will not affect the value in the calling function. Each invocation of the function causes storage to be automatically allocated on the stack for another instance of e. If it recurses a thousand times, at the deepest level there will be a thousand distinct instances of e on the stack. And at each level, the function can see only its own copy.

Now C has a history of letting programmers be lazy (one of its major faults), and if one omits the word "auto" or "static" the compiler notices the context and decides what you really meant.

In this case, it did the right thing (it almost always does) and knew that you really meant "auto", and allocated a separate storage location for each invocation.

Most programmers do omit the keyword auto, but I prefer to always use it, both to remind me that it isn't static, global, external, or (in older versions) block common, and to make it easier to find when I'm searching for definitions.