Recursion
Master recursive functions - functions that call themselves to solve problems by breaking them into smaller, similar subproblems
Learn how to write functions that call themselves to solve problems through recursive thinking.
A Simple Example
#include <iostream>
// Count down from n to 1
void countdown(int n) {
// Base case: stop when we reach 0
if (n <= 0) {
std::cout << "Liftoff!" << "\n";
return;
}
// Recursive case: print and call with smaller value
std::cout << n << "..." << "\n";
countdown(n - 1); // Function calls itself!
}
int main() {
countdown(5);
return 0;
}Breaking It Down
Base Case - The Stopping Condition
- What it does: Defines when the recursion should stop
- Essential: Without it, you get infinite recursion and stack overflow
-
Example:
if (n <= 0) return;stops when counting reaches zero - Remember: Always write the base case first when creating recursive functions
Recursive Case - The Self-Call
- What it does: Calls the same function with a simpler problem
- Must progress: Each call should move closer to the base case
-
Example:
countdown(n - 1)reduces n by 1 each time - Remember: Think "solve a smaller version of the same problem"
The Call Stack
- What happens: Each function call is pushed onto a stack in memory
- Unwinding: When base case is reached, calls return in reverse order
- Limit: Stack has limited size, too many calls cause stack overflow
- Remember: Recursion uses more memory than loops due to stack frames
Recursive Return Values
- What to do: If function returns a value, return the recursive call
-
Common pattern:
return someValue + recursiveCall(n-1); -
Example: Factorial needs
return n * factorial(n-1); - Remember: Forgetting to return the recursive result loses computed values
Why This Matters
- Some problems are naturally recursive: calculating factorials, traversing tree structures, searching directories, processing nested data.
- Recursion can make these problems elegant and simple, where iterative solutions would be complex and hard to understand.
- Master recursion and you'll unlock a new way of thinking about problem-solving.
Critical Insight
The order of the recursive call matters! Calling recursively before or after your operation changes behavior completely:
#include <iostream>
void beforeRecursion(int n) {
if (n <= 0) return;
std::cout << n << " "; // Print FIRST
beforeRecursion(n - 1); // Then recurse
}
// Output for beforeRecursion(5): 5 4 3 2 1
void afterRecursion(int n) {
if (n <= 0) return;
afterRecursion(n - 1); // Recurse FIRST
std::cout << n << " "; // Then print
}
// Output for afterRecursion(5): 1 2 3 4 5
Operations after the recursive call happen in "unwinding" order, from innermost to outermost!
Best Practices
Always define the base case first: Write and test your stopping condition before the recursive case to prevent infinite recursion.
Make progress toward base case: Each recursive call must move closer to the base case. Ensure parameters change in a way that eventually reaches the stopping condition.
Consider iteration for simple cases: If recursion depth could be large or the problem is naturally iterative, use loops instead to avoid stack overflow.
Return recursive calls: If your function returns a value, don't forget return recursiveFunction(...) to pass the result up the call chain.
Common Mistakes
Missing Base Case: Causes infinite recursion and stack overflow. Always include a clear stopping condition.
Base Case Never Reached: Progress doesn't lead to base case. Example: decrementing by 2 but checking for n == 0 misses odd numbers.
Forgetting to Return Recursive Call: Writing factorial(n-1); instead of return n * factorial(n-1); loses the computed value.
Too Deep Recursion: Very large inputs cause stack overflow. Consider iteration or tail recursion optimization.
Inefficient Recursion: Multiple redundant calculations like naive Fibonacci. Use memoization or dynamic programming.
Debug Challenge
This recursive function tries to count down but has a bug that causes infinite recursion. Click the highlighted line to fix it:
Quick Quiz
- What are the two essential parts of a recursive function?
- What happens if you forget the base case in a recursive function?
- Given:
int factorial(int n) { if (n <= 1) return 1; return n * factorial(n-1); }What is factorial(4)?
Practice Playground
Time to try out what you just learned! Play with the example code below, experiment by making changes and running the code to deepen your understanding.
Output:
Error:
Lesson Progress
- Fix This Code
- Quick Quiz
- Practice Playground - run once