L13: Recursion III: Branching Search

Branching Recursion Rule

Branching recursion means one call can ask for two or more smaller answers.

Before coding, name:

1. Success base case.
2. Failure base case.
3. Smaller calls.
4. Combine step.

Trace First: Fibonacci Shape

The Fibonacci sequence uses two previous values:

fib(0) = 0
fib(1) = 1
fib(n) = fib(n - 1) + fib(n - 2)

Fill the trace for fib(4) before writing code.

Circle one repeated call in the tree. That repeat is why Fibonacci is a good warning example for branching recursion.

Coding Exercise 1: Fibonacci

Complete the helper.

function fib(n: number): number {
  // TODO: base case for 0

  // TODO: base case for 1

  // TODO: combine two smaller recursive answers
}

Check these cases:

Do not add memoization yet. First make the recursive meaning correct.

Trace Second: Count Stair Ways

You can climb stairs using either 1-step or 2-step moves.

Draw a two-level tree for countWays(4).

countWays(4)
|- take 1 step -> countWays(3)
|- take 2 steps -> countWays(2)

Mark each leaf as:

• one complete path when the remaining steps are 0
• zero paths when the remaining steps are below 0
• keep branching when the remaining steps are positive

Coding Exercise 2: Count Stair Ways

Complete the helper.

function countWays(steps: number): number {
  // TODO: base case for exactly reaching the top

  // TODO: base case for stepping past the top

  // TODO: combine the one-step and two-step branches
}

Check these cases:

Bug Fix Station

This helper never gets closer to a base case:

function brokenFib(n: number): number {
  if (n < 2) return n;
  return brokenFib(n) + brokenFib(n - 1);
}

1. Circle the recursive call that does not get smaller.
2. Write the corrected return line.
3. Add one check that would fail or hang before the fix.

Programming Challenge

Complete both coding exercises. For each one:

1. Write the base cases first.
2. Write the smaller recursive calls.
3. Trace one input that reaches a base case quickly.
4. Trace one input that branches.
5. Run or write the checks before moving on.

Extra Practice Bank

• solveMaze(grid, row, col, visited): boolean: branch up, down, left, and right. Base cases should handle out-of-bounds, walls, already-visited cells, and the goal.
• permutations(text: string): string[]: choose each character as the first character, then recurse on the remaining characters.
• isValidParentheses(text: string): boolean: write a recursive helper that tracks the current index and open count. Stop with success only when the index is at the end and open count is 0.
• Maze trace: draw a 4-by-4 grid, mark walls and goal, then trace which branches fail before one branch succeeds.
• Permutation trace: trace permutations("abc") as a tree of choices before coding.
• Parentheses trace: predict "()", "(())", "(()", and ")(" before writing the helper.

Common Bugs

• Forgetting one of the Fibonacci base cases.
• Returning 0 for countWays(0) instead of one completed path.
• Calling the function again with the same input instead of smaller inputs.

Bonus Puzzles

• Add memoization as a labeled experiment after the plain version works.
• Change the stair moves to 1, 2, or 3 steps and write new tests.