Complete Guide to Recursion in Python

Recursion is a technique where a function calls itself to solve a smaller version of the same problem. It is a core concept in algorithms, data structures, and problem solving.

In this chapter you will learn

• What recursion is and why it is useful
• Base case vs recursive case
• Classic examples (factorial, Fibonacci, countdown)
• Recursion in trees, graphs, and sorting algorithms
• Common mistakes & how to design recursive solutions

1. What Is Recursion?

Recursion happens when a function calls itself to solve a smaller part of a problem.

A recursive function must have:

• A base case: when to stop calling itself
• A recursive case: how it calls itself with a smaller input

2. Why Is Recursion Useful?

Recursion is especially useful for problems with:

• Self-similar structure (problem contains smaller versions of itself)
• Hierarchical data (trees, graphs, nested folders)
• Divide & conquer algorithms

Real-life analogies:

• Russian nesting dolls
• Family trees
• Folder → subfolder → sub-subfolder structures

3. Basic Recursion Example: Countdown

This function prints a countdown from n to 1, then prints "Done!". It uses recursion to reduce the problem size with each call.

Output for countdown(5):

4. Factorial Using Recursion

Factorial is defined as:

Recursive definition

We can define factorial recursively as:

• n! = n × (n-1)! for n > 1
• 1! = 1 is the base case

def factorial(n):
    if n == 1:              # Base case
        return 1
    return n * factorial(n - 1)   # Recursive case

How factorial(5) works

Each call reduces n by 1 until it reaches the base case:

Step-by-step evaluation

5. Fibonacci Using Recursion

The Fibonacci sequence is defined as:

def fib(n):
    if n <= 1:              # Base cases
        return n
    return fib(n - 1) + fib(n - 2)  # Recursive case

Call tree for fib(4)

This version is simple but inefficient for large n because it recomputes many values. (You typically optimize it with memoization or iteration.)

6. Recursion vs Iteration

Many recursive algorithms can also be written using loops.

7. Tail Recursion & Recursion Limits

Tail recursion is a special case where the recursive call is the last operation in the function. Some languages optimize tail calls to avoid growing the call stack.

7.1 Tail Recursion

A function is tail recursive if the recursive call is the last operation in the function.

def factorial_tail(n, acc=1):
    if n == 1:
        return acc
    return factorial_tail(n - 1, acc * n)

In some languages, tail recursion is optimized to avoid extra stack frames. Python does NOT perform tail recursion optimization, so deep recursion can still overflow.

7.2 Python Recursion Limit

import sys
print(sys.getrecursionlimit())  # often 1000 by default

You can increase this limit, but it is risky:

import sys
sys.setrecursionlimit(5000)  # Use with caution!

Deep recursion can lead to crashes. For very deep problems, consider iterative solutions or using data structures like stacks.

Always ensure your recursive functions have proper base cases to prevent infinite recursion.

Test code here: (It will show that the code is valid but no output will be displayed)

8. Recursion in Trees & Graphs

Recursion is a natural fit for traversing hierarchical data structures like trees and graphs.

8.1 In-Order Traversal of a Binary Tree

In-order traversal visits the left subtree, the node, then the right subtree:

def inorder(node):
    if not node:
        return
    inorder(node.left)
    print(node.value)
    inorder(node.right)

8.2 Depth-First Search (DFS) in a Graph

DFS explores as far as possible along each branch before backtracking:

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    if node in visited:
        return
    visited.add(node)
    print(node)

    for neighbor in graph[node]:
        dfs(graph, neighbor, visited)

9. Recursion in Sorting Algorithms

Many efficient sorting algorithms use recursion to divide and conquer the problem.

9.1 Merge Sort (Divide & Conquer)

Merge sort divides the array into halves, sorts each half recursively, then merges them:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    # merge two sorted halves
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

9.2 Quick Sort

Quick sort selects a pivot, partitions the array, then sorts the partitions recursively:

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[0]
    left  = [x for x in arr[1:] if x < pivot]
    right = [x for x in arr[1:] if x >= pivot]

    return quick_sort(left) + [pivot] + quick_sort(right)

10. Common Mistakes in Recursion

Common pitfalls when writing recursive functions include:

• No base case → leads to infinite recursion
• Base case never reached → wrong condition or wrong decrement
• Problem not reduced correctly in recursive step
• Missing return statements (forgetting to return recursive results)
• Too many repeated subcalls (like naive Fibonacci) → exponential time

11. How to Design a Recursive Solution

For any recursive problem, follow this pattern:

1. Define the problem in terms of smaller subproblems.
2. Identify the base case (smallest, simplest input).
3. Write the recursive case that reduces the input.
4. Ensure progress toward the base case every call.

General template:

def solve(problem):
    # 1. Base case
    if is_simple(problem):
        return simple_answer(problem)

    # 2. Reduce the problem
    subproblem = make_smaller(problem)

    # 3. Recursive call
    subresult = solve(subproblem)

    # 4. Combine result
    return combine(problem, subresult)

12. Classic Problems Using Recursion

Here are some common recursive exercises to practice your skills:

12.1 Common Recursive Exercises

• Reverse a string recursively
• Sum of elements in a list
• Count digits of a number
• Power function pow(x, n)
• Generate all subsets of a set
• Generate all permutations of a string/list
• Flatten a nested list
• Binary tree traversals (pre/in/post order)

These problems are very common in interviews and are great practice for mastering recursion.

13. Summary

In this guide, you learned:

• What recursion is and how it works
• The importance of base cases and problem reduction
• How to implement classic recursive functions (factorial, Fibonacci, countdown)
• How recursion is used in trees, graphs, and sorting algorithms
• Common recursion pitfalls and how to avoid them
• A general pattern you can apply to almost any recursive problem

Recursion is a powerful tool in your programming toolbox. With practice, it becomes an intuitive way to think about complex, structured problems.