45:"/_next/static/chunks/33yus346z0l_n.js" 46:"/_next/static/chunks/2j22cxchii_xx.js" 47:"/_next/static/chunks/0iv56yrji_20j.js" 48:"/_next/static/chunks/32izpn90gvm22.js" 49:"/_next/static/chunks/3j8bi-zu9bqs4.js" 4a:"/_next/static/chunks/1z-pox7hqp2x3.js" 4b:"/_next/static/chunks/20w4eaqlekefm.js" 4c:"/_next/static/chunks/1tn-0fivsxsv1.js" 4d:"/_next/static/chunks/09nq57stwzkgf.js" 4e:"/_next/static/chunks/3m1xjj5kw5fie.js" 4f:"/_next/static/chunks/0gafyzg9j9yqj.js" 50:"/_next/static/chunks/3k2gyg36fnag_.js" 51:"/_next/static/chunks/3bgoyiso1rhn7.js" 52:"/_next/static/chunks/3cstd6xzfli_o.js" 53:"/_next/static/chunks/253gnmj0-cj17.js" 54:"/_next/static/chunks/0hlb44ca7-4a2.js" 55:"/_next/static/chunks/20329i6m_04t6.js" 56:"/_next/static/chunks/40mq7ggq-ozo4.js" 57:"/_next/static/chunks/082jo-0ajazgr.js" 58:"/_next/static/chunks/2ozcrjb_hh74t.js" 59:"/_next/static/chunks/01a-3hvnqu8wl.js" 5a:"/_next/static/chunks/05i8en-x14ibi.js" 5b:"/_next/static/chunks/3m0r7x0jt5wm7.js" 5c:"/_next/static/chunks/2k8pepwc4pxns.js" 5d:"/_next/static/chunks/0wa9m1-tphf9u.js" 5e:"/_next/static/chunks/30jdm3dwz834g.js" 5f:"/_next/static/chunks/0k9bl6dipnsvu.js" 60:"/_next/static/chunks/18ggtgz2yf759.js" 61:"/_next/static/chunks/0i3-eynrkvqi7.js" 62:I[593304,["$2a","$2b","$2c","$2d","$2e","$2f","$45","$46","$47","$48","$49","$4a","$4b","$4c","$4d","$4e","$4f","$50","$51","$52","$53","$54","$55","$56","$57","$58","$59","$5a","$5b","$5c","$5d","$5e","$5f","$60","$61"],"OwnedHydration"] 63:T450,Base cases serve four essential purposes that make recursion possible and correct: **1. Termination Guarantee** Without a base case, recursive calls continue indefinitely. Each call adds a new frame to the call stack until memory is exhausted, causing a **stack overflow**. The base case is the emergency brake that stops this expansion. **2. Foundation for Correctness** The correctness of a recursive algorithm depends on **mathematical induction**: - **Base case proved**: The algorithm is correct for the smallest inputs - **Inductive step**: If correct for size `k`, then correct for size `k+1` Without a correct base case, the entire inductive argument collapses. **3. Anchor for Return Values** Recursive functions build their answers from smaller answers. The base case provides the **first actual answer**—the seed from which all larger answers grow through the recursive chain. **4. Problem Boundary Definition** The base case implicitly defines what inputs your function handles. It marks the boundary between 'problems that need decomposition' and 'problems we can solve directly.'64:T4da,Identifying the right base case(s) isn't guesswork—it's a methodical process. Follow these steps to systematically derive base cases for any recursive problem: **Step 1: Identify the Input Parameter(s)** What is your function parameterized by? This determines what 'smaller' means. - A number `n` → smaller means `n-1`, `n/2`, etc. - An array/list → smaller means a subarray, shorter list - A tree → smaller means subtrees, children - A string → smaller means substrings **Step 2: Ask 'What Is the Smallest Valid Input?'** For each parameter, determine the smallest value(s) it can take: - Numbers: 0, 1, or the problem's minimum - Arrays: empty array `[]`, or single-element `[x]` - Trees: `null` (empty tree), or a leaf node - Strings: empty string `""`, or single character **Step 3: For Each Smallest Input, Answer: 'What's the Result?'** Don't compute—just **know** the answer: - Sum of empty array → 0 - Length of empty string → 0 - Maximum of single element → that element - Factorial of 0 → 1 **Step 4: Verify the Base Case Catches All Termination Points** Trace your recursive logic and ensure the base case activates at the right moment. Every path through your recursion must eventually hit a base case.65:T5d8,from typing import List def binary_search(arr: List[int], target: int, low: int, high: int) -> int: """ Search for target in a sorted array using binary search. Returns index if found, -1 otherwise. """ # BASE CASE: Search space is empty if low > high: return -1 # Target not found mid = (low + high) // 2 # BASE CASE: Target found (sometimes considered part of recursive case) if arr[mid] == target: return mid # RECURSIVE CASE: Search in appropriate half if target < arr[mid]: return binary_search(arr, target, low, mid - 1) else: return binary_search(arr, target, mid + 1, high) def merge_sort(arr: List[int]) -> List[int]: """Sort an array using merge sort.""" # BASE CASE: Array of size 0 or 1 is already sorted if len(arr) <= 1: return arr # RECURSIVE CASE: Split, sort halves, merge mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left, right) # merge() combines two sorted arrays def merge(left: List[int], right: List[int]) -> List[int]: """Merge two sorted arrays into one sorted array.""" result = [] i = j = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result.extend(left[i:]) result.extend(right[j:]) return result66:T49b,def climb_stairs(n: int) -> int: """ Count distinct ways to climb n stairs, taking 1 or 2 steps at a time. BASE CASES: - n = 0: Already at top → 1 way (the empty path) - n = 1: One step left → 1 way (take 1 step) RECURSIVE CASE: - To reach step n, we either: - Came from step n-1 (took 1 step) - Came from step n-2 (took 2 steps) - Total ways = ways(n-1) + ways(n-2) """ # BASE CASES if n == 0: return 1 # One way: stay (empty path) if n == 1: return 1 # One way: single step # RECURSIVE CASE return climb_stairs(n - 1) + climb_stairs(n - 2) # Why is climb_stairs(0) = 1? # This is the "empty sum" principle. If you're already at the destination, # there exists exactly one way to "get there": by doing nothing. # This is analogous to how the empty product is 1 (0! = 1). # Let's verify: # climb_stairs(2) = climb_stairs(1) + climb_stairs(0) = 1 + 1 = 2 # Path 1: [1, 1] (two single steps) # Path 2: [2] (one double step) # ✓ Correct! # climb_stairs(3) = climb_stairs(2) + climb_stairs(1) = 2 + 1 = 3 # Path 1: [1, 1, 1] # Path 2: [1, 2] # Path 3: [2, 1] # ✓ Correct!67:T415,function climbStairs(n: number): number { /** * Count distinct ways to climb n stairs, taking 1 or 2 steps at a time. * * BASE CASES: * - n = 0: Already at top → 1 way (the empty path) * - n = 1: One step left → 1 way (take 1 step) * * RECURSIVE CASE: * - To reach step n, we either: * - Came from step n-1 (took 1 step) * - Came from step n-2 (took 2 steps) * - Total ways = ways(n-1) + ways(n-2) */ // BASE CASES if (n === 0) { return 1; // One way: stay (empty path) } if (n === 1) { return 1; // One way: single step } // RECURSIVE CASE return climbStairs(n - 1) + climbStairs(n - 2); } // Why is climbStairs(0) = 1? // This is the "empty sum" principle. If you're already at the destination, // there exists exactly one way to "get there": by doing nothing. // Let's verify: // climbStairs(2) = climbStairs(1) + climbStairs(0) = 1 + 1 = 2 ✓ // climbStairs(3) = climbStairs(2) + climbStairs(1) = 2 + 1 = 3 ✓68:T4a4,Identifying a base case is only half the battle—you must also verify it's correct. Here's a rigorous validation checklist: **Validation Check 1: Termination Guarantee** For every valid input, will the recursion eventually reach a base case? - Trace the recursive calls from any starting point - Verify that each recursive call moves closer to a base case - Check for inputs that might bypass base cases (negative numbers, empty collections with wrong checks, etc.) **Validation Check 2: Correctness for Smallest Inputs** Is the returned value actually correct for the base case inputs? - Manually verify: Does `factorial(0)` really equal 1? Does `sum([])` really equal 0? - Cross-check with mathematical definitions or problem constraints **Validation Check 3: Boundary Coverage** Are there any inputs that could slip through? - What happens at `n = -1`? At empty strings? At null pointers? - Ensure your base case conditions cover all non-recursive scenarios **Validation Check 4: Consistency with Recursive Case** Does the base case integrate smoothly with the recursive logic? - The recursive case builds upon base case answers - Verify that the types and semantics match69:T59f,# Let's validate the base cases for a string palindrome checker def is_palindrome(s: str) -> bool: """ Check if a string is a palindrome (reads same forwards and backwards). """ # BASE CASE ANALYSIS: # - Empty string "" → Is it a palindrome? YES (vacuously true) # - Single char "a" → Is it a palindrome? YES # Therefore: strings of length 0 or 1 are palindromes if len(s) <= 1: return True # RECURSIVE CASE: # If first char == last char AND middle is palindrome → palindrome if s[0] != s[-1]: return False return is_palindrome(s[1:-1]) # VALIDATION: # ✓ Termination: s[1:-1] is always shorter than s, so we reach len(s) <= 1 # ✓ Correctness: "" and "x" are indeed palindromes # ✓ Boundary: len(s) == 0 is covered (not missed) # ✓ Consistency: Recursive case properly depends on base case # Let's trace is_palindrome("racecar"): # is_palindrome("racecar") # 's'[0]='r' == 's'[-1]='r' ✓ # → is_palindrome("aceca") # 's'[0]='a' == 's'[-1]='a' ✓ # → is_palindrome("cec") # 's'[0]='c' == 's'[-1]='c' ✓ # → is_palindrome("e") # len("e") == 1 → return True ← BASE CASE # return True # return True # return True # Result: True ✓ # Counterexample trace: is_palindrome("hello") # is_palindrome("hello") # 's'[0]='h' != 's'[-1]='o' → return False # Result: False ✓6a:T5c8,Certain base case values appear repeatedly across different problems. Understanding their semantic meaning helps you choose correctly: **Return 0 (Additive Identity)** Used when combining results through **addition**. - Sum of empty list → 0 (adding nothing contributes nothing) - Count of elements in empty list → 0 - Distance in empty path → 0 **Return 1 (Multiplicative Identity)** Used when combining results through **multiplication** or **counting combinations**. - Factorial of 0 → 1 (multiplying nothing yields the identity) - Number of ways to arrange 0 items → 1 (one way: do nothing) - Empty product → 1 **Return True (Vacuous Truth)** Used in Boolean contexts for **universal conditions on empty sets**. - Is empty list sorted? → True (no elements to be out of order) - Is empty string a palindrome? → True (trivially true) - Does empty set satisfy property P? → True (if P is universal) **Return False (Existential Failure)** Used when **searching** for something in an empty collection. - Does empty list contain X? → False - Is there a path with no nodes? → False **Return Empty Collection** Used when building/filtering collections that might be empty. - Filter on empty list → empty list - Flatten empty nested structure → empty structure **Return self/None/Null** Used in **structural recursion** on data structures. - Reverse empty list → empty list (or same pointer) - Tree traversal on null → do nothing / return null43:["$","$L62",null,{"owner":"anonymous","state":{"mutations":[],"queries":[{"dehydratedAt":1792309753038,"state":{"data":{"json":{"id":"seed_850d92b5ec269917b761322ea7ef450e","slug":"base-cases-and-recursive-cases","category":"Data Structures & Algorithms","topic":"Base Cases & Recursive Cases","title":"Base Cases & Recursive Cases","description":"Master the art of designing base cases and recursive cases—the two pillars of every recursive solution. Learn to identify correct termination conditions, handle multiple base cases, ensure convergence, and avoid the common pitfalls that cause infinite recursion and stack overflows.","difficulty":"BEGINNER","estimatedMinutes":60,"pages":[{"id":"seed_bfb81dcd009211e189123ff87aaa308c","title":"Identifying Correct Base Cases","order":0,"content":[{"id":"opening-hook","title":"The Foundation That Prevents Infinite Descent","content":[{"data":{"content":"Every recursive function faces an existential question: **When do I stop?**\n\nWithout a clear answer, recursion becomes a one-way trip into oblivion—an infinite cascade of function calls that eventually crashes your program with a stack overflow. The **base case** is that answer. It's the bedrock upon which all recursive reasoning rests.\n\nYet despite its criticality, the base case is often treated as an afterthought—something developers tack on after writing the 'interesting' recursive logic. This backwards approach leads to subtle bugs, infinite loops, and hours of frustrating debugging. In this page, we'll reverse that thinking: **we start with the base case, because it determines everything else.**"},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand what base cases are and why they're essential, how to systematically identify correct base cases for any recursive problem, the relationship between base cases and problem structure, common patterns in base case design, and techniques for validating that your base cases are complete and correct.","variant":"info"},"type":"callout"}]},{"id":"what-is-base-case","title":"What Is a Base Case?","content":[{"data":{"content":"A **base case** is the simplest instance of a problem—one so trivial that it can be solved directly, without any further recursion. It's the point where the recursive decomposition stops and actual computation begins.\n\n**Formal Definition:**\n\nIn a recursive function `f(n)`, a base case is a condition where:\n1. The answer is immediately known (no further computation needed)\n2. The function returns without calling itself\n3. The problem cannot be reduced any further\n\n**The Analogy of Descent:**\n\nImagine you're descending a staircase in the dark. Each step down represents a recursive call to a smaller subproblem. The base case is the ground floor—the moment your feet touch solid foundation. Without it, you'd keep stepping down forever, falling into an infinite void.\n\nEvery well-designed recursive function has this structure:\n- **Recursive cases** move you toward the ground floor\n- **Base cases** tell you when you've arrived\n- **Return values** carry answers back up the staircase"},"type":"text"},{"data":{"fileName":"base_case_anatomy.py","languages":[{"code":"def factorial(n: int) -> int:\n \"\"\"\n Compute n! = n × (n-1) × (n-2) × ... × 2 × 1\n \n BASE CASE: When n = 0 or n = 1, we know the answer is 1\n - 0! = 1 (by mathematical convention)\n - 1! = 1 (trivially, just 1)\n \n RECURSIVE CASE: For n > 1, n! = n × (n-1)!\n - This reduces the problem to a smaller instance\n \"\"\"\n # BASE CASE: The problem is small enough to solve directly\n if n <= 1:\n return 1 # No recursion needed—we know the answer\n \n # RECURSIVE CASE: Reduce to smaller subproblem\n return n * factorial(n - 1)\n\n# Trace: factorial(4)\n# factorial(4) → 4 * factorial(3)\n# → 4 * (3 * factorial(2))\n# → 4 * (3 * (2 * factorial(1)))\n# → 4 * (3 * (2 * 1)) ← BASE CASE HIT\n# → 4 * (3 * 2)\n# → 4 * 6\n# → 24","label":"Python","value":"python"},{"code":"function factorial(n: number): number {\n /**\n * Compute n! = n × (n-1) × (n-2) × ... × 2 × 1\n * \n * BASE CASE: When n = 0 or n = 1, we know the answer is 1\n * - 0! = 1 (by mathematical convention)\n * - 1! = 1 (trivially, just 1)\n * \n * RECURSIVE CASE: For n > 1, n! = n × (n-1)!\n * - This reduces the problem to a smaller instance\n */\n \n // BASE CASE: The problem is small enough to solve directly\n if (n <= 1) {\n return 1; // No recursion needed—we know the answer\n }\n \n // RECURSIVE CASE: Reduce to smaller subproblem\n return n * factorial(n - 1);\n}\n\n// Trace: factorial(4)\n// factorial(4) → 4 * factorial(3)\n// → 4 * (3 * factorial(2))\n// → 4 * (3 * (2 * factorial(1)))\n// → 4 * (3 * (2 * 1)) ← BASE CASE HIT\n// → 4 * (3 * 2)\n// → 4 * 6\n// → 24","label":"TypeScript","value":"typescript"}]},"type":"code"},{"data":{"icon":"Lightbulb","title":"The Ground Truth Principle","content":"Think of base cases as 'ground truths'—facts about your problem that you know to be true without needing to compute anything. For factorial: 1! = 1. For Fibonacci: F(0) = 0, F(1) = 1. For tree traversal: an empty tree has no nodes to visit. These ground truths anchor all recursive computation.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":1},{"id":"why-base-cases-critical","title":"Why Base Cases Are Critical","content":[{"data":{"content":"$63"},"type":"text"},{"data":{"left":[{"data":{"items":["Function calls itself infinitely","Stack grows without bound","Eventually: **Stack Overflow Error**","No answer is ever returned","Program crashes or hangs"],"title":{"icon":"XCircle","text":"Without Base Case","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["Recursion stops at known boundary","Stack has finite maximum depth","Function terminates predictably","Concrete answers propagate upward","Correct result is computed"],"title":{"icon":"CheckCircle","text":"With Correct Base Case","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"fileName":"infinite_recursion_example.py","languages":[{"code":"# ❌ DANGEROUS: No base case - infinite recursion\ndef countdown_broken(n: int) -> None:\n \"\"\"This function will crash with a stack overflow.\"\"\"\n print(n)\n countdown_broken(n - 1) # Never stops!\n\n# countdown_broken(5) will print:\n# 5, 4, 3, 2, 1, 0, -1, -2, -3, ... then CRASH!\n\n# ✅ CORRECT: Base case stops the recursion\ndef countdown_correct(n: int) -> None:\n \"\"\"This function terminates when n reaches 0.\"\"\"\n if n < 0: # BASE CASE\n return # Stop recursing\n \n print(n)\n countdown_correct(n - 1)\n\n# countdown_correct(5) prints: 5, 4, 3, 2, 1, 0 then stops gracefully","label":"Python","value":"python"},{"code":"// ❌ DANGEROUS: No base case - infinite recursion\nfunction countdownBroken(n: number): void {\n /** This function will crash with a stack overflow. */\n console.log(n);\n countdownBroken(n - 1); // Never stops!\n}\n\n// countdownBroken(5) will print:\n// 5, 4, 3, 2, 1, 0, -1, -2, -3, ... then CRASH!\n\n// ✅ CORRECT: Base case stops the recursion\nfunction countdownCorrect(n: number): void {\n /** This function terminates when n reaches 0. */\n if (n < 0) { // BASE CASE\n return; // Stop recursing\n }\n \n console.log(n);\n countdownCorrect(n - 1);\n}\n\n// countdownCorrect(5) prints: 5, 4, 3, 2, 1, 0 then stops gracefully","label":"TypeScript","value":"typescript"}]},"type":"code"},{"data":{"icon":"AlertCircle","title":"Stack Overflow Reality","content":"In most languages, the default call stack can hold only a few thousand frames. Python's default limit is about 1000; JavaScript/Node.js varies but is typically around 10,000-30,000. Without base cases, you hit these limits in milliseconds.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"systematic-approach","title":"The Systematic Approach to Finding Base Cases","content":[{"data":{"content":"$64"},"type":"text"},{"data":{"rows":[["Sum of array elements","Array","Empty array []","0 (nothing to sum)","if len(arr) == 0: return 0"],["Factorial n!","Integer n","n = 0 or n = 1","1","if n <= 1: return 1"],["Fibonacci F(n)","Integer n","n = 0 or n = 1","F(0)=0, F(1)=1","if n <= 1: return n"],["String reversal","String s","Empty string \"\"","\"\" (or single char)","if len(s) <= 1: return s"],["Binary search","Low/high indices","low > high","Not found (-1)","if low > high: return -1"],["Tree height","Node pointer","null / None","-1 or 0 (convention)","if node is None: return -1"]],"caption":"Base Case Identification Examples","headers":["Problem","Parameter","Smallest Input","Known Answer","Base Case Code"]},"type":"table"},{"data":{"icon":"Info","title":"The 'Edge Case = Base Case' Insight","content":"There's a deep connection between base cases and edge cases. The base cases of a recursive function are precisely the edge cases of the problem—the boundary conditions where special handling is required. If you've identified your edge cases, you've often identified your base cases.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"base-case-patterns","title":"Base Case Patterns by Problem Type","content":[{"data":{"content":"Different problem categories tend to have characteristic base case patterns. Recognizing these patterns accelerates your problem-solving.\n\n**Pattern 1: Numeric Countdown/Countup**\n\nProblems where a number decrements (or increments) toward a boundary.\n\n*Base case*: When the number reaches 0, 1, or some threshold.\n\n*Examples*: Factorial, power computation, counting steps"},"type":"text"},{"data":{"fileName":"numeric_patterns.py","languages":[{"code":"def power(base: float, exponent: int) -> float:\n \"\"\"Compute base^exponent using recursion.\"\"\"\n # BASE CASE: Any number to the power of 0 is 1\n if exponent == 0:\n return 1\n \n # RECURSIVE CASE: base^n = base × base^(n-1)\n return base * power(base, exponent - 1)\n\n# power(2, 4) = 2 * power(2, 3)\n# = 2 * (2 * power(2, 2))\n# = 2 * (2 * (2 * power(2, 1)))\n# = 2 * (2 * (2 * (2 * power(2, 0))))\n# = 2 * (2 * (2 * (2 * 1))) ← BASE CASE\n# = 16","label":"Python","value":"python"}]},"type":"code"},{"data":{"content":"**Pattern 2: Collection Decomposition**\n\nProblems where you process elements from an array, list, or string one at a time.\n\n*Base case*: When the collection is empty (or sometimes has one element).\n\n*Examples*: Sum of array, finding maximum, list reversal"},"type":"text"},{"data":{"fileName":"collection_patterns.py","languages":[{"code":"from typing import List\n\ndef find_max(arr: List[int]) -> int:\n \"\"\"Find the maximum element in an array recursively.\"\"\"\n # BASE CASE: Single element is its own maximum\n if len(arr) == 1:\n return arr[0]\n \n # RECURSIVE CASE: Compare first element with max of rest\n rest_max = find_max(arr[1:])\n return arr[0] if arr[0] > rest_max else rest_max\n\ndef sum_array(arr: List[int]) -> int:\n \"\"\"Sum all elements in an array recursively.\"\"\"\n # BASE CASE: Empty array has sum 0\n if len(arr) == 0:\n return 0\n \n # RECURSIVE CASE: First element + sum of rest\n return arr[0] + sum_array(arr[1:])\n\n# Note: sum_array([]) naturally returns 0\n# Note: find_max requires at least 1 element—would need error handling for []","label":"Python","value":"python"}]},"type":"code"},{"data":{"content":"**Pattern 3: Tree/Graph Traversal**\n\nProblems involving hierarchical or connected structures.\n\n*Base case*: When you reach a null/None pointer (no node exists) or a leaf node.\n\n*Examples*: Tree height, tree traversal, path finding"},"type":"text"},{"data":{"fileName":"tree_patterns.py","languages":[{"code":"class TreeNode:\n def __init__(self, val: int):\n self.val = val\n self.left: 'TreeNode | None' = None\n self.right: 'TreeNode | None' = None\n\ndef tree_height(node: TreeNode | None) -> int:\n \"\"\"\n Calculate the height of a binary tree.\n Height = longest path from root to any leaf.\n \"\"\"\n # BASE CASE: Empty tree (null node) has height -1\n # (Some define it as 0; -1 means a leaf has height 0)\n if node is None:\n return -1\n \n # RECURSIVE CASE: 1 + maximum height of subtrees\n left_height = tree_height(node.left)\n right_height = tree_height(node.right)\n return 1 + max(left_height, right_height)\n\ndef count_nodes(node: TreeNode | None) -> int:\n \"\"\"Count total nodes in a binary tree.\"\"\"\n # BASE CASE: Empty tree has 0 nodes\n if node is None:\n return 0\n \n # RECURSIVE CASE: 1 (this node) + nodes in left + nodes in right\n return 1 + count_nodes(node.left) + count_nodes(node.right)","label":"Python","value":"python"}]},"type":"code"},{"data":{"content":"**Pattern 4: Divide and Conquer**\n\nProblems where input is split into halves (or parts) for processing.\n\n*Base case*: When the input cannot be split further (size 0 or 1).\n\n*Examples*: Binary search, merge sort, quick sort"},"type":"text"},{"data":{"fileName":"divide_conquer_patterns.py","languages":[{"code":"$65","label":"Python","value":"python"}]},"type":"code"},{"data":{"icon":"Lightbulb","title":"Pattern Recognition Accelerates Design","content":"Once you recognize which pattern a problem fits, the base case often writes itself. 'This is a collection decomposition problem' immediately suggests 'empty collection is the base case.' Pattern recognition transforms design from invention to application.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"deriving-from-problem","title":"Deriving Base Cases from Problem Statements","content":[{"data":{"content":"Let's apply our systematic approach to a concrete problem, demonstrating how to extract base cases from a problem statement.\n\n**Problem: Count the number of ways to climb a staircase**\n\n*You are climbing a staircase with `n` steps. At each step, you can climb 1 or 2 steps at a time. In how many distinct ways can you reach the top?*\n\n**Step 1: Identify the Parameter**\n- `n`: the number of steps remaining to climb\n\n**Step 2: What's the Smallest Valid Input?**\n- `n = 0`: No steps remaining (you're at the top)\n- `n = 1`: One step remaining\n- (Could also consider `n < 0`: Went past the top—but this is an invalid state)\n\n**Step 3: What's the Answer for Each?**\n- `n = 0`: There's exactly **1 way** to reach the top from the top: do nothing. (This is crucial—the 'empty path' counts as one valid path)\n- `n = 1`: There's exactly **1 way**: climb 1 step\n\n**Step 4: Define the Base Cases**"},"type":"text"},{"data":{"fileName":"staircase_climbing.py","languages":[{"code":"$66","label":"Python","value":"python"},{"code":"$67","label":"TypeScript","value":"typescript"}]},"type":"code"},{"data":{"icon":"Info","title":"The 'n = 0 Means 1' Pattern","content":"Many counting problems have this counterintuitive base case: when there's 'nothing' to consider, the count is 1. This is consistent with mathematical conventions: the empty sum is 0, the empty product is 1, and the number of ways to partition nothing is 1. It makes the recurrence relations work out correctly.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"validating-base-cases","title":"Validating Your Base Cases","content":[{"data":{"content":"$68"},"type":"text"},{"data":{"fileName":"validation_examples.py","languages":[{"code":"$69","label":"Python","value":"python"}]},"type":"code"},{"data":{"items":["**Termination**: Every input path reaches a base case eventually","**Correctness**: Base case returns mathematically/logically correct values","**Completeness**: No edge cases slip through without handling","**Consistency**: Types and semantics align with recursive case expectations","**Minimality**: Base cases aren't more complex than necessary"],"title":{"icon":"CheckCircle","text":"Base Case Validation Checklist","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"titleType":"number","titleNumber":6},{"id":"common-base-values","title":"Common Base Case Values and Their Meanings","content":[{"data":{"content":"$6a"},"type":"text"},{"data":{"rows":[["Summation / Addition","0","Additive identity (x + 0 = x)","sum([]) = 0"],["Multiplication / Counting","1","Multiplicative identity (x × 1 = x)","factorial(0) = 1"],["Boolean AND / Universal","True","Vacuous truth","all([]) = True"],["Boolean OR / Existential","False","No evidence exists","any([]) = False"],["Finding maximum","−∞ (or first element)","Identity for max","max([]) → error or −∞"],["Finding minimum","+∞ (or first element)","Identity for min","min([]) → error or +∞"],["String concatenation","\"\" (empty string)","Concat identity (s + \"\" = s)","join([]) = \"\""]],"caption":"Base Case Value Selection Guide","headers":["Operation Type","Base Case Value","Mathematical Principle","Example"]},"type":"table"},{"data":{"icon":"Lightbulb","title":"Match the Identity to the Operation","content":"The key insight is that base cases should return the identity element for the operation used to combine recursive results. If you're adding, return 0. If you're multiplying, return 1. If you're ANDing, return True. This ensures the base case contributes 'neutrally' to the final answer.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"summary","title":"Summary: Mastering Base Case Identification","content":[{"data":{"content":"Base cases are the foundation upon which all recursive logic rests. Without them, recursion is just infinite descent. With them correctly designed, recursion becomes a powerful problem-solving technique."},"type":"text"},{"data":{"type":"ordered","items":["**Base cases are stopping conditions** — They define when recursion ends and direct answers are returned.","**Start with the smallest input** — Ask 'What is the simplest problem instance?' That's usually your base case.","**Base cases are ground truths** — They're facts you know without computation, not derived from recursion.","**Match values to operations** — Return 0 for addition, 1 for multiplication, True for universal statements.","**Validate rigorously** — Check termination, correctness, completeness, and consistency.","**Patterns accelerate design** — Recognize numeric countdown, collection decomposition, tree traversal, and divide-and-conquer patterns.","**Edge cases often reveal base cases** — The boundary conditions of your problem are frequently your base cases."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's Next:**\n\nNow that you understand how to identify a single, correct base case, the next page explores problems that require **multiple base cases**. Many real-world recursive functions need several stopping conditions, and designing them correctly requires additional care and technique."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now have a systematic framework for identifying correct base cases in recursive functions. This skill is fundamental—every recursive solution you write will depend on properly designed base cases. In the next page, we'll extend this foundation to handle problems requiring multiple base cases.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":8}],"isLocked":false},{"id":"seed_fb48fd576bf6abeddfa9cb355246b9f0","title":"Multiple Base Cases","order":1,"content":null,"isLocked":true},{"id":"seed_f7f4e2fe54e975965ac84813f0556817","title":"Ensuring Progress Toward the Base Case","order":2,"content":null,"isLocked":true},{"id":"seed_04f6b28d28da1b8f331574f2e66ce53e","title":"Common Mistakes: Missing or Wrong Base Cases","order":3,"content":null,"isLocked":true}]}},"dataUpdateCount":1,"dataUpdatedAt":1792309752877,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getModule"],{"input":{"slug":"base-cases-and-recursive-cases"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getModule\"],{\"input\":{\"slug\":\"base-cases-and-recursive-cases\"},\"type\":\"query\"}]"},{"dehydratedAt":1792309753039,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792309752875,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getProgress"],{"input":{"moduleId":"seed_850d92b5ec269917b761322ea7ef450e"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getProgress\"],{\"input\":{\"moduleId\":\"seed_850d92b5ec269917b761322ea7ef450e\"},\"type\":\"query\"}]"},{"dehydratedAt":1792309753039,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792309752875,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","get"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_fb48fd576bf6abeddfa9cb355246b9f0"},"type":"query"}],"queryHash":"[[\"feedback\",\"get\"],{\"input\":{\"contentId\":\"seed_fb48fd576bf6abeddfa9cb355246b9f0\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792309753039,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792309752875,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","getUserLike"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_fb48fd576bf6abeddfa9cb355246b9f0"},"type":"query"}],"queryHash":"[[\"feedback\",\"getUserLike\"],{\"input\":{\"contentId\":\"seed_fb48fd576bf6abeddfa9cb355246b9f0\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792309753039,"state":{"data":{"json":[]},"dataUpdateCount":1,"dataUpdatedAt":1792309752875,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["highlights","getHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_fb48fd576bf6abeddfa9cb355246b9f0"},"type":"query"}],"queryHash":"[[\"highlights\",\"getHighlights\"],{\"input\":{\"contentId\":\"seed_fb48fd576bf6abeddfa9cb355246b9f0\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792309753039,"state":{"data":"$undefined","dataUpdateCount":0,"dataUpdatedAt":0,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"pending","fetchStatus":"fetching"},"queryKey":[["highlights","getPopularHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_fb48fd576bf6abeddfa9cb355246b9f0","minCount":2},"type":"query"}],"queryHash":"[[\"highlights\",\"getPopularHighlights\"],{\"input\":{\"contentId\":\"seed_fb48fd576bf6abeddfa9cb355246b9f0\",\"contentType\":\"LEARNING_PAGE\",\"minCount\":2},\"type\":\"query\"}]","promise":"$@6b"}]},"children":"$L6c"}]