Interview Cheat Sheets | Recursion Cheat Sheet

December 30th, 2023

Introduction

This article will serve to further summarize the excellent overview of recursion from the tech interview handbook.

Overview:

  • Recursion involves solving a computational problem by breaking it into smaller instances with defined base cases.

All recursive functions contain two parts:

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

Common Example:

  • The Fibonacci sequence is a classic example of recursion with base cases and a recurrence relation.
function fib(n: number): number {
  if (n <= 1) {
    return n;
  }

  return fib(n - 1) + fib(n - 2);
}

Interview Tips:

  • Emphasize the importance of defining a base case to terminate recursion.
  • Highlight recursion’s utility for permutations and tree-based questions.
  • Address stack-related considerations and potential stack overflow issues.
  • Discuss the benefits of rewriting recursive approaches iteratively.
  • Consider tail-call optimization and its impact on space complexity.

Corner Cases:

  • Consider special cases such as n = 0 and n = 1 in recursive functions.
  • Ensure an adequate number of base cases to cover all possible recursive function invocations.

Techniques:

  • Memoization is a technique that can be used to optimize recursion by storing previously computed results.

Essential Questions:

  • Generate Parentheses
  • Combinations
  • Subsets
  • Letter Combinations of a Phone Number
  • Subsets II
  • Permutations - My solution
  • Sudoku Solver