Recursion on lists and the stack limit

Why this matters

Recursion means a function that calls itself. A linked list suits recursion well, because a list is a node followed by another list. Many list problems have a short recursive answer, and the tree lessons later in this course rely on the same idea.

Recursion has a limit that a loop does not have. Every call uses a small amount of memory from a fixed area called the call stack. A list with enough nodes uses up that area, and the program stops with a crash. This lesson shows how to write recursive list functions, how to see the calls on the stack, and how to rewrite them as loops so that the size of the list does not matter.

The code uses the Node struct from the earlier lessons of this module. A node holds an int called value and a pointer called next. A pointer is a variable that stores the memory address of another value. The next pointer of the last node is nullptr, which means "points to nothing".

A function that calls itself, in plain words

Picture a line of people, and you want to know how many people are in it. You can see only the person in front of you. You ask that person how many people are behind them. They ask the person behind them, and so on. The last person says "nobody behind me, so the answer is zero". Each person then adds one to the answer they received and passes it back. The first person hears the total.

That is recursion. The function answers a question about the whole by asking the same question about a smaller part, then adding its own piece. Every recursive function needs two parts.

• A base case. This is the simplest input, where the function answers without calling itself. For a list, the base case is the empty list, which is nullptr.
• A recursive case. This handles one piece of the input and calls the same function for the rest. For a list, that means handling the current node and calling the function on head->next.

Before writing any recursive function, answer three questions. What is the smallest input, and what should the function return for it? When the input is larger, which part can the function handle right now? What answer does the rest give, and how is it combined with the part just handled? For length_rec, an empty list gives 0, the current node counts as 1, and the rest gives its own count, which is added to 1. Each answer maps to one line of the function.

Each call is a separate run of the function. It has its own copy of its parameters and its own local variables. The computer records the active calls on the call stack. Picture the stack as a pile of sheets of paper. A call writes its details on a new sheet and puts it on top. The top sheet is the call that is running now. When a call finishes, its sheet is removed, and the sheet below continues from the line where it stopped. The pile has a maximum height. That maximum is the stack limit, and the rest of this lesson returns to it.

Example 1: counting the nodes

The first function counts the nodes in a list.

int length_rec(const Node* head) {
    if (head == nullptr) {
        return 0;                       // base case: an empty list has 0 nodes
    }
    return 1 + length_rec(head->next);  // this node, plus the count of the rest
}

Read the function against the line-of-people picture. The if is the base case. When head is nullptr, there are no nodes left, so the function returns 0 without calling itself. The last line is the recursive case. It asks for the count of the rest of the list, then adds 1 for the current node.

Trace the call on the list 1, 2, 3, 4. Each call waits for the call below it to return, so the calls pile up on the stack before any of them can finish.

The first call to start is the last one to finish. Call 5 returns 0 first. Call 4 then finishes with 1, call 3 with 2, call 2 with 3, and call 1 with 4. The answer travels back up the pile, one sheet at a time.

The complete program at the end of Example 3 prints this trace with one line per call. Its output shows the pile going down and then coming back up.

Example 2: sum, and printing in reverse order

The sum uses the same pattern. The value of the current node is added to the sum of the rest.

long long sum_rec(const Node* head) {
    if (head == nullptr) {
        return 0;
    }
    return head->value + sum_rec(head->next);
}

The long long type holds larger numbers than int. It is used here so that the total of many large values does not overflow.

A more surprising example is printing a list in reverse order. The trick is to put the print line after the recursive call, not before it.

void print_reverse(const Node* head) {
    if (head == nullptr) {
        return;
    }
    print_reverse(head->next);            // first, handle everything after this node
    std::cout << head->value << ' ';      // then print this node
}

On the list 1, 2, 3, 4, the call for node 1 reaches the recursive call first and waits. The call for node 2 waits too. The calls for nodes 3 and 4 also wait. The call for node 4 reaches its print line first, because its recursive call on nullptr returns at once. So the output starts with 4. After that, the waiting calls resume in the order they were stacked, which prints 3, 2 and then 1. The output is 4 3 2 1.

The order of the lines decides the behaviour. A line before the recursive call runs on the way down, in list order. A line after the recursive call runs on the way up, in reverse list order. Keep this rule in mind when you convert recursion to a loop later in the lesson.

Example 3: reversing a list with recursion

Reversal is harder, because the function must change pointers, not just read values. Here is the recursive version. It returns the new head of the reversed list.

Node* reverse_rec(Node* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;                       // empty list or one node: nothing to turn
    }
    Node* new_head = reverse_rec(head->next);  // reverse the rest first
    head->next->next = head;               // the node after head now points back to head
    head->next = nullptr;                  // head becomes the new end of the list
    return new_head;                       // the head of the whole reversed list
}

The base case has two parts. An empty list is returned as it is. A list with one node is also returned as it is, because one node is already reversed.

The recursive case is the hardest part to read. When the call for head gets control back, the rest of the list is already reversed, and new_head is its first node. Node head->next is now the last node of that reversed rest, and its next pointer is nullptr. Setting head->next->next = head attaches the current node after it. Setting head->next = nullptr makes the current node the end.

