# 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:

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

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

| call | base case? | smaller calls | returned value |
| --- | --- | --- | --- |
| fib(4) | no | fib(___), fib(___) | ___ |
| fib(3) | no | fib(___), fib(___) | ___ |
| fib(2) | no | fib(___), fib(___) | ___ |
| fib(1) | yes | none | ___ |
| fib(0) | yes | none | ___ |

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.

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

  // TODO: base case for 1

  // TODO: combine two smaller recursive answers
}
```

Check these cases:

| input | expected output |
| --- | --- |
| 0 | 0 |
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 5 |

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)`.

```text
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.

```ts
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:

| steps | expected output | why |
| --- | --- | --- |
| 0 | 1 | one completed path |
| 1 | 1 | one 1-step move |
| 2 | 2 | 1+1 or 2 |
| 3 | 3 | 1+1+1, 1+2, or 2+1 |
| 4 | 5 | combine `countWays(3)` and `countWays(2)` |

## Bug Fix Station

This helper never gets closer to a base case:

```ts
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.