Recursion Cheat Sheet

Explains recursive function structure, base and recursive cases, the call stack, memoization, and recursion versus iteration tradeoffs.

1 PageBeginnerMar 25, 2026

Anatomy of a Recursive Function

Every recursive function needs a base case and a recursive case.

python

def factorial(n):    if n <= 1:                    # base case: stops the recursion        return 1    return n * factorial(n - 1)   # recursive casefactorial(5)   # => 120

Fibonacci & Tree Traversal

Naive vs memoized recursion, and recursive tree traversal.

python

# Naive recursive Fibonacci: O(2^n)def fib(n):    if n <= 1:        return n    return fib(n - 1) + fib(n - 2)# Memoized Fibonacci: O(n)def fib_memo(n, memo={}):    if n in memo:        return memo[n]    if n <= 1:        return n    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)    return memo[n]# Recursive in-order binary tree traversaldef inorder(node, result=None):    if result is None:        result = []    if node is None:        return result    inorder(node.left, result)    result.append(node.value)    inorder(node.right, result)    return result

Key Concepts

Core vocabulary for reasoning about recursive functions.

Base case- The condition that stops recursion; every recursive function must have at least one to avoid infinite recursion
Recursive case- The part of the function that calls itself with a smaller or simpler input, progressing toward the base case
Call stack- Each recursive call pushes a new stack frame; deep recursion can exhaust it and cause a stack overflow
Tail recursion- A recursive call that is the last operation in the function; some languages optimize it into a loop (Python does not)
Memoization- Caching results of expensive recursive calls by argument to avoid redundant recomputation
Divide and conquer- A recursion pattern that splits a problem into subproblems, solves them recursively, and combines results, e.g. merge sort

Recursion vs Iteration

The same logic expressed both ways.

python

# Recursive sumdef sum_recursive(arr):    if not arr:        return 0    return arr[0] + sum_recursive(arr[1:])# Iterative equivalent (no call-stack growth)def sum_iterative(arr):    total = 0    for x in arr:        total += x    return total

Pro Tip

Python has no tail-call optimization and a default recursion limit (around 1000 frames) — convert deep or hot-path recursion to an explicit loop rather than relying on sys.setrecursionlimit().

Was this cheat sheet helpful?

Data Structures Cheat Sheet

Sorting Algorithms Cheat Sheet

Explore Topics

#Recursion#RecursionCheatSheet#Programming#Beginner#AnatomyOfARecursiveFunction#FibonacciTreeTraversal#KeyConcepts#RecursionVsIteration#Functions#DataStructures#Algorithms#CheatSheet#SkillVeris

Sri Hayavadhana Info-Tech

Professional Web Designing Services