Recursion Tutorial: Master Recursive Thinking & Divide-Conquer for Interviews
Complete recursion guide with base cases, divide-and-conquer patterns, and backtracking in Python. Learn recursive problem-solving, tail recursion, and when to use iteration for coding interviews
When Recursion Finally Clicked
I used to hate recursion. The call stack visualization made no sense. Why would you call a function from within itself? It felt like circular logic that should cause infinite loops.
Then someone told me: "Don't think about how—think about what." Don't trace every recursive call. Just trust that if your function works for smaller inputs, it works for larger ones.
That mental shift changed everything. Suddenly, problems that seemed impossibly complex became elegant one-liners.
In this guide, I'll share the mindset that made recursion intuitive for me. You'll learn to recognize recursive patterns, write base cases correctly, and transform complex problems into simple recursive solutions.
The Recursive Mindset
The key insight: Solve the problem for the smallest case, then assume you can solve it for smaller inputs. Combine those solutions for the current input.
The three-step framework:
- Base case: What's the simplest input? What should we return?
- Recursive case: Assume we can solve smaller problems. How do we combine them?
- Progress: Each recursive call must move toward the base case.
Example: Factorial
def factorial(n):
"""
Calculate n! recursively.
Trust that factorial(n-1) works!
"""
# Base case: simplest input
if n == 0 or n == 1:
return 1
# Recursive case: combine with smaller problem
return n * factorial(n - 1)
Mental model:
factorial(5) = 5 * factorial(4)- Don't trace all the way down
- Just trust that
factorial(4)gives the right answer
Pattern 1: Simple Recursion
Sum of Array
def array_sum(arr):
"""Sum array recursively."""
# Base case: empty array
if not arr:
return 0
# Recursive case: first element + sum of rest
return arr[0] + array_sum(arr[1:])
Reverse String
def reverse_string(s):
"""Reverse string recursively."""
# Base case: empty or single character
if len(s) <= 1:
return s
# Recursive case: last char + reverse of rest
return s[-1] + reverse_string(s[:-1])
Pattern: Process one element, recurse on the rest.
Pattern 2: Divide and Conquer
Break problem into independent subproblems, solve each, combine results.
Merge Sort
def merge_sort(arr):
"""
Sort array using divide and conquer.
Divide, sort halves, merge.
"""
# Base case: array of 0 or 1 element
if len(arr) <= 1:
return arr
# Divide
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # Solve left half
right = merge_sort(arr[mid:]) # Solve right half
# Conquer: merge sorted halves
return merge(left, right)
def merge(left, right):
"""Merge two sorted arrays."""
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
Pattern: Divide → Solve independently → Combine results
Quick Sort
def quick_sort(arr):
"""
Sort using divide and conquer.
Pick pivot, partition, recurse.
"""
# Base case
if len(arr) <= 1:
return arr
# Choose pivot
pivot = arr[len(arr) // 2]
# Partition
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
# Recurse and combine
return quick_sort(left) + middle + quick_sort(right)
Pattern 3: Binary Search (Recursive)
def binary_search_recursive(arr, target, left=0, right=None):
"""
Binary search implemented recursively.
Divide search space in half each time.
"""
if right is None:
right = len(arr) - 1
# Base case: search space exhausted
if left > right:
return -1
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, right)
else:
return binary_search_recursive(arr, target, left, mid - 1)
Pattern: Eliminate half the search space each call.
Pattern 4: Tree Recursion
Trees are naturally recursive structures—perfect for recursion!
Tree Height
def max_depth(root):
"""
Find height of binary tree.
Height = 1 + max(left_height, right_height).
"""
# Base case: empty tree
if not root:
return 0
# Recursive case: trust that it works for children
left_height = max_depth(root.left)
right_height = max_depth(root.right)
return 1 + max(left_height, right_height)
Tree Paths
def all_paths(root):
"""
Find all root-to-leaf paths.
Build path as we recurse.
"""
def dfs(node, current_path, all_paths):
if not node:
return
# Add current node
current_path.append(node.val)
# Leaf node: save path
if not node.left and not node.right:
all_paths.append(current_path[:])
else:
# Recurse on children
dfs(node.left, current_path, all_paths)
dfs(node.right, current_path, all_paths)
# Backtrack
current_path.pop()
result = []
dfs(root, [], result)
return result
Pattern 5: Backtracking with Recursion
Explore all possibilities by making choices, recursing, and undoing choices.
Generate Permutations
def permutations(nums):
"""
Generate all permutations recursively.
Choose → Recurse → Unchoose.
"""
result = []
def backtrack(current, remaining):
# Base case: used all numbers
if not remaining:
result.append(current[:])
return
# Try each remaining number
for i in range(len(remaining)):
# Choose
current.append(remaining[i])
# Recurse with one fewer option
backtrack(current, remaining[:i] + remaining[i+1:])
# Unchoose
current.pop()
backtrack([], nums)
return result
Generate Subsets
def subsets(nums):
"""
Generate all subsets recursively.
For each element: include it or don't.
"""
result = []
def backtrack(index, current):
# Base case: processed all elements
if index == len(nums):
result.append(current[:])
return
# Don't include current element
backtrack(index + 1, current)
# Include current element
current.append(nums[index])
backtrack(index + 1, current)
current.pop()
backtrack(0, [])
return result
Pattern 6: Multiple Recursions (Fibonacci-style)
Fibonacci
def fibonacci(n):
"""
Calculate nth Fibonacci number.
Two recursive calls (exponential without memoization!).
"""
# Base cases
if n <= 1:
return n
# Recursive case: sum of two previous
return fibonacci(n - 1) + fibonacci(n - 2)
# With memoization for efficiency
def fibonacci_memo(n, memo={}):
"""Fibonacci with memoization (top-down DP)."""
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
return memo[n]
Climbing Stairs
LeetCode #70 - Climbing Stairs
def climb_stairs(n):
"""
Ways to climb n stairs (1 or 2 steps at a time).
Same structure as Fibonacci!
"""
if n <= 2:
return n
return climb_stairs(n - 1) + climb_stairs(n - 2)
Pattern: Two recursive calls that combine results.
Pattern 7: Tail Recursion
Recursion where recursive call is the last operation (can be optimized to iteration).
Factorial (Tail Recursive)
def factorial_tail(n, accumulator=1):
"""
Tail-recursive factorial.
No operations after recursive call.
"""
if n == 0:
return accumulator
return factorial_tail(n - 1, n * accumulator)
Benefit: Some compilers optimize tail recursion to avoid stack overflow.
Sum (Tail Recursive)
def sum_tail(arr, accumulator=0):
"""Tail-recursive sum."""
if not arr:
return accumulator
return sum_tail(arr[1:], accumulator + arr[0])
Common Recursion Patterns
1. Process and Recurse
def process_and_recurse(data):
if not data:
return base_value
# Process first element
result = process(data[0])
# Recurse on rest
return combine(result, process_and_recurse(data[1:]))
2. Divide and Conquer
def divide_and_conquer(data):
if len(data) <= 1:
return data
mid = len(data) // 2
left = divide_and_conquer(data[:mid])
right = divide_and_conquer(data[mid:])
return merge(left, right)
3. Multiple Paths
def multiple_paths(n):
if n <= base:
return base_value
path1 = multiple_paths(n - 1)
path2 = multiple_paths(n - 2)
return combine(path1, path2)
Recursion vs Iteration
When to use recursion:
- Problem naturally recursive (trees, graphs)
- Divide and conquer
- Backtracking
- Makes code cleaner and more readable
When to use iteration:
- Simple loops
- Stack overflow concerns (very deep recursion)
- Performance critical (recursion has overhead)
Converting recursion to iteration:
# Recursive
def factorial_recursive(n):
if n <= 1:
return 1
return n * factorial_recursive(n - 1)
# Iterative
def factorial_iterative(n):
result = 1
for i in range(2, n + 1):
result *= i
return result
Common Recursion Mistakes
Mistake 1: Missing Base Case
# WRONG: No base case → infinite recursion!
def countdown(n):
print(n)
countdown(n - 1) # Never stops!
# RIGHT: Base case stops recursion
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1)
Mistake 2: Not Making Progress
# WRONG: Not moving toward base case
def buggy(n):
if n == 0:
return
buggy(n) # Infinite recursion!
# RIGHT: Each call moves toward base case
def fixed(n):
if n == 0:
return
fixed(n - 1) # Progress!
Mistake 3: Modifying and Using Same Variable
# WRONG: Modifying list being recursed on
def buggy_sum(arr):
if not arr:
return 0
first = arr.pop(0) # Modifies arr!
return first + buggy_sum(arr)
# RIGHT: Don't modify, slice instead
def correct_sum(arr):
if not arr:
return 0
return arr[0] + correct_sum(arr[1:])
Mistake 4: Stack Overflow
# For very large n, this crashes
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
# Solution: Use iteration or increase recursion limit
import sys
sys.setrecursionlimit(10000) # Use cautiously!
Recursion Complexity Analysis
Time complexity:
- Count recursive calls × work per call
- Tree structure: O(branches^depth)
- Linear recursion: O(n)
Space complexity:
- Recursion depth (call stack)
- O(n) for linear, O(log n) for binary
Examples:
factorial(n): Time O(n), Space O(n)fibonacci(n)(naive): Time O(2^n), Space O(n)fibonacci(n)(memo): Time O(n), Space O(n)merge_sort(n): Time O(n log n), Space O(n)
The Recursion Decision Tree
When you see a problem:
1. Can it be broken into smaller identical problems?
- YES → Consider recursion
2. Is there a natural recursive structure? (tree, graph)
- YES → Recursion likely best
3. Do you need to explore all possibilities?
- YES → Backtracking with recursion
4. Is it divide and conquer?
- YES → Recursive divide
5. Will recursion depth be very large? (> 1000)
- YES → Use iteration or memoization
My Practice Strategy
Week 1: Simple Recursion
- Factorial, sum, reverse
- Master base cases
- Practice tracing (but don't rely on it!)
- 20-30 simple problems
Week 2: Tree Recursion
- Binary tree problems
- Height, paths, properties
- 15-20 tree problems
Week 3: Divide and Conquer
- Merge sort, quick sort
- Binary search recursive
- 15-20 problems
Week 4: Backtracking
- Permutations, combinations, subsets
- N-Queens, Sudoku
- 20-30 problems
Real Interview Success
I was asked: "Print all valid combinations of n pairs of parentheses."
My approach:
- "Generate all valid combinations" → Backtracking
- At each step: add '(' or ')'
- Constraints: can't have more ')' than '(', can't exceed n
Coded recursively in 10 minutes:
def generate_parentheses(n):
result = []
def backtrack(current, open_count, close_count):
if len(current) == 2 * n:
result.append(current)
return
if open_count < n:
backtrack(current + '(', open_count + 1, close_count)
if close_count < open_count:
backtrack(current + ')', open_count, close_count + 1)
backtrack('', 0, 0)
return result
The recursive solution was elegant and clear!
Conclusion: Your Recursion Mastery Roadmap
Recursion isn't magic—it's trusting that smaller problems are solved:
- Think "what," not "how" - Don't trace every call
- Master base cases - Where recursion stops
- Ensure progress - Each call moves toward base case
- Practice patterns - Simple, divide-and-conquer, backtracking
Start with simple problems (factorial, sum). Build confidence. Move to trees (natural recursion). Finally, tackle backtracking.
Within 4 weeks, recursive thinking becomes natural. You'll see elegant recursive solutions where others see complexity.
Remember: every recursive expert once struggled to understand the call stack. The difference is they learned to trust the recursion!
Happy coding, and may your base cases always be reached!
If you found this guide helpful, share it with others learning recursion. Recursive thinking is a superpower once it clicks. If this guide helped you master recursion or understand divide-and-conquer dsa, I'd love to hear about it! Connect with me on Twitter or LinkedIn.
Support My Work
If this guide helped you finally understand recursion, master recursive thinking, or ace recursion interview questions, I'd really appreciate your support! Creating comprehensive, free content like this takes significant time and effort. Your support helps me continue sharing knowledge and creating more helpful resources for students like you.
☕ Buy me a coffee - Every contribution, big or small, means the world to me and keeps me motivated to create more content!
Cover image by Marcus Urbenz on Unsplash