Base Case & Recursive Case
DSA · Recursion & Backtrackingsyntax
Every recursive function needs:
1. Base case: when to stop (prevents infinite recursion)
2. Recursive case: break problem into smaller subproblem
3. Progress: each call must move toward the base caseexample
// JavaScript — Sum of array using recursion
function sumArray(arr, idx = 0) {
if (idx >= arr.length) return 0; // base case
return arr[idx] + sumArray(arr, idx + 1); // recursive case
}
// Power function
function power(base, exp) {
if (exp === 0) return 1; // base case
if (exp % 2 === 0) {
const half = power(base, exp / 2);
return half * half; // O(log n)
}
return base * power(base, exp - 1);
}
# Python
def sum_array(arr, idx=0):
if idx >= len(arr):
return 0
return arr[idx] + sum_array(arr, idx + 1)
def power(base, exp):
if exp == 0:
return 1
if exp % 2 == 0:
half = power(base, exp // 2)
return half * half
return base * power(base, exp - 1)output
sum_array([1,2,3,4]) → 10
power(2, 10) → 1024Note Always identify the base case first. Stack overflow risk: Python default limit is 1000 frames (sys.setrecursionlimit can increase). For deep recursion, convert to iteration. The power function shows how recursion can achieve O(log n) — a common follow-up.