Learn how a function can solve a smaller version of the same problem. Understand base cases, recursive calls, the call stack and important recursion patterns.
Recursion is a technique where a function calls itself to solve a smaller version of the same problem.
The condition that stops the recursive calls. Every recursive solution needs a clear stopping condition.
The function calls itself with a smaller or simpler input.
Every function call waits on the stack until its recursive call finishes.
A recursive problem can usually be understood using three simple steps.
Factorial is one of the easiest ways to understand the recursive idea.
These patterns appear frequently in DSA problems.
One recursive call at every step. Examples include factorial and sum of numbers.
A function makes multiple recursive calls. Fibonacci is a common example.
Use an index or two pointers to recursively process an array.
Move through a string or reduce it one character at a time.
Make a choice, recurse, then undo the choice and try another possibility.
Divide a problem into smaller parts, solve them recursively and combine the results.
Decide exactly what the function should return or accomplish.
Ask when the problem becomes small enough to solve directly.
Every recursive call must move closer to the base case.
Assume the recursive function correctly solves the smaller problem.
Use the smaller result to construct the answer for the current problem.
Draw the call stack when recursion becomes difficult to visualize.
| Problem | Time | Stack Space |
|---|---|---|
| Factorial | O(n) | O(n) |
| Sum of Array | O(n) | O(n) |
| Binary Search | O(log n) | O(log n) |
| Merge Sort | O(n log n) | O(log n) |
| Naive Fibonacci | O(2ⁿ) | O(n) |
Implement factorial using recursion.
Enter a number and see how factorial moves toward the base case.
Watch the concept first and then solve the practice problems.