Think Recursively: Base & Recurse
Break a problem into smaller copies.
Think Recursively: Base & Recurse is a free Coding 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 Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
What Recursion Means
Recursion is a function that solves a problem by calling itself on a smaller piece, until the piece is tiny enough to answer directly. 🌀
Trust the Smaller Copy
The key mindset is the leap of faith: assume the recursive call already works on the smaller input, then build your answer on top of it.
Every Recursion Needs a Base Case
The base case is the smallest input you answer without recursing. Without it, the function calls itself forever and crashes.
The Recursive Case
The recursive case reduces the problem and calls itself on the smaller version. Each call must move closer to the base case.
Factorial as a First Example
Here factorial shows both parts: a base case at zero and a recursive call on n minus one.
def fact(n):
if n == 0:
return 1
return n * fact(n - 1)How the Call Stack Works
Each call waits on the call stack until its inner call returns. The deepest call finishes first, then the answers unwind back up.
Watch the Recursion Depth
Python caps recursion depth near 1000 by default. Deep contest recursion needs sys.setrecursionlimit to avoid a runtime error.
import sys
sys.setrecursionlimit(300000)Make Progress Every Call
A correct recursion always shrinks the input toward the base case. If it ever passes the same size again, it loops forever. ⚠️
Sum a List Recursively
This recursive sum peels off the first element, then trusts the call to add the rest of the list.
def total(a):
if not a:
return 0
return a[0] + total(a[1:])Recursion Trees Show Branching
When a function makes more than one call, the work forms a recursion tree. Its size tells you the total cost.
Repeated Work Can Be Slow
Naive Fibonacci recomputes the same values over and over, giving exponential time. Memoizing those answers fixes it instantly.
Quick Check
What happens if a recursive function has no base case?
Recap: Two Parts, One Idea
You learned that recursion needs a base case to stop and a recursive case that shrinks the input. Trust the smaller call and the rest follows. 🎯
Frequently asked questions
Is the “Think Recursively: Base & Recurse” lesson free?
Yes — the full text of “Think Recursively: Base & Recurse” is free to read here on the web, and the Coding 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 Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Think Recursively: Base & Recurse”?
Break a problem into smaller copies. You practise Coding 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 Coding Interview Prep?
No prior experience is required. Coding 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 “Think Recursively: Base & Recurse” 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 Coding Interview Prep lesson?
Yes. Every Coding 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
- Think Recursively: Base & Recurse
- Generate All Subsets
- Permutations and the N-Queens Idea
- Prune to Survive the Time Limit