SyntaxShelf

Base case

2 snippets across 2 stacks - Interview Prep, Python

DSAInterview Prep

Base Case & Recursive Case

DSA · Recursion & Backtracking
Syntax
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 case
Example
// 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) → 1024

Note 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.

PYPython

Recursion

PY · Functions
Syntax
def func(n):
    if base_case: return value
    return func(modified_n)
Example
def factorial(n: int) -> int:
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(factorial(6))

import sys
print(f"Recursion limit: {sys.getrecursionlimit()}")
Output
720
Recursion limit: 1000

Note Python's default recursion limit is 1000. Deeply recursive algorithms should be rewritten iteratively or use sys.setrecursionlimit() with caution.

Frequently asked questions

How does Interview Prep handle base case?
This task is covered in 2 stacks on this page: Interview Prep, Python. The "Base Case & Recursive Case" snippet in Interview Prep uses `Every recursive function needs:`.
Which code does the Interview Prep example use?
The "Base Case & Recursive Case" snippet uses `Every recursive function needs:`, from the Recursion & Backtracking section of the Interview Prep cheat sheet.
Which stacks cover "base case" on this page?
Interview Prep, Python. Together they hold 2 copy-ready snippets for this task.
Is there anything to watch out for?
Yes. For "Base Case & Recursive Case": 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.

Browse all tasks by intent