Recursion
MedRecursion solves problems by expressing a solution in terms of smaller, self-similar subproblems. The key is a clear base case, a correct recursive step, and a clean combine step.
Time Complexity
| Operation | Average | Worst | Best |
|---|---|---|---|
| Factorial | O(n) | ||
| Binary Search | O(log n) | O(log n) | |
| Divide-and-Conquer | O(n log n) | O(n log n) |
Key Points
- Every recursive function needs a base case that stops further calls
- The recursive step must move toward the base case
- The combine step is where you build the final answer from recursive results
- Divide-and-conquer uses recursion when the combine step is deterministic
- Call stack depth equals recursion depth and can be a practical limit
Code Examples
Factorial (Base + Recursive Case)
function factorial(n) {
if (n <= 1) return 1
return n * factorial(n - 1)
}
factorial(5) // 120Base case handles n<=1. For n>1, we reduce the same problem size by 1 and multiply by n on the way back.
Recursive Binary Search
function binarySearch(arr, target, left = 0, right = arr.length - 1) {
if (left > right) return -1
const mid = Math.floor((left + right) / 2)
if (arr[mid] === target) return mid
if (target < arr[mid]) {
return binarySearch(arr, target, left, mid - 1)
}
return binarySearch(arr, target, mid + 1, right)
}
binarySearch([1, 3, 5, 7, 9], 7) // 3Each call reduces the search range in half. Time complexity is O(log n) because each level removes about half the candidates.
Tree DFS (Depth First)
function maxDepth(node) {
if (!node) return 0
const left = maxDepth(node.left)
const right = maxDepth(node.right)
return Math.max(left, right) + 1
}Tree questions often become recursion naturally because each node has the same subproblem on left and right child.
Common Mistakes
- Forgetting the base case causes infinite recursion
- Not reducing input toward base case creates an infinite loop
- Passing wrong arguments into recursive calls
- Ignoring call stack depth for deep input
- Using recursion when an iterative approach is simpler for constraints
Interview Tips
- State the state of one recursive call before moving to the next
- Write base case first, then recursion, then combine
- Trace one sample input by hand before coding
- Mention O(recursion depth) space from call stack