Recursion on Linked Lists

July 2026 · 21 min read

A linked list is the simplest recursive data type there is. Written as an algebraic type it is literally List = null | (value, List): a list is either empty, or one value followed by another list. That definition is recursive, so structural induction applies directly — and every list algorithm you can write as a loop, you can also write by pattern-matching on those two cases. This post gives you the template, shows five instances of it, then spends the rest of its time on the thing recursion gets you fired for: blowing the stack.

The List Is a Recursive Type

Because List = null | (value, List) has exactly two shapes, every recursive function over a list has exactly two branches, and they line up one-to-one with the type’s cases. That gives a template you can write without thinking:

Result f(Node* head) {
    if (!head) return base;             // case 1: the empty list
    Result rest = f(head->next);        // solve the smaller list first
    return combine(head->val, rest);    // case 2: fold this node into the result
}

Three blanks to fill: the base value for the empty list, the recursive call on head->next (the strictly smaller subproblem that guarantees termination), and the combine step. Fill them in and the function is correct by induction: it works for the empty list, and if it works for a list of length n−1 it works for length n.

The "strictly smaller" part is not decoration — it is what makes the recursion well-founded. Each call passes head->next, one node shorter, so the argument shrinks monotonically toward the base case and the recursion is guaranteed to stop. On a well-formed acyclic list that happens for free; on a list that contains a cycle it does not, and the recursion never reaches null — one more reason to run cycle detection before you hand a list to a recursive function you did not write.

Five Instances of One Template

Watch how little changes between them — only the base and the combine.

int length(Node* head) {
    if (!head) return 0;                          // base = 0
    return 1 + length(head->next);                // combine = 1 + rest
}

long sum(Node* head) {
    if (!head) return 0;                          // base = 0
    return head->val + sum(head->next);           // combine = val + rest
}

bool contains(Node* head, int target) {
    if (!head) return false;                      // base = false
    return head->val == target || contains(head->next, target);
}

Node* reverse(Node* head) {
    if (!head || !head->next) return head;        // base = the last node
    Node* newHead = reverse(head->next);          // reverse the rest
    head->next->next = head;                      // the next node points back at me
    head->next = nullptr;                         // I become the new tail
    return newHead;
}

void printReverse(Node* head) {
    if (!head) return;                            // base = do nothing
    printReverse(head->next);                     // recurse first...
    std::cout << head->val << ' ';                 // ...print on the way back
}

length, sum, and contains are almost copies of each other. reverse looks different only because its "combine" is a two-line pointer surgery instead of an arithmetic operator. And printReverse is the one that reveals the real subtlety of recursion: when the work happens.

Work on the Way Down vs. the Way Up

Every recursive call has two moments you can attach work to: before the recursive call (on the way down, as the stack grows) and after it returns (on the way up, as the stack unwinds). Printing a list forwards and backwards differ by exactly which moment you choose:

void printForward(Node* head) {
    if (!head) return;
    std::cout << head->val;    // work BEFORE recursing  => head recursion, prints in order
    printForward(head->next);
}

void printBackward(Node* head) {
    if (!head) return;
    printBackward(head->next);
    std::cout << head->val;    // work AFTER recursing   => prints in reverse
}

One line moves, and the output reverses. That is the entire idea behind the recursive palindrome check below: by doing the comparison on the way up, the recursion hands you the nodes back in reverse order for free, while a second pointer walks forward — letting you compare front against back without ever reversing anything.

Worked trace: sum(1→2→3)

The same computation the animation runs, written out. Indentation is stack depth; the additions all land on the unwind:

sum(1)                     // descend: push frame, recurse before adding anything
  sum(2)
    sum(3)
      sum(null) = 0        // base case reached at depth 4 (length + 1)
    sum(3) = 3 + 0 = 3     // unwind: each frame adds its value on the way back up
  sum(2) = 2 + 3 = 5
sum(1) = 1 + 5 = 6         // final answer, produced entirely on the return path

Tail Recursion and Why It Becomes a Loop

A call is in tail position when it is the very last thing the function does — nothing is pending after it returns. Compare:

// NOT tail-recursive: the "1 +" is pending work that must run AFTER the call returns,
// so every frame has to stay alive. Stack depth = list length.
int length(Node* head) {
    if (!head) return 0;
    return 1 + length(head->next);
}

// Tail-recursive: the recursive call is the last action; the running count is carried
// in an accumulator, so nothing is pending when the call returns.
int lengthTail(Node* head, int acc = 0) {
    if (!head) return acc;
    return lengthTail(head->next, acc + 1);
}

Under -O2, GCC and Clang compile lengthTail into a plain loop: because no work is pending after the recursive call, the compiler reuses the current stack frame instead of pushing a new one — tail-call optimization, which turns the "call" into a jump. The result runs in O(1) stack space. The non-tail length cannot be optimised this way: the pending 1 + forces each frame to survive until its child returns, so it uses O(n) stack and can overflow.

Palindrome Linked List (LeetCode 234), Three Ways

"Is this list a palindrome?" is the canonical showcase for recursion on lists, because the three accepted solutions trade space, cleverness, and side effects against each other.

1. Copy to an array — O(n) space

