Abdu's Garden

Recursion

2 min read

Trust the natural recursion…

Intro

Recursion is a method of solving problems starting from the base case(s), the smallest instances of the problem. This is often done by calling the procedure/function over and over until the base case is reached and the final (but also the most atomic) solution is returned and it all cascades up like a row of dominoes. It’s the opposite of an Iterative solution, where you start from the beginning and iterate till the end.

All recursive problems have two parts:

  1. The base-case(s): this is where the recursion stops and a result is returned the triggers the chain reaction.
  2. The recursive step: this is often a condition or circumstance that breaks the problem into a smaller segment and makes a recursive call.

Common examples

The most common example of Recursion is the FibonacciSequence

  • Base case: fib(0)=0 and fib(1)=1
  • Recursive step: fib(i) = fib(i-1) + fib(i-2)
def fib(n):
	if n <= 1:
		return n
	return fib(n-1) + fib(n-2)

Notice how the result of the same step can be computed more than once because of fib(n-1) + fib(n-2) ? This can be improved using Memoization where the result of a step such as fib(3) is memoized instead of computed again, this improves efficiency and makes time complexity O(n). To do this, computed solutions are stored in a cache. There are different types of memoization, but it all ties into DynamicProgramming, more.

Others include:

Lookout for

  1. Always define your base case first, and be vigilant if there’s more than one.
  2. Recursion is great for generating permutations, generates all combinations in tree-based questions. // Know how to generate all the permutations of a sequence
  3. Recursion is implicitly a stack so they can be solved iteratively using them, but beware of stack overflow…
  4. Recursion is NEVER O(1) space complexity because of the stack.

Corner cases

  • n=0
  • n=1 Try thinking of all possible base cases to cover every invocation possible, as best as you can.

Essential questions

Solve these basics on LeetCode.

  • Generate Parentheses
  • Combinations
  • Subsets

Recommended practice questions

Try these after you’re done with the essentials.

  • Letter Combinations of a Phone Number
  • Subsets II
  • Permutations
  • Sudoku Solver
  • Strobogrammatic Number II (LeetCode Premium)

Graph View

Backlinks