Understanding Recursion

Recursion occurs when a procedure or function includes a call to itself. This is known as direct recursion. When function A calls function B, and function B then calls function A, this is called indirect recursion.

Designing Recursive Algorithms

Recursive problem-solving follows a consistent pattern: decompose the entire problem into smaller subproblems, solve each subproblem, and combine the results to obtain the final solution. These subproblems share the same solving approach as the original problem, allowing them to be further divided until they become simple enough to solve directly. This process of decomposition from the top, solving, then combining results is called recursive problem-solving—a divide-and-conquer algorithmic strategy.

Practical Examples: Recursive Linked List Operations

Consider a singly linked list without a dummy head node, defined as follows:

typedef struct ListNode {
    ElemType data;
    struct ListNode *link;
} ListNode;

Let head represent the pointer to such a list. Notice that head->link also represents a valid linked list (with one fewer node). This self-similar property makes recursion an elegant solution approach.

Below are eight common recursive operations on linked lists:

1. Counting Nodes in a Linked List

Functon countNodes returns the number of nodes in the list:

int countNodes(ListNode *head) {
    if (head == NULL)
        return 0;
    return 1 + countNodes(head->link);
}

2. Forward Traversal and Display

Function displayForward prints all node values in forward order:

void displayForward(ListNode *head) {
    if (head != NULL) {
        printf("%d ", head->data);
        displayForward(head->link);
    }
}

3. Reverse Traversal and Display

Function displayBackward prints all node values in reverse order:

void displayBackward(ListNode *head) {
    if (head != NULL) {
        displayBackward(head->link);
        printf("%d ", head->data);
    }
}

4. Deleting First Occurrence of a Value

Function deleteFirst removes the first node containing a specified value:

void deleteFirst(ListNode **headRef, ElemType value) {
    ListNode *temp;
    if (*headRef == NULL)
        return;
    
    if ((*headRef)->data == value) {
        temp = *headRef;
        *headRef = (*headRef)->link;
        free(temp);
    } else {
        deleteFirst(&((*headRef)->link), value);
    }
}

5. Deleting All Occurrences of a Value

Function deleteAll removes every node containing the specified value:

void deleteAll(ListNode **headRef, ElemType value) {
    ListNode *temp;
    if (*headRef == NULL)
        return;
    
    if ((*headRef)->data == value) {
        temp = *headRef;
        *headRef = (*headRef)->link;
        free(temp);
        deleteAll(headRef, value);
    } else {
        deleteAll(&((*headRef)->link), value);
    }
}

6. Finding Maximum Value

Function findMax returns the largest value in the list:

ElemType findMax(ListNode *head) {
    ElemType maxOfRest;
    if (head->link == NULL)
        return head->data;
    
    maxOfRest = findMax(head->link);
    return (maxOfRest > head->data) ? maxOfRest : head->data;
}

7. Finding Minimum Value

Function findMin returns the smallest value in the list:

ElemType findMin(ListNode *head) {
    ElemType minOfRest;
    if (head->link == NULL)
        return head->data;
    
    minOfRest = findMin(head->link);
    return (minOfRest < head->data) ? minOfRest : head->data;
}

8. Releasing All Nodes

Function freeList deallocates memory for all node in the list:

void freeList(ListNode *head) {
    if (head != NULL) {
        freeList(head->link);
        free(head);
    }
}

Key Observations

These recursive implementations leverage the inherent structure of linked lists—where the tail (starting from the second node) is itself a valid linked list. The base case typically handles the empty list (NULL pointer) or a single-node list, while the recursive case processes the curent node and delegates the remaining work to the tail sublist.