bool isPalindrome(ListNode* head) {
    std::vector<int> v;
    for (ListNode* p = head; p; p = p->next) v.push_back(p->val);
    for (int i = 0, j = (int)v.size() - 1; i < j; ++i, --j)
        if (v[i] != v[j]) return false;
    return true;
}

Dead simple, O(n) time, O(n) space. It works because an array gives you the two-ended access a list denies you. Perfectly acceptable when memory is not the constraint.

2. Recursion with a forward pointer — O(n) stack

class Solution {
    ListNode* front;                     // shared state; advances as recursion unwinds
public:
    bool isPalindrome(ListNode* head) {
        front = head;
        return check(head);
    }
    bool check(ListNode* node) {
        if (!node) return true;          // reached the tail
        if (!check(node->next)) return false;      // recurse to the end FIRST
        if (node->val != front->val) return false; // compare back-node vs front-node
        front = front->next;             // advance front on the way UP
        return true;
    }
};

This is the "work on the way up" idea taken to its conclusion. The recursion drives node to the tail and hands the nodes back in reverse as it unwinds; meanwhile front walks from the head forward. At unwind level i, node is the i-th node from the end and front is the i-th from the start, so a single comparison checks the pair. Elegant, but it still uses O(n) stack — the same liability as any depth-n recursion.

3. Reverse the second half — O(1) space, and restore it

bool isPalindrome(ListNode* head) {
    if (!head || !head->next) return true;
    ListNode *slow = head, *fast = head;             // 1. find the middle
    while (fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; }

    ListNode* second = reverse(slow->next);          // 2. reverse the second half
    ListNode *p1 = head, *p2 = second;               // 3. compare the two halves
    bool ok = true;
    while (p2) { if (p1->val != p2->val) { ok = false; break; } p1 = p1->next; p2 = p2->next; }

    slow->next = reverse(second);                    // 4. RESTORE the list, then answer
    return ok;
}

More Instances: Merge, Remove, Flatten

Once you see the template, whole problems fall out of it in a few lines.

// Merge two sorted lists: base case is "one list is empty", combine is "take the smaller head".
ListNode* merge(ListNode* a, ListNode* b) {
    if (!a) return b;
    if (!b) return a;
    if (a->val <= b->val) { a->next = merge(a->next, b); return a; }
    else                  { b->next = merge(a, b->next); return b; }
}

// Remove every node equal to val: fix the rest first, then decide whether to drop myself.
ListNode* removeElements(ListNode* head, int val) {
    if (!head) return nullptr;
    head->next = removeElements(head->next, val);
    return head->val == val ? head->next : head;
}

Flattening a multilevel list is the same shape with two recursive edges instead of one — you recurse into the child branch and the next branch and splice the results. Its depth is bounded by the nesting, not the total node count, which (as the next section explains) is exactly why flattening is safe to write recursively while sum is not. The full treatment lives in Flattening Multilevel Lists.

The Stack Limit, in Numbers

Here is the arithmetic that decides whether a recursive list function is a clever solution or a latent crash. On Linux the default thread stack is 8 MB. A single frame for one of these simple recursions — a saved return address, a saved frame pointer, one or two Node* locals, and alignment padding — costs roughly 48–64 bytes. So:

8 MB / 64 bytes  =  131,072 frames
8 MB / 48 bytes  =  174,762 frames

A recursion whose depth equals the list length therefore overflows and segfaults somewhere around a few hundred thousand nodes. A list of 1,000,000 nodes — trivial for an iterative loop — blows the stack every time. This is not theoretical: it is the single most common reason a linked-list solution that passes small tests dies on the large ones.

The fix is the mechanical recursion → iteration conversion:

• Tail recursion → a loop with an accumulator. You already saw lengthTail; drop the call and write the while.
• Non-tail recursion → an explicit stack. When work happens on the way up, simulate the call stack with a std::stack<Node*>: push nodes going forward, then pop them to do the deferred work. This moves the frames from the (small, fixed) call stack to the (large, growable) heap.

Two objections come up every time. "Can’t I just raise the stack limit?" You can — ulimit -s for the main thread, or constructing a std::thread with a larger stack — but that only pushes the cliff edge a bit further out; a big enough list still walks off it, and you have made correctness depend on the environment the code happens to run in. "Isn’t recursion clearer?" Frequently, yes — which is why the right habit is to prototype recursively for clarity, then convert the depth-n cases to iteration before they ever meet production-sized input. Because both conversions above are mechanical, clarity and safety are not actually in tension.

The rule compresses to one line: recursion is safe when its depth is bounded by something small — the nesting depth, log n, a constant — and dangerous when its depth is the list length. Reach for recursion to express an algorithm clearly, then check the depth before you ship it.

Check Yourself

Each item gives a situation; pick the statement that is actually true.

Practice

• LeetCode 234 — Palindrome Linked List work-on-unwind write all three ways; restore the list in the O(1) one.
• LeetCode 206 — Reverse Linked List template recursive and iterative; compare stack usage.
• LeetCode 21 — Merge Two Sorted Lists combine the recursive merge is four lines.
• LeetCode 203 — Remove Linked List Elements filter fix the rest, then decide about the head.
• LeetCode 24 — Swap Nodes in Pairs structural a clean two-node-at-a-time recursion.
• LeetCode 2 — Add Two Numbers carry try it recursively, passing the carry down.