Recursion

Introduction

Recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem.

All recursive functions contain two parts:

1. A base case (or cases), which defines when the recursion is stopped - otherwise it will go on forever!
2. Breaking down the problem into smaller subproblems and invoking the recursive call.

One of the most common examples of recursion is the Fibonacci sequence:

• Base cases: fib(0) = 0 and fib(1) = 1
• Recurrence relation: fib(i) = fib(i-1) + fib(i-2)

def fib(n):
  if n <= 1:
    return n
  return fib(n - 1) + fib(n - 2)

Many algorithms relevant in coding interviews make heavy use of recursion, such as:

• Binary search
• Merge sort
• Tree traversal
• Depth-first search (DFS)

This document focuses on questions that use recursion but aren’t part of other well-known algorithms.

Learning resources

Readings

• Recursion, University of Utah

Videos

• Tail Recursion, University of Washington

Things to look out for during interviews

1. Always define a base case so that your recursion will end.
2. Recursion is useful for generating permutations, combinations, and solving tree-based questions. You should know how to:
   • Generate all permutations of a sequence.
   • Handle duplicates effectively.
3. Recursion implicitly uses a stack. All recursive approaches can be rewritten iteratively using a stack. Be cautious of cases where the recursion level goes too deep and causes a stack overflow (the default limit in Python is 1000). You may get bonus points for pointing this out to the interviewer.
4. Recursion will never be O(1) space complexity because a stack is involved unless there is tail-call optimization (TCO). Find out if your chosen language supports TCO.
5. Number of base cases:
   • In the Fibonacci example above, note that fib(n - 2) is invoked, so 2 base cases are defined to cover all possible invocations.
   • If your recursive function only invokes fn(n - 1), then 1 base case is sufficient.

Corner cases

• n = 0
• n = 1
• Ensure you have enough base cases to cover all possible invocations of the recursive function.

Techniques

Memoization

In some cases, you may be computing the result for previously computed inputs. For example, in the Fibonacci function:

fib(5) calls fib(4) and fib(3)
fib(4) calls fib(3) and fib(2)

Here, fib(3) is being called twice!

If the value for fib(3) is memoized and reused, it greatly improves the efficiency of the algorithm. The time complexity becomes O(n).

Example with memoization:

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]