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.
Recursion Framework: Base Case, Trust, Build is a free DSA Interview Prep lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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')Step 2: Trust the Recursive Call
The trust step is the leap of faith: assume your function already works correctly for any input strictly smaller than the current one. You do not need to prove it for every smaller input right now — the inductive proof guarantees it. Simply call your function on the smaller sub-problem and trust it returns the correct result.
This is the step beginners skip, trying to mentally simulate instead. Resist that urge; it scales to arbitrarily deep recursion once you internalise the framework.
# Trust example: sum_list([3, 1, 4, 1, 5])
# Trust: sum_list([1, 4, 1, 5]) = 11 (we TRUST this, don't trace it)
# Build: 3 + 11 = 14
# So:
def sum_list(lst):
if not lst:
return 0
# Trust that sum_list(lst[1:]) returns sum of the rest
return lst[0] + sum_list(lst[1:])
print(sum_list([3, 1, 4, 1, 5])) # 14Step 3: Build the Solution
The build step combines the trusted sub-problem result with the contribution of the current element to produce the answer for the full input. This is usually a single line: apply an operation to the current element and the result of the recursive call. Common builds: add to sum, prepend to list, increment count, combine two sub-results.
def factorial(n):
if n == 0:
return 1
# Trust: factorial(n-1) gives (n-1)!
# Build: n * (n-1)! = n!
return n * factorial(n - 1)
def power(base, exp):
if exp == 0:
return 1
# Trust: power(base, exp-1) gives base^(exp-1)
# Build: base * base^(exp-1) = base^exp
return base * power(base, exp - 1)
print(factorial(6)) # 720
print(power(2, 10)) # 1024Applying the Framework to Sum of Digits
Problem: compute the sum of digits of a non-negative integer. Base case: n == 0 → sum is 0 (or n < 10 → n itself). Trust: sumDigits(n // 10) returns the sum of all digits except the last. Build: add the last digit n % 10 to the trusted result. The framework produces the solution in three declarative steps.
def sumDigits(n):
if n < 10:
return n # base case: single digit
# Trust: sumDigits(n // 10) gives sum of all digits except last
# Build: add the last digit
return n % 10 + sumDigits(n // 10)
print(sumDigits(0)) # 0
print(sumDigits(7)) # 7
print(sumDigits(123)) # 6
print(sumDigits(9999)) # 36Fibonacci: Two Sub-Problems
Fibonacci requires two recursive calls: fib(n-1) and fib(n-2). Apply the framework: base cases are fib(0) = 0 and fib(1) = 1. Trust: both smaller calls return the correct Fibonacci values. Build: return their sum. This naive implementation is O(2^n) — we will fix that in the memoisation lesson.
def fib(n):
if n <= 1:
return n # base cases: fib(0)=0, fib(1)=1
# Trust both smaller sub-problems
return fib(n - 1) + fib(n - 2)
for i in range(8):
print(f'fib({i}) = {fib(i)}') # 0,1,1,2,3,5,8,13Reverse a String Recursively
Problem: reverse a string recursively. Base case: empty string or single character — already reversed. Trust: reverse(s[1:]) returns the reverse of everything after the first character. Build: append the first character at the end of the reversed suffix. The framework gives a three-line solution.
def reverse_str(s):
if len(s) <= 1:
return s # base case
# Trust: reverse_str(s[1:]) = reverse of 'ello' for 'hello'
# Build: append first character at end
return reverse_str(s[1:]) + s[0]
print(reverse_str('')) # ''
print(reverse_str('a')) # 'a'
print(reverse_str('hello')) # 'olleh'
print(reverse_str('racecar')) # 'racecar'Counting Occurrences Recursively
Problem: count occurrences of a target value in a list recursively. Base case: empty list — count is 0. Trust: count(lst[1:], target) returns the count in the tail. Build: add 1 if the first element matches the target, else add 0. Every recursive step makes progress toward the base case by reducing list size by 1.
def count_occurrences(lst, target):
if not lst:
return 0
# Trust: count in rest of list is handled recursively
# Build: add 1 if first element matches, else 0
return (1 if lst[0] == target else 0) + count_occurrences(lst[1:], target)
print(count_occurrences([1, 2, 3, 2, 4, 2], 2)) # 3
print(count_occurrences([], 5)) # 0
print(count_occurrences([7, 7, 7], 7)) # 3Check if a List is Sorted
Problem: check if a list is sorted in ascending order recursively. Base case: list of 0 or 1 elements is always sorted. Trust: is_sorted(lst[1:]) tells you if the tail is sorted. Build: the list is sorted if the first element is <= the second AND the tail is sorted. This is a clean example where the build step uses a logical AND of two conditions.
def is_sorted(lst):
if len(lst) <= 1:
return True
# Trust: is_sorted(lst[1:]) tells us if tail is sorted
# Build: head <= second element AND tail is sorted
return lst[0] <= lst[1] and is_sorted(lst[1:])
print(is_sorted([])) # True
print(is_sorted([1])) # True
print(is_sorted([1, 2, 3, 4])) # True
print(is_sorted([1, 3, 2, 4])) # FalseBinary Search Recursively (Revisited)
Binary search expressed recursively via the framework: base case: lo > hi → not found (return -1). Trust: recursive call on the correct half finds the target or returns -1. Build: compute mid, compare, call the appropriate half. The recursive form clearly shows the divide-and-conquer structure even though the iterative form is preferred in production for O(1) space.
def binary_search(arr, target, lo, hi):
if lo > hi: # base case: search space exhausted
return -1
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
# Trust both halves return correct results
if arr[mid] < target:
return binary_search(arr, target, mid + 1, hi)
else:
return binary_search(arr, target, lo, mid - 1)
arr = [1, 3, 5, 7, 9, 11]
print(binary_search(arr, 7, 0, len(arr) - 1)) # 3
print(binary_search(arr, 4, 0, len(arr) - 1)) # -1When to Use Recursion vs Iteration
Recursion excels when the problem naturally decomposes into smaller sub-problems of the same type (trees, divide and conquer, backtracking). Iteration is preferred when: the recursion depth is large (risking stack overflow in Python, which defaults to ~1000), the recursive and iterative versions are equally clear, or the problem is a simple loop (factorial, Fibonacci without memoisation).
A good rule of thumb: if drawing a recursion tree feels natural, use recursion. If the tree is a straight line (tail recursion), convert to iteration.
import sys
# Python's default recursion limit
print('Recursion limit:', sys.getrecursionlimit()) # 1000
# A list of 2000 elements would overflow the recursive sum_list
# Use iteration for safety:
def sum_list_iter(lst):
total = 0
for x in lst:
total += x
return total
big = list(range(2000))
print(sum_list_iter(big)) # 1999000 — no stack overflowQuick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: the three-step framework is Base Case (simplest known answer), Trust (assume sub-problem is solved), and Build (combine current element with trusted result), write base cases first and avoid tracing full call trees mentally, and use iteration when recursion depth risks stack overflow or when the recursive and iterative forms are equally clear. Next up we visualise the call stack in detail.
Frequently asked questions
Is the “Recursion Framework: Base Case, Trust, Build” lesson free?
Yes — the full text of “Recursion Framework: Base Case, Trust, Build” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “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. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Recursion Framework: Base Case, Trust, Build” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Recursion Framework: Base Case, Trust, Build
- Visualising the Call Stack
- Recursive vs Iterative Trade-offs
- Memoisation: Caching Recursive Results