On this page

Recursion in Python: A Functional Approach

Published on July 3, 2026

Enrico Hochkoeppler Profile

By Enrico Hochkoeppler

Web Developer & TutoriaLibre Founder

Recursion is the fundamental iteration mechanism of functional programming. Where imperative code uses loops with mutable counters and accumulators, functional code expresses repetition through functions that call themselves. A recursive function solves a problem by breaking it into smaller instances of the same problem, then combining the results — with no mutable state, no side effects, and no explicit iteration. Python fully supports recursion, including tail recursion (though without automatic optimization), and recursive patterns are essential for traversing trees, processing nested data structures, and implementing divide‑and‑conquer algorithms. This lesson teaches you how to write pure recursive functions in Python, understand the call stack, optimize with tail recursion and memoization, and recognise when recursion is the right tool for the job.


What Is Recursion?​

A recursive function is a function that calls itself. This simple idea is one of the most powerful concepts in programming because it allows you to express complex, repetitive operations in a clean, declarative way.

Consider the problem of summing all numbers in a list. An imperative solution uses a loop and a mutable accumulator:


def sum_list_imperative(numbers):

    total = 0

    for n in numbers:

        total += n

    return total

A recursive solution expresses the same operation without any mutable state:


def sum_list_recursive(numbers):

    if not numbers:

        return 0

    return numbers[0] + sum_list_recursive(numbers[1:])

This function embodies the essence of recursion: it handles the smallest possible case first (an empty list returns 0), then combines the first element with the result of recursively processing the rest.

The Two Essential Parts of Every Recursive Function​

Every correct recursive function consists of two parts:

1. The Base Case

The base case is the condition that stops the recursion. It is the simplest possible version of the problem, one that can be solved directly without further recursive calls. Without a base case, the function would call itself indefinitely, eventually raising a RecursionError.

In sum_list_recursive, the base case is if not numbers: return 0. An empty list has a sum of zero, and there is no smaller list to process.

2. The Recursive Case

The recursive case is where the function calls itself with a smaller or simpler version of the input. The key insight is that the function must make progress toward the base case with each call.

In sum_list_recursive, the recursive case is numbers[0] + sum_list_recursive(numbers[1:]). Each call processes a smaller list, moving inexorably toward the empty list.


How Python Handles Recursive Calls​

When a function calls itself, Python does not simply replace the current call. Instead, it stacks each call on the call stack — a data structure that tracks the execution state of every active function.


def factorial(n):

    if n <= 1:

        return 1

    return n * factorial(n - 1)



factorial(4)

When factorial(4) executes, the call stack grows as follows:


factorial(4)

│

├── 4 * factorial(3)

│   │

│   ├── 3 * factorial(2)

│   │   │

│   │   ├── 2 * factorial(1)

│   │   │   │

│   │   │   └── returns 1 (base case)

│   │   │

│   │   └── 2 * 1 = 2

│   │

│   └── 3 * 2 = 6

│

└── 4 * 6 = 24

Each call waits for the call below it to return a value. Once the base case is reached, the stack unwinds — each waiting call receives its result and completes.

The Problem with Deep Recursion​

Because each recursive call consumes stack space, very deep recursion can exceed Python's recursion limit. The default limit is 1000, meaning a recursive function that calls itself more than 1000 times will raise a RecursionError.


def infinite_recursion():

    return infinite_recursion()



infinite_recursion()  # RecursionError: maximum recursion depth exceeded

You can check and modify the recursion limit:


import sys

print(sys.getrecursionlimit())  # 1000

sys.setrecursionlimit(2000)

However, increasing the limit is rarely the right solution. Deep recursion often indicates that an iterative approach or a different algorithm would be more appropriate.


Recursion and Purity​

In functional programming, recursive functions must be pure — deterministic, side‑effect‑free, and referentially transparent. The recursive case should not modify any external state.

Pure recursive function:


def factorial_pure(n: int) -> int:

    if n <= 1:

        return 1

    return n * factorial_pure(n - 1)

This function is pure because it:

Impure recursive function:


counter = 0



def factorial_impure(n: int) -> int:

    global counter

    counter += 1  # Side effect

    if n <= 1:

        return 1

    return n * factorial_impure(n - 1)

The impure version modifies a global variable with each call, making it harder to reason about, test, and debug.


Common Recursive Patterns​

1. Processing Lists Recursively​

The list is the fundamental data structure in functional programming, and recursion is the natural way to process it.


def sum_list(nums):

    if not nums:

        return 0

    return nums[0] + sum_list(nums[1:])



def product_list(nums):

    if not nums:

        return 1

    return nums[0] * product_list(nums[1:])



def max_list(nums):

    if len(nums) == 1:

        return nums[0]

    return max(nums[0], max_list(nums[1:]))

Each function processes the first element, then recurses on the remainder of the list. The base case is the empty list or a single‑element list.

