Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Solving a problem by calling the same idea on a smaller version

Recursion uses the call stack to go deeper, reach a base case, and return

Functions taught you how to package reusable logic. Recursion takes the next step: a function can call itself on a smaller version of the same problem until a stopping rule is reached.

Core Explanation

Every recursive function needs two ingredients:

  1. a base case that stops the process

  2. a recursive step that moves to a smaller or simpler version of the problem

Why this belongs before graph DFS

DFS often feels natural recursively because each unfinished path behaves like a stack frame. Learning recursion first makes the DFS notebook easier to read.

Stack Trace Intuition

The call stack grows while recursion goes deeper and shrinks after the base case is reached.

What to notice

  • the going inside lines appear while the stack is growing

  • the base case appears at the deepest point

  • the closing stack lines appear while the calls return upward

Recursive Permutations of ABC

Backtracking is a recursive pattern where you make a choice, go deeper, and then return to try another choice.

Expected result

The final list contains all six permutations of ABC:

['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']

Guided Practice

What is the main purpose of a base case in recursion?

To stop the recursive calls from continuing foreverCorrect. The base case is the stopping rule that lets the stack start returning.
To make the function run faster than every loopRecursion is not automatically faster. The base case is about stopping correctly.
To remove the need for functionsRecursion still uses functions heavily.

Why is the permutations example a form of backtracking?

Because it sorts the string alphabetically every timeThe key idea is trying choices and then returning, not sorting.
Because it chooses one letter, goes deeper, then returns to try another letterCorrect. That choose, explore, and return rhythm is classic backtracking.
Because recursion can only work on stringsRecursion works on many kinds of problems.

Key Takeaway

Recursion is a way to express repeated structure by calling the same idea on a smaller case. Once you can read the stack growth, base case, and unwind, recursive DFS becomes much easier to understand.

Programming for Machine Learning and Business
Functions and Modular Programming
Programming for Machine Learning and Business
Modules Packages and Dependency Management