Recursion Framework: Base Case, Trust, Build
Apply the three-step method to write correct recursive solutions for factorial, power, and sum-of-digits without tracing every call.
Why Recursion Feels Difficult
Most beginners try to trace every recursive call mentally, which quickly becomes overwhelming for even five-level deep recursion. The professional approach is to use a three-step framework — Base Case, Trust, Build — that lets you write correct recursive functions without mentally simulating the entire call tree.
The framework is sometimes called the leap of faith: you trust that your function works on smaller inputs and use that assumption to build the solution for larger inputs.
Step 1: Define the Base Case
The base case is the simplest input for which the answer is known without further recursion. Every recursive function must have at least one base case; without it the function recurses forever (stack overflow). Good base cases are: empty list, single element, n == 0, n == 1, or the problem reduces to a trivial identity.
Write the base case first, before any recursive logic. Identify it by asking: 'What is the smallest version of this problem I can answer immediately?'
# Base cases for common problems
def factorial(n):
if n == 0: # base case: 0! = 1
return 1
# ... recursive step below
def sum_list(lst):
if not lst: # base case: sum of empty list is 0
return 0
# ...
def height(node):
if node is None: # base case: height of null node is 0
return 0
# ...
print('Base cases identified')All lessons in this course
- Recursion Framework: Base Case, Trust, Build
- Visualising the Call Stack
- Recursive vs Iterative Trade-offs
- Memoisation: Caching Recursive Results