Recursion on Python linked lists and the recursion limit

Why this matters

Many list problems have a short recursive answer. Recursion means a function calls itself. The length of a list, its sum, and its reversal can each be written in a few lines this way, and interviewers often ask for the recursive version first.

The short version has a cost. Python keeps a record of every call that has started but has not finished. For a list with 100,000 nodes, the recursive version asks Python to keep 100,000 unfinished calls in memory at the same time. Python caps that record at a fixed depth, called the recursion limit. When a call goes past the cap, the program stops with an error named RecursionError.

This lesson writes list recursion, shows where the cap is reached, and then rewrites the same functions as loops. The lesson uses one small node class and does not repeat how singly linked lists are built. That is covered in the earlier lesson on singly linked lists in this module.

The node class and two helpers

Every example uses the same node class. A node holds a value and a link called next that points at the next node. The last node has next set to None, which is Python's word for "points at nothing".

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

__init__ is the function that runs when a new node is created. self is the node being set up. The next=None part means next is optional, and it is None when you leave it out.

Building a list one node at a time is clumsy in examples, so the next helper builds a list from a row of values. It starts from the last value, because each new node must point at the list that is already built.

def from_values(*values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head

The * before values means the function takes any number of arguments. from_values(10, 20, 30) works, and so does from_values(), which returns None, the empty list. The name head is the usual name for the first node of a list.

The third helper turns a list into text so the output is easy to read.

def show(head):
    parts = []
    cur = head
    while cur is not None:
        parts.append(str(cur.value))
        cur = cur.next
    return " -> ".join(parts) if parts else "(empty)"

parts is a list of text pieces. " -> ".join(parts) glues the pieces together with arrows between them. The while loop walks the list from the first node to the last, which is the loop form you will convert the recursion into later in this lesson.

The idea: solve the rest, then add your part

Take the list 10 -> 20 -> 30. Its length is 3. Look at it another way. The first node holds 10, and the rest of the list is 20 -> 30, which is a shorter list. The length of the whole list is 1 for the first node plus the length of the rest. The rest has length 2 by the same rule, and so on, until nothing is left.

A recursive function has two parts.

• Base case. The simplest input, where the answer is known without another call. For a list, that is the empty list, which is None. The length of None is 0.
• Recursive step. The function calls itself on a smaller input, then combines that answer with its own piece. For length, the own piece is 1.

If the base case is missing, or the recursive step does not make the input smaller, the calls never stop. The Common mistakes section shows what that looks like.

Worked example 1: the length of a list

Here is the length function. It is the first example, so every line is explained.

def length(node):
    if node is None:
        return 0
    return 1 + length(node.next)

The first if is the base case. If the node is None, there are no more nodes, so the answer is 0. The last line is the recursive step. It says: the length from this node is 1, plus the length of the list that starts at the next node.

Here is what happens for the list 10 -> 20 -> 30. Each line is one call. The function does not finish a line until the call under it has returned an answer.

length(10 -> 20 -> 30) waits for length(20 -> 30)
length(20 -> 30)       waits for length(30)
length(30)             waits for length(None)
length(None)           returns 0
length(30)             returns 1 + 0 = 1
length(20 -> 30)       returns 1 + 1 = 2
length(10 -> 20 -> 30) returns 1 + 2 = 3

The calls go down one line at a time, then the answers come back up. That two-way movement is the core of recursion. The going-down part reaches the base case. The coming-back-up part builds the answer.

Here is a complete program that runs the function on a four-node list.

The output is this.

length: 4

Worked example 2: sum and search

The second example adds values, and the third example stops early. Both use the same two-part shape.

Summing follows the length pattern. The base case is None, which adds up to 0. The recursive step adds the value of this node to the sum of the rest. The function is named total here, because sum is a built-in function in Python, and a new function with that name would hide it.

def total(node):
    if node is None:
        return 0
    return node.value + total(node.next)

Searching is different. The function can return early, before it reaches the end of the list. If this node holds the target, the answer is True and no further call is needed. If it does not, the function asks the rest of the list.

def contains(node, target):
    if node is None:
        return False
    if node.value == target:
        return True
    return contains(node.next, target)

Here the base case is different. Reaching None means the value was not found, so the answer is False. The two if lines that come before the recursive call are the checks that can finish early.

Worked example 3: work after the call

The third example is harder because the work happens after the recursive call returns, not before. The function prints the list backwards: the last value first, the first value last.

def print_reverse(node):
    if node is None:
        return
    print_reverse(node.next)
    print(node.value, end=" ")

The line that prints comes after the recursive call. So the function first goes all the way to the end of the list, and only then prints. When the calls return, the printing happens from the last node back to the first. end=" " tells print to put a space after each value instead of a new line.

Here is a complete program that uses this function with the other examples. It prints the sum, the two searches, and the reversed list.

For the list 10 -> 20 -> 30 -> 40, the calls go down to the None at the end. Then the last node prints 40, the one before it prints 30, and so on. The output from a run is this.

sum: 100
contains 30: True
contains 99: False
reverse order: 40 30 20 10 

The trailing space on the last line comes from end=" " in the print call. A recursive function that does its work after the call is a common pattern in list problems, and it is the same mechanism that the reversal in the next example depends on.

Worked example 4: reversing a list recursively

Reversing is the hardest of the four because the list must be rewired, not just read. The idea is this. Suppose the rest of the list, from the second node onward, has already been reversed. Then the first node is now at the end of that reversed rest. It must point back at the first node, and its own next must become None.

Take the list 1 -> 2 -> 3. Here is the function.

def reverse(head):
    if head is None or head.next is None:
        return head
    new_head = reverse(head.next)
    head.next.next = head
    head.next = None
    return new_head

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 reversed is still one node. The recursive step has three lines, and each one has a job.

• new_head = reverse(head.next) reverses the rest. For 1 -> 2 -> 3, the rest is 2 -> 3, and reversing it gives 3 -> 2. The new first node of the rest is 3, which is saved in new_head.
• head.next.next = head makes the node after head point back at head. Here head is 1, and head.next is 2, so node 2 now points at node 1.
• head.next = None cuts the old forward link from node 1 to node 2. Node 1 is now the end of the list.

The function returns new_head, which is 3. Here is the result for the list 1 -> 2 -> 3, printed with show.

print("recursive reverse:", show(reverse(from_values(1, 2, 3))))

The output is this.

recursive reverse: 3 -> 2 -> 1

Notice that the function returns the new head, not the old one. The old head, 1, is now the last node, and it is no longer the way into the list. The caller must use the returned value. Mistakes with this are covered later in the lesson.

The call stack and the recursion limit

Python tracks every function call that has started and not yet finished. It stores this record in a region of memory called the call stack. The name comes from a stack of plates: the last call that started is the first one to finish, like the top plate.

Each call takes one block of memory called a frame. A frame holds the function's parameters, its local variables, and the place to return to when the call finishes. A recursive function that reaches 100,000 levels deep has 100,000 frames on the stack at once.

The stack has a limit on its depth. Check the limit with sys.getrecursionlimit(). The limit is the maximum number of calls that can be unfinished at the same time, and it is set by the interpreter. On the machine used for this lesson, with Python 3.14, the limit was 1000. A call that would go past the limit raises RecursionError. The limit exists to stop endless recursion from crashing Python.

The following program keeps calling a function that never returns. The counter records how many calls happen before the error. The function does nothing else, so this measures only the room for calls.

import sys
 
counter = 0
 
 
def count_forever():
    global counter
    counter += 1
    count_forever()
 
 
print("limit", sys.getrecursionlimit())
try:
    count_forever()
except RecursionError as e:
    print("calls before overflow:", counter)
    print("error:", type(e).__name__)

The try and except lines let the program print a message instead of stopping. The global counter line tells the function to change the counter that is defined outside it. The output from one run was this.

limit 1000
calls before overflow: 999
error: RecursionError

The count is one less than the limit here, because the module's own code also takes a slot on the stack. Your number can be different if the program is run from a different place or with different settings. The point is that the room is limited, and it is small compared with a list that can hold millions of nodes.

Now test the recursive length on lists of different sizes. The probe builds a list of zeros of each size and calls length on it.

for n in (100, 500, 900, 990, 995, 1000, 2000, 5000):
    try:
        print(n, "nodes recursive length:", length(from_values(*([0] * n))))
    except RecursionError:
        print(n, "nodes recursive length: RecursionError")

The output was this.

100 nodes recursive length: 100
500 nodes recursive length: 500
900 nodes recursive length: 900
990 nodes recursive length: 990
995 nodes recursive length: 995
1000 nodes recursive length: RecursionError
2000 nodes recursive length: RecursionError
5000 nodes recursive length: RecursionError

So for this simple function, the limit on this machine lies between 995 and 1000 nodes. The exact number depends on how deep the calls already are when the function starts, so it is not something to rely on. A list of 100,000 nodes is far past it.

big = from_values(*([0] * 100_000))
print("loop length of 100000 nodes:", length_loop(big))
try:
    print("recursive length:", length(big))
except RecursionError as e:
    print("recursive length failed:", type(e).__name__)

The 100_000 uses underscores as digit separators, so it is easy to read. It is the same number as 100000. The loop version, length_loop, comes in the next section. The output was this.

loop length of 100000 nodes: 100000
recursive length failed: RecursionError

A higher limit can be set with sys.setrecursionlimit(n). The help text for the function says the limit exists to stop endless recursion from crashing Python, and that the highest possible value depends on the platform. With the limit raised to 200000, the recursive length returned 100000 for the 100,000-node list on the machine used here. A test with a million nodes and a limit of 1,100,000 also returned 1000000.

import sys
 
sys.setrecursionlimit(200_000)
big = from_values(*([0] * 100_000))
print("recursive length with limit 200000:", length(big))

recursive length with limit 200000: 100000

This moves the limit up, but every call still takes memory, and a higher limit is only safe if you test it on the sizes you expect. A list with unknown size can still fail. The reliable fix is to write the function as a loop.

Python also does not remove the calls at the end of a function. A call that is the last thing a function does is called a tail call. Some languages turn tail calls into loops automatically. Python does not. This function counts down with a tail call, and it fails at 5000 calls:

def tail_countdown(n):
    if n == 0:
        return 0
    return tail_countdown(n - 1)
 
 
print(tail_countdown(5000))

The output ends with this.

  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Converting the recursion to a loop

A loop does not need a frame for each node. It uses a fixed number of variables, and the variables are reused on every step. So a loop can walk a list of any length without growing the call stack.

The length function becomes a loop with one counter and one moving pointer.

def length_loop(node):
    n = 0
    cur = node
    while cur is not None:
        n += 1
        cur = cur.next
    return n

The variable cur plays the role that node played in each call. Each step moves cur to the next node. The step where cur becomes None is the base case, and the loop stops there. The count n is the answer that the recursion built up on the way back.

The reversal needs more care. The recursive version used the call stack to hold the nodes it had passed. The loop must keep track of them itself. It uses three variables.

def reverse_loop(head):
    prev = None
    cur = head
    while cur is not None:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev

Here is what the three variables do for the list 1 -> 2 -> 3. The variable prev starts as None, because the first node will become the end of the list. The variable cur starts at the first node. Each step does four things in order.

start:    prev = None   cur = 1   list 1 -> 2 -> 3
step 1:   nxt = 2; 1.next = None; prev = 1; cur = 2
          list now: 1 -> None, and 2 -> 3 is still ahead
step 2:   nxt = 3; 2.next = 1; prev = 2; cur = 3
          list now: 2 -> 1 -> None, and 3 is still ahead
step 3:   nxt = None; 3.next = 2; prev = 3; cur = None
          list now: 3 -> 2 -> 1 -> None
end:      cur is None, so the loop stops and prev = 3 is returned

The variable nxt is needed because cur.next is changed in the same step. Without it, the link to the rest of the list would be lost. This is the most common loop mistake in list reversal, and the one that is easiest to miss when reading code.

Run both reversal versions on the same list, and the loop version on 100,000 nodes, to see the difference in the output.

print("iterative reverse:", show(reverse_loop(from_values(1, 2, 3, 4, 5))))
big = from_values(*([0] * 100_000))
print("loop length of 100000 nodes:", length_loop(big))

The output is this.

iterative reverse: 5 -> 4 -> 3 -> 2 -> 1
loop length of 100000 nodes: 100000

The loop handles the big list because it never makes a new call for each node.

How to turn a recursion into a loop

There is a simple way to decide whether a recursive function can become a loop. Ask whether the function does any work after the recursive call returns. If not, the loop is a direct walk from the first node, as in length and total. If yes, as in print_reverse, the loop must save the work to do in the right order, or reverse the order of the work. For printing backwards, the easy fix is to store the values in a list and then print them from the end.

def print_reverse_loop(node):
    values = []
    cur = node
    while cur is not None:
        values.append(cur.value)
        cur = cur.next
    for v in reversed(values):
        print(v, end=" ")

The reversal is the third case. The recursion did its work by rewiring nodes on the way back up. The loop does the same rewiring on the way forward, and the three variables hold everything the call stack used to hold.

Common mistakes

Each output shown below is from a real run. The file name and line numbers in a traceback depend on where the code is saved, so your numbers will differ.

Mistake 1: no base case. A function that never reaches its stopping point causes RecursionError. This function recurses on the same node every time, so node never moves to a smaller list.

def length_stuck(node):
    if node is None:
        return 0
    return 1 + length_stuck(node)

The call is length_stuck(node) and not length_stuck(node.next). The input never gets smaller, so the calls never reach the base case. Running it on a two-node list ended with this.

  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

The lines before that repeat the same function and line, which shows that one call started another. The message is the same whatever the list.

Mistake 2: forgetting the None check. A recursive call on node.next is not safe if node itself can be None. The function below checks the value before it checks for None.

def length_no_none_check(node):
    if node.value == -1:
        return 0
    return 1 + length_no_none_check(node.next)

When the recursion reaches the end, node is None, and node.value tries to read an attribute of nothing. The run on a three-node list ended with this.

    if node.value == -1:
       ^^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'value'

The fix is to check for None first, as the base case does. An AttributeError is a different error from RecursionError. The first means an attribute was read from None. The second means the calls never stopped.

Mistake 3: returning the old head in a reversal. The recursive reverse must return new_head, the node that was found at the far end of the list. The buggy version below returns head instead.

def reverse_buggy(head):
    if head is None or head.next is None:
        return head
    new_head = reverse_buggy(head.next)
    head.next.next = head
    head.next = None
    return head

The rewiring is right, but the answer is wrong. The function returns node 1, and node 1 is now the last node, with next set to None. Printing the result from a list of 1 -> 2 -> 3 gave this.

buggy reverse: 1

The caller sees a list with one node. The other two nodes still exist, but nothing the program can reach leads to them, so they are lost to it.

Mistake 4: thinking the last line makes the recursion free. A function that ends with a call to itself is sometimes called tail recursion. Python does not turn it into a loop, as shown in the section on the recursion limit. The length function above also ends with a call to itself, but as part of an addition, so it is not a tail call anyway. Writing return on the recursive call does not change how much of the call stack is used in Python. A loop is the reliable choice for long lists.

Mistake 5: relying on a higher limit. sys.setrecursionlimit can make a list that failed begin to work. It does not change the function. A list large enough can still fail, and the platform sets the highest value you can use. Test the loop version when the list size is not known in advance.

Practice

The answers for each exercise are below its question. The code in these answers was run with the same node class used in this lesson.

Exercise 1. Write a recursive function count_even(node) that returns how many values in the list are even. For the list 4 -> 7 -> 10 -> 3 -> 8 the answer is 3. For None the answer is 0.

Show the answer

def count_even(node):
    if node is None:
        return 0
    here = 1 if node.value % 2 == 0 else 0
    return here + count_even(node.next)

The base case returns 0 for an empty list. The recursive step adds 1 if this value is even, or 0 if it is odd, and then adds the count from the rest. The % operator gives the remainder after division, so value % 2 == 0 is true for even numbers. The conditional expression 1 if ... else 0 is a short way to write a choice between two values. Running the function on the list above returns 3, and on None it returns 0.

Exercise 2. Write a recursive function last(node) that returns the value of the last node. The list is never empty. For the list 4 -> 7 -> 10 -> 3 -> 8 the answer is 8.

Show the answer

def last(node):
    if node.next is None:
        return node.value
    return last(node.next)

This base case is different from the others in the lesson. It stops one node early, at the node whose next is None, because that node holds the answer. Running the function on the list above returns 8.

Exercise 3. Write a recursive function same_values(a, b) that returns True when two lists have the same values in the same order. Two empty lists are the same. A list is not the same as a list that is one node shorter.

Show the answer

def same_values(a, b):
    if a is None or b is None:
        return a is b
    if a.value != b.value:
        return False
    return same_values(a.next, b.next)

The base case handles the case where one or both lists have ended. It returns True only when both have ended, which is the test a is b when both are None. Running it gave True for two lists of 1 -> 2 -> 3, False for 1 -> 2 -> 3 against 1 -> 2, and True for two empty lists.

Exercise 4. Rewrite total as a loop, so that it works on a list of 100,000 nodes without a RecursionError.

Show the answer

def sum_loop(node):
    total = 0
    cur = node
    while cur is not None:
        total += cur.value
        cur = cur.next
    return total

The variable total plays the role of the work that the recursion did on the way back up. The loop adds each value as it walks forward, so the order of additions is different, but the total is the same because addition gives the same answer in any order. For the list 4 -> 7 -> 10 -> 3 -> 8 the result is 32.

Exercise 5. Explain, in your own words, why length_loop cannot cause a RecursionError on a list of any size, while length can.

Show the answer

length makes one new call for every node, and each call takes a frame on the call stack, so a long list needs a deep call stack. length_loop makes no new calls. It uses two variables, n and cur, and reuses them on every step. The call stack stays the same depth however long the list is. The only thing that grows is the time the loop takes, which is one step per node.

Summary

• Recursion solves a list problem by calling itself on the rest of the list. Every recursive function needs a base case that stops the calls.
• Each call uses a frame on the call stack. Python caps the depth with the recursion limit, so a long list can exceed it.
• Some recursive functions do their work before the call and some after. The functions that do work after the call need more care when turned into loops.
• Reversing a list recursively needs the new head to be returned, not the old one.
• A loop with a fixed number of variables handles a list of any length, and sys.setrecursionlimit only raises the cap.