Overview

A recursive function calls itself on a smaller input until it reaches a case simple enough to answer directly. Writing one well comes down to a single act of trust: assume the call on the smaller input already works, and only worry about combining its result with the current step. Programmers call this the "leap of faith".

Recursion is not just a coding style — it is how trees, graphs, backtracking and dynamic programming are naturally expressed. The cost model is the recursion tree: the total work is the sum over every call, and the extra space is the depth of the call stack.

Key concepts

Tick a concept once you can explain it in your own words without notes.

Complexity cheat sheet

OperationCost
Linear recursion (factorial, list sum)O(n) time, O(n) stack
Halving recursion (fast power)O(log n)
Merge sortO(n log n)
Naive FibonacciO(2ⁿ) — O(n) with memoisation

Patterns to recognise

Leap of faith

Use it for: Any problem defined in terms of smaller versions of itself.

Define what f(n) returns, handle the base case, express f(n) using f(smaller).

Halve the input

Use it for: Powers, binary search, divide and conquer.

Recurse on half the problem and combine in O(1) or O(n).

Recurse on choices

Use it for: Generating combinations, expression evaluation.

Each call branches on a decision; this grows into backtracking later in the roadmap.

Code template

Fast exponentiation — x to the power n in O(log n)
def power(x, n):
    if n == 0:
        return 1.0
    if n < 0:
        return 1 / power(x, -n)
    half = power(x, n // 2)          # trust the smaller call
    return half * half if n % 2 == 0 else half * half * x

Common mistakes

  • A missing or unreachable base case causes infinite recursion and a stack overflow.
  • Calling the function twice on the same input (power(x, n/2) * power(x, n/2)) silently makes the algorithm exponential.
  • Negating INT_MIN overflows in C++/Java — widen to long long first.
  • Shared mutable state (a global list) must be restored after each call, or results leak between branches.

Quick check

Three questions on Recursion. Get all three right to earn +15 XP.

  1. What happens when a recursive function has no base case?

  2. Naive recursive Fibonacci, fib(n) = fib(n-1) + fib(n-2), runs in roughly:

  3. How much extra memory does a recursion of depth d use, beyond its variables?

Challenges

Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.

Stuck on Recursion?Ask Orbi for a hint, a fresh explanation or a review of your code.

Ask the tutor