2. Tree Traversal​

Recursion is the natural way to traverse tree‑shaped data structures.


class Node:

    def __init__(self, value, left=None, right=None):

        self.value = value

        self.left = left

        self.right = right



def sum_tree(node):

    if node is None:

        return 0

    return node.value + sum_tree(node.left) + sum_tree(node.right)

This function computes the sum of all values in a binary tree. It sums the current node's value and recursively sums its left and right subtrees.

3. The Fibonacci Sequence​

The Fibonacci sequence is a classic example of recursion:


def fibonacci(n):

    if n <= 1:

        return n

    return fibonacci(n - 1) + fibonacci(n - 2)

However, this naive implementation is extremely inefficient because it repeatedly computes the same values. The time complexity is exponential, O(2^n).

Memoization solves this problem by caching results:


from functools import lru_cache



@lru_cache(maxsize=None)

def fibonacci_memo(n):

    if n <= 1:

        return n

    return fibonacci_memo(n - 1) + fibonacci_memo(n - 2)

With @lru_cache, each value is computed only once, reducing time complexity to O(n).


Tail Recursion​

Tail recursion occurs when the recursive call is the very last operation performed by the function. In a tail‑recursive function, there is no additional computation after the recursive call returns.

Non‑tail‑recursive (the recursive call is followed by multiplication):


def factorial_non_tail(n):

    if n <= 1:

        return 1

    return n * factorial_non_tail(n - 1)

Tail‑recursive (the recursive call is the last operation):


def factorial_tail(n, accumulator=1):

    if n <= 1:

        return accumulator

    return factorial_tail(n - 1, n * accumulator)

In factorial_tail, the multiplication happens before the recursive call, and nothing is left to do after it returns. The result is passed forward through the accumulator parameter.

Why Tail Recursion Matters​

In languages that support tail call optimization (TCO), the compiler or interpreter can transform a tail‑recursive function into a loop, reusing the same stack frame for each call instead of growing the call stack. This eliminates the risk of stack overflow and makes tail‑recursive functions as efficient as loops.

Python does not implement tail call optimization. The language designers have intentionally chosen not to add TCO because they believe it complicates debugging and stack traces. Nevertheless, writing tail‑recursive functions is still valuable because it demonstrates an understanding of the concept and improves code clarity.


Recursion vs. Iteration​

Most problems that can be solved recursively can also be solved iteratively with loops. The choice between recursion and iteration depends on the problem and the context.

AspectRecursionIterationStateNo mutable stateRequires mutable state (loop counters, accumulators)ReadabilityOften more natural for tree‑shaped problemsMore natural for sequential problemsPerformanceFunction call overheadGenerally fasterStack usageGrows with recursion depthConstant stack usageRiskStack overflow with deep recursionNo stack overflow risk

When to Use Recursion​

Recursion is particularly well‑suited for:

When to Use Iteration​

Iteration is often a better choice when:


Common Pitfalls and How to Avoid Them​

1. Forgetting the Base Case​

The most common recursion mistake is forgetting to define a base case or defining one that is never reached.


def countdown(n):

    print(n)

    return countdown(n - 1)  # No base case

This function will run until Python raises a RecursionError.

2. Not Making Progress Toward the Base Case​

Each recursive call must move closer to the base case. If it does not, the recursion will never terminate.


def bad_recursion(n):

    if n <= 1:

        return 1

    return bad_recursion(n)  # Same value — no progress

3. Excessive Recursion Depth​

Even with a correct base case, recursion can be too deep. If you are processing a list with thousands of elements, consider using iteration instead.

4. Unnecessary Side Effects​

In functional programming, recursive functions should be pure. Avoid modifying global state or printing inside recursive functions unless absolutely necessary.


Practical Example: A Recursive File System Traversal​

A practical use of recursion is traversing a file system:


import os



def list_files(directory, indent=0):

    for item in os.listdir(directory):

        path = os.path.join(directory, item)

        if os.path.isdir(path):

            print("  " * indent + f"[DIR] {item}")

            list_files(path, indent + 1)

        else:

            print("  " * indent + f"[FILE] {item}")

This function prints the contents of a directory, recursively descending into subdirectories. It is pure in the sense that it only produces output — it does not modify any external state beyond printing.


Summary​

Recursion is the functional programmer's loop. It allows you to express repetition without mutable state, side effects, or explicit iteration. This lesson has covered:

Recursion is an essential tool for functional programming in Python. Mastering it allows you to write code that is declarative, expressive, and free of the accidental complexity that mutable state introduces. As you continue through this module, you will see recursion applied in increasingly sophisticated ways — from processing complex data structures to implementing higher‑order functions and decorators.

Found this helpful? Share the knowledge...

... or support this project to keep it alive!

Buy Me a Coffee

Previous

Paradigm Shift

Next

Structural Pattern Matching