Python Recursion

Satellite · Functions

Recursion

Recursion solves problems that reference smaller subproblems—just remember your base cases and limits.

See templatesMonitor depth

Template

def factorial(n: int) -> int:
    if n <= 1:         # base case
        return 1
    return n * factorial(n - 1)  # recursive step

• Always define a base case to terminate recursion.
• Reduce the problem space each call.

Common use cases

• Tree/graph traversal
• Divide-and-conquer algorithms (merge sort, quicksort)
• Backtracking (combinatorial problems)

Recursion limit

import sys
sys.getrecursionlimit()      # default ~1000
sys.setrecursionlimit(2000)  # adjust cautiously

Use iteration or explicit stacks if you risk deep recursion.

Next up in your learning path

Functions pillar

See recursion in the context of all function tools.

Companion

Type hints

Document recursive function signatures.

Advanced

Loop alternatives

Decide when iteration is clearer.

Comparison