Recursion - nth element from last in a linkedlist

Question

Can someone please explain the following function ?

void printNthFromLast(struct node* head, int n) 
{
    static int i = 0;
    if(head == NULL)
       return;
    printNthFromLast(head->next, n);
    if(++i == n)
       printf("%d", head->data);
}

I just want to know how order of execution of statements occur in recursion i.e given recursive call is before the second if condition , so will the second if condition be checked ?

Answer 1

I just want to know how order of execution of statements occur in recursion i.e given recursive call is before the second if condition , so will the second if condition be checked ?

Yes, the second if condition will be checked, after the recursive call returns. And it will return, provided the recursion terminates by reaching the end of the linked list. This concept is essential to understanding recursion. Most particularly, you must understand that each function call, including recursive ones, executes in its own context, and upon return control resumes immediately after the call. It's associated with the flow of execution, not with the function that is called -- you don't lose your place by calling a function recursively.

Answer 2

The function printNthFromLast calls itself recursively for every node in the linked list. Upon return, i is incremented and the field data is printed only for the nth return from recursion, hence for the nth item from the end of the list, the last counting as 1. printNthFromEnd would be a more precise name for it.

This function is interesting as a quiz only: it updates a global inaccessible state and thus only works correctly once! It is the epitome of non-reentrant behaviour: not only should it not be used in different threads, it should not be used more than once, period. This method could be extended to fetch the nth mode from the end via another static variable:

void getNthFromEnd(struct node *head, int n) {
    static int i = 0;
    static struct node *np = NULL;
    if (head != NULL) {
        getNthFromEnd(head->next, n);
        if (++i == n) np = head;
    }
    return np;
}

A much better alternative is this:

struct node *getNthFromEnd(struct node *head, int n) {
    struct node *np;

    for (np = head; n > 0; n--) {
        if (np == NULL) return NULL;
        np = np->next;
    }
    while (np != NULL) {
        head = head->next;
        np = np->next;
   }
    return head;
}