DSA · Lesson 6 of 9

Recursion & backtracking

Functions that call themselves, base cases, memoisation and generating combinations.

A recursive function solves a problem by calling itself on a smaller version of it. Every recursive function needs:

a base case that returns without recursing, and
a recursive case that moves towards the base case.

Repeated sub-problems (like Fibonacci) explode exponentially — cache results with memoisation (functools.lru_cache) to make them linear. This is the start of dynamic programming.

Backtracking builds a solution step by step, undoing a choice (“backtracking”) when it can't lead to an answer — used for subsets, permutations and puzzles.

Try it yourself

Code editor

Press Run to see the output.

Edit and press Run (or Ctrl/⌘ + Enter). Python runs in your browser — the first run downloads the Python engine and takes a few seconds.

Key points

Always define the base case first.
Memoise overlapping sub-problems.
Backtracking = choose, explore, un-choose.

Quick check

What happens if a recursive function has no reachable base case?

It returns None It runs forever until a recursion limit/stack overflow Python fixes it automatically It becomes a loop

Practice task

Write permutations(s) that returns every ordering of the letters in a short string such as "abc".

Interview corner

Recursion vs iteration?

Recursion is often clearer for trees and divide-and-conquer but uses call-stack memory; iteration avoids stack limits. Most recursion can be rewritten with an explicit stack.

What is memoisation?

Caching the results of function calls by their arguments so repeated sub-problems are computed once — top-down dynamic programming.