Trace the list 1, 2, 3. Each row shows what one call does after its recursive call returns.

The list now reads 3, 2, 1. The value 3 is returned by every call, because node 3 is the head of the reversed list at every level.

The caller must keep the returned head. The caller also has to store it, as in list = reverse_rec(list);. The Common mistakes section shows what happens when it is not stored.

Here is the complete program. It builds a list, prints the calls as they happen, reverses the list recursively, and frees the nodes at the end.

Compiled with g++ -std=c++20 -Wall -Wextra, it prints:

list: 1 2 3 4 
length_rec: 4
sum_rec: 10
reverse order: 4 3 2 1 
--- trace ---
enter depth 0 node 1
  enter depth 1 node 2
    enter depth 2 node 3
      enter depth 3 node 4
        enter depth 4 node -1
        return 0
      return 1
    return 2
  return 3
return 4
--- end trace ---
after reverse_rec: 4 3 2 1 
length_loop: 4

The trace shows the pile. Each enter line is a call going onto the stack. Each return line is a call coming off it. Indentation is the depth, so the deepest call is the most indented.

Turning recursion into a loop

A recursive function can be rewritten as a loop when its work is done in list order, or when the loop can keep the values it needs in a container. Two rewrites show the two cases.

The length function does its work on the way down, so a loop that walks forward is enough.

int length_loop(const Node* head) {
    int count = 0;
    for (const Node* cur = head; cur != nullptr; cur = cur->next) {
        ++count;
    }
    return count;
}

Printing in reverse does its work on the way up. A loop that walks forward would print in list order. The loop must first remember the values, then print them from the back. A std::vector works for this. It is the standard library's resizable array. Its values are stored on the heap, which is the large memory area used for new, so it does not use the call stack.

void print_reverse_loop(const Node* head) {
    std::vector<int> values;
    for (const Node* cur = head; cur != nullptr; cur = cur->next) {
        values.push_back(cur->value);
    }
    for (auto it = values.rbegin(); it != values.rend(); ++it) {
        std::cout << *it << ' ';
    }
    std::cout << '\n';
}

The loop version of reverse_rec is the three-pointer loop from the reversal lesson earlier in this module. It uses three local variables and no recursion, so its size does not depend on the call stack.

A rewrite is correct when it returns the same answer for every list. Test the loop version against the recursive version on several lists, including the empty list. A list with one node is also a useful test, because it hits the base case at once.

The stack limit

The call stack has a fixed size. On Linux, the ulimit command shows the size of the stack for the current shell, in kilobytes.

ulimit -s

On the machine used to test this lesson, the output was (yours can differ):

8192

That is 8192 kilobytes, or about 8 MB. Windows programs often get a smaller default, commonly 1 MB, so the same recursive function can fail earlier there.

To see the limit, the test program below builds a list of n nodes, calls length_rec, and prints the count. The argument n comes from the command line.

#include <cstdlib>
#include <iostream>
#include <vector>
 
struct Node {
    int value;
    Node* next;
};
 
Node* build_list(std::size_t n) {
    Node* head = nullptr;
    for (std::size_t i = 0; i < n; ++i) {
        head = new Node{static_cast<int>(i), head};
    }
    return head;
}
 
void free_list(Node* head) {
    while (head != nullptr) {
        Node* next = head->next;
        delete head;
        head = next;
    }
}
 
int length_rec(const Node* head) {
    if (head == nullptr) {
        return 0;
    }
    return 1 + length_rec(head->next);
}
 
int length_loop(const Node* head) {
    int count = 0;
    for (const Node* cur = head; cur != nullptr; cur = cur->next) {
        ++count;
    }
    return count;
}
 
int main(int argc, char** argv) {
    std::size_t n = argc > 1 ? std::strtoull(argv[1], nullptr, 10) : 10;
    bool use_loop = argc > 2;
    Node* list = build_list(n);
    int len = use_loop ? length_loop(list) : length_rec(list);
    std::cout << "n=" << n << " length=" << len << '\n';
    free_list(list);
    return 0;
}

It was compiled with g++ -std=c++20 -Wall -Wextra -o depth depth.cpp and run for several sizes. The test checked the exit code, which is 0 for success. A crash by a segmentation fault gives 139, which is 128 plus 11, the number of the signal for a segmentation fault.

With 200000 nodes the program also finished with exit code 0, and with 400000 it crashed. So on this build, the limit lies between those two sizes. That gives about 21 to 42 bytes per call, since 8 MB divided by 400000 calls is about 21 bytes and divided by 200000 calls is about 42 bytes. The exact number depends on the compiler, the optimisation level and the machine, so the lesson does not give a fixed size. The point is that a limit exists and that a list with a million nodes is past it.

The same program with length_loop in place of length_rec handled 1000000 nodes and printed length=1000000. The loop uses the same memory for any list length.

When the stack runs out, the operating system stops the program. Built with AddressSanitizer, which is a checking tool built into g++ that reports memory errors while the program runs, the same crash gives a clear message:

