Recursion

Recursion

Recursion is a programming technique where functions solve problems by calling themselves with simpler inputs until reaching a base case. Imagine a set of nested boxes: to open the largest box, you must open each smaller box inside it until you reach the innermost one—just as recursive solutions break complex problems into smaller, self-similar ones.

Think of organizing a library: to sort all books, you sort each shelf; to sort a shelf, you sort each section—using the same sorting principle at every level.

Recursion Structure

graph TD
    A[Complex Problem] --> B{Base Case?}
    B -->|Yes| C[Direct Solution]
    B -->|No| D[Break Into Smaller Problem]
    D --> E[Recursive Call]
    E --> F[Combine Results]
    F --> G[Return Solution]

    style A fill:#ffcdd2
    style C fill:#c8e6c9
    style D fill:#e3f2fd
    style F fill:#fff3e0

Core Components

• Base Case: The simplest version of the problem with a direct solution—the stopping point
• Recursive Case: Express the problem in terms of a smaller identical problem
• Progress: Each recursive call must move closer to the base case to ensure termination

Classic Recursive Examples and Their Complexity

Below are several classic applications of recursion, including computing the factorial of a number and performing in-order traversal of a binary tree. For each example, the associated time and space complexity characteristics are provided to facilitate understanding of both computational efficiency and the effects of recursion on the call stack.

Factorial Calculation

• Time Complexity: O(n)
• Space Complexity: O(n) (due to call stack; each call is stacked until n==1)

In-Order Tree Traversal

• Time Complexity: O(n), where n is the number of nodes in the tree
• Space Complexity: O(h), where h is the height of the tree (depth of recursion stack, best case O(log n) for balanced trees, worst case O(n) for skewed trees)

JavaKotlinTypeScriptDartSwiftPython

// Factorial
public static long factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

// Tree traversal (in-order)
public static void inOrder(TreeNode root) {
    if (root == null) return;
    inOrder(root.left);
    System.out.print(root.val + " ");
    inOrder(root.right);
}

// Factorial
fun factorial(n: Int): Long {
    if (n <= 1) return 1
    return n * factorial(n - 1)
}

// Tree traversal (in-order)
fun inOrder(root: TreeNode?) {
    if (root == null) return
    inOrder(root.left)
    print("${root.value} ")
    inOrder(root.right)
}

// Factorial
function factorial(n: number): number {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

// Tree traversal (in-order)
function inOrder(root: TreeNode | null): void {
    if (root === null) return;
    inOrder(root.left);
    process.stdout.write(root.val + " ");
    inOrder(root.right);
}

// Factorial
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

// Tree traversal (in-order)
void inOrder(TreeNode? root) {
    if (root == null) return;
    inOrder(root.left);
    stdout.write('${root.val} ');
    inOrder(root.right);
}

// Factorial
func factorial(_ n: Int) -> Int {
    if n <= 1 { return 1 }
    return n * factorial(n - 1)
}

// Tree traversal (in-order)
func inOrder(_ root: TreeNode?) {
    guard let root = root else { return }
    inOrder(root.left)
    print(root.val, terminator: " ")
    inOrder(root.right)
}

# Factorial
def factorial(n: int) -> int:
    if n <= 1:
        return 1
    return n * factorial(n - 1)

# Tree traversal (in-order)
def in_order(root: TreeNode | None) -> None:
    if root is None:
        return
    in_order(root.left)
    print(root.val, end=" ")
    in_order(root.right)

Applications

• Tree & Graph Operations: Natural fit for hierarchical structures—in-order, pre-order, post-order traversals, DFS
• Divide and Conquer: Break problems into halves—merge sort, quick sort, binary search
• Mathematical: Number theory algorithms—GCD, factorial, Fibonacci sequences