What is the difference between head and tail recursion when reversing a linked list?

Question

I am learning about different recursive approaches for reversing a linked list in C++. I have implemented both head and tail recursion methods, but I'm unsure about their differences and which one is more optimal.

Which type of recursion writing would be the optimized for reversing a linked list using recursion 1.Head recursion 2.Tail recursion

Answer 1

Here is my implementation using head recursion:

#include <iostream>
using namespace std;

struct node {
    int data;
    node* next;
    node(int val) : data(val), next(nullptr) {}
};

node* reverse(node* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    node* rest = reverse(head->next); // Reverse the rest of the list
    head->next->next = head;          // Adjust the next pointer of the next node
    head->next = nullptr;             // Set the next pointer of the current node to nullptr
    return rest;                      // Return the new head of the reversed list
}

// Helper function to print the linked list
void printList(node* head) {
    while (head != nullptr) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    // Create the linked list: 1 -> 2 -> 3 -> 4 -> 5
    node* head = new node(1);
    head->next = new node(2);
    head->next->next = new node(3);
    head->next->next->next = new node(4);
    head->next->next->next->next = new node(5);

    // Print the original linked list
    cout << "Original list: ";
    printList(head);

    // Reverse the linked list using head recursion
    head = reverse(head);

    // Print the reversed linked list
    cout << "Reversed list using head recursion: ";
    printList(head);

    return 0;
}

And here is my implementation using tail recursion:

 #include <iostream>
    using namespace std;
    
    struct node {
        int data;
        node* next;
        node(int val) : data(val), next(nullptr) {}
    };
    
    node* helper(node* current, node* prev) {
        if (current == nullptr) {
            return prev;
        }
        node* next = current->next;
        current->next = prev;
        return helper(next, current); // Tail recursion
    }
    
    node* tailReverse(node* head) {
        return helper(head, nullptr);
    }
    
    // Helper function to print the linked list
    void printList(node* head) {
        while (head != nullptr) {
            cout << head->data << " ";
            head = head->next;
        }
        cout << endl;
    }
    
    int main() {
        // Create the linked list: 1 -> 2 -> 3 -> 4 -> 5
        node* head = new node(1);
        head->next = new node(2);
        head->next->next = new node(3);
        head->next->next->next = new node(4);
        head->next->next->next->next = new node(5);
    
        // Print the original linked list
        cout << "Original list: ";
        printList(head);
    
        // Reverse the linked list using tail recursion
        head = tailReverse(head);
    
        // Print the reversed linked list
        cout << "Reversed list using tail recursion: ";
        printList(head);
    
        return 0;
    }

**Analysis

Linked List Size: 4 Nodes (1 -> 2 -> 3 -> 4)**

Head Recursion Approach

First call: reverse(head) where head points to node 1.

Second call: reverse(head->next) where head->next points to node 2.

Third call: reverse(head->next) where head->next points to node 3.

Fourth call: reverse(head->next) where head->next points to node 4.

Fifth call: reverse(head) where head is now nullptr.

Once the base case is reached, each of these calls returns in reverse order, making adjustments to the pointers:

The fourth call (node 4) returns.

The third call (node 3) returns, adjusting node 4's next pointer.

The second call (node 2) returns, adjusting node 3's next pointer.

The first call (node 1) returns, adjusting node 2's next pointer.

In total, there are 4 function calls to reach the base case and 4 function returns to adjust the pointers, totaling 8 function calls.

Tail Recursion Approach

First call: reverseUtil(head, nullptr) where head points to node 1 and prev is nullptr.

Second call: reverseUtil(head->next, head) where head points to node 2 and prev points to node 1.

Third call: reverseUtil(head->next, head) where head points to node 3 and prev points to node 2.

Fourth call: reverseUtil(head->next, head) where head points to node 4 and prev points to node 3.

Fifth call: reverseUtil(head->next, head) where head is nullptr and prev points to node 4.

In total, there are 4 function calls to reach the base case and 1 return from the base case, totaling 5 function calls.

Conclusion : Head Recursion Approach: 8 function calls in total (4 calls to reach the base case and 4 returns to adjust pointers). Tail Recursion Approach: 5 function calls in total (4 calls to reach the base case and 1 final return).