AddressSanitizer:DEADLYSIGNAL
==182556==ERROR: AddressSanitizer: stack-overflow on address 0x7fffba56eff8 (pc 0x5c31ca8e84b8 bp 0x7fffba56f010 sp 0x7fffba56f000 T0)

The address and the process number change on each run. The next lines of the report show the same function, length_rec, many times. That repeated line is the sign of a recursion that is too deep.

Common mistakes

Missing base case

A recursive function with no base case calls itself forever. Here is a version of length_rec with the if removed.

int bad_length(const Node* head) {
    return 1 + bad_length(head->next);
}

The compiler warns about it before the program runs:

warning: infinite recursion detected [-Winfinite-recursion]

The program does not reach the stack limit. At the last node, head->next is nullptr, and the next call reads head->next through a null pointer. The AddressSanitizer report for the program with three nodes was:

AddressSanitizer:DEADLYSIGNAL
==175773==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000008 (pc 0x626314d0b322 bp 0x7ffd7c39a100 sp 0x7ffd7c39a0f0 T0)
==175773==The signal is caused by a READ memory access.

The address 0x8 is the offset of next inside a node, which is 8 bytes after the start of the node. It means the code read next from a node that did not exist. Without the sanitizer, the same program exits with code 139.

Forgetting to keep the returned head

reverse_rec returns the new head. A function that ignores that value and returns the old head loses track of the reversed list. Here is a version that returns head at the end, instead of new_head.

Node* bad_reverse(Node* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    bad_reverse(head->next);
    head->next->next = head;
    head->next = nullptr;
    return head;
}

On the list 1, 2, 3 the program printed this line:

bad_reverse head value: 1

The reversed list is 3, 2, 1, so the head should have value 3. The value 1 is the old head, which is now the end of the list. The program compiled without a warning, so the mistake is only visible in the output. Check the first value of the result as well as the order of the rest.

Checking the next pointer before checking for null

The base case must test for nullptr on head before it reads head->next. A version that tests head->next == nullptr first reads through head when the list is empty, and that is a null pointer read, the same kind of crash shown above. Put the head == nullptr check first in every recursive list function.

Recursing on very long lists

A recursive function is safe only when the list is short enough for the stack. For a list of unknown length, such as one read from a file, use a loop. The stack section shows the size where a recursive function fails on one build.

Practice

Exercise 1

Write count_even_rec, which returns how many values in the list are even. A value is even when value % 2 is 0. Use recursion.

Show the answer

int count_even_rec(const Node* head) {
    if (head == nullptr) {
        return 0;
    }
    int here = (head->value % 2 == 0) ? 1 : 0;
    return here + count_even_rec(head->next);
}

On the list 4, 7, 2, 9, 6 this returns 3, because the even values are 4, 2 and 6.

Exercise 2

Write contains_rec(const Node* head, int target), which returns true when some node has the value target, and false otherwise.

Show the answer

bool contains_rec(const Node* head, int target) {
    if (head == nullptr) {
        return false;
    }
    if (head->value == target) {
        return true;
    }
    return contains_rec(head->next, target);
}

The base case is the empty list, which cannot contain the target. The first check returns at once when the current node matches, so the calls stop early.

Exercise 3

Predict the output of print_reverse on the list 5, 6, 7. Then check your answer.

Show the answer

The output is 7 6 5 , with a trailing space. The call for node 7 reaches its print line first, then the waiting calls print 6 and 5.

Exercise 4

Rewrite contains_rec from Exercise 2 as a loop.

Show the answer

bool contains_loop(const Node* head, int target) {
    for (const Node* cur = head; cur != nullptr; cur = cur->next) {
        if (cur->value == target) {
            return true;
        }
    }
    return false;
}

The recursive version also walks the list in order, so the loop follows the same path. The loop uses one local pointer, so it does not grow with the list.

Exercise 5

The function below is meant to return the last value in a list. It crashes on the empty list. Find the bug and fix it.

int last_rec(const Node* head) {
    return head->next == nullptr ? head->value : last_rec(head->next);
}

Show the answer

The bug is that the function reads head->next when head is nullptr. The fix is to test for the empty list first. This version throws an exception, which the caller can catch, because an empty list has no last value.

int last_rec(const Node* head) {
    if (head == nullptr) {
        throw std::invalid_argument("empty list has no last value");
    }
    if (head->next == nullptr) {
        return head->value;
    }
    return last_rec(head->next);
}

The header <stdexcept> is needed for std::invalid_argument. A caller that does not catch it stops the program with an error message, so the choice of exception or a default value is part of the design.

Summary

• A recursive function needs a base case that returns without calling itself, and a recursive case that works on a smaller list.
• Work placed before the recursive call runs in list order, and work placed after it runs in reverse list order.
• Each active call takes memory on the call stack, and a long enough list crashes the program.
• A loop that uses a few local pointers or a std::vector gives the same answer without that growth.
• Always test for nullptr first, and store the head that a reversal returns.