Part I · Foundations, Programming and Algorithmic Thinking
5. Recursion and Divide-and-Conquer Fundamentals
7 lessons•44 topics•Beginner
7 of 7 lessons published
5.011 animated
Recursion mechanics
- Base case
- Recursive case
- Call stack
- Return path
- Stack frames
- Termination
- Recursive invariants
- Tail recursion
5.026 animated
Classical examples
- Factorial
- Fibonacci
- Sum of digits
- Reverse array
- Power function
- Greatest common divisor
- Recursive binary search
5.031 animated
Recursion patterns
- Linear recursion
- Binary recursion
- Multiple branching
- Head vs tail recursion
- Mutual recursion
- Recursion with return value
5.043 animated
Divide and conquer
- Divide
- Conquer
- Combine
- Balanced vs unbalanced split
- Recursion tree
- Merge sort intuition
- Quick sort intuition
5.051 animated
Recurrence analysis
- Recurrence setup
- Recursive tree size
- Call stack depth
- Master theorem cases
- Time-space trade-off
5.06Lesson
Recursion pitfalls
- Missing base case
- Incorrect return
- Shared mutable state
- Repeated subproblems
- StackOverflowError
- Integer overflow
5.07Lesson
Converting recursion
- Explicit stack
- Iterative DFS
- Bottom-up processing
- Tail-call transformation
- Memoization