# L11: Recursion I: Self-Similar Problems

## Trace Before Coding

Recursion code is easier to write after you can name four parts:

1. Base case: the input that stops.
2. Smaller input: what changes in the recursive call.
3. Saved current work: the value this call must remember.
4. Combine step: how this call uses the smaller answer.

## Warm-Up Trace: sumTo

```ts
function sumTo(n: number): number {
  if (n <= 0) return 0;
  return n + sumTo(n - 1);
}
```

Fill the call table for `sumTo(4)`.

| call | base case? | smaller call | saved current work | returned value |
| --- | --- | --- | --- | --- |
| sumTo(4) | no | sumTo(___) | 4 | ___ |
| sumTo(3) | no | sumTo(___) | 3 | ___ |
| sumTo(2) | no | sumTo(___) | 2 | ___ |
| sumTo(1) | no | sumTo(___) | 1 | ___ |
| sumTo(0) | yes | none | none | ___ |

## Starter Chain

Use this shape for the node exercises:

```ts
type ListNode = { value: string; next?: ListNode };

const a: ListNode = { value: "hit" };
const b: ListNode = { value: "miss" };
const c: ListNode = { value: "hit" };

a.next = b;
b.next = c;
```

Draw the chain as:

```text
a("hit") -> b("miss") -> c("hit") -> end
```

## Coding Exercise 1: Count Nodes

Complete the helper.

```ts
function countNodes(node: ListNode | undefined): number {
  // TODO: base case

  // TODO: recursive case
}
```

Check these cases:

| input | expected output |
| --- | --- |
| undefined | 0 |
| c | 1 |
| a | 3 |

## Coding Exercise 2: Contains

Complete the helper.

```ts
function contains(node: ListNode | undefined, target: string): boolean {
  // TODO: base case for an empty chain

  // TODO: base case for a match at this node

  // TODO: recursive case that searches the smaller chain
}
```

Check these cases:

| input | target | expected output |
| --- | --- | --- |
| undefined | "hit" | false |
| a | "hit" | true |
| a | "miss" | true |
| a | "coin" | false |

## Coding Exercise 3: Count Matches

Complete the helper.

```ts
function countMatches(node: ListNode | undefined, target: string): number {
  // TODO: base case

  const here = node.value === target ? 1 : 0;
  // TODO: combine here with the smaller answer
}
```

Check these cases:

| input | target | expected output |
| --- | --- | --- |
| undefined | "hit" | 0 |
| c | "hit" | 1 |
| a | "hit" | 2 |
| a | "coin" | 0 |

## Bug Fix Station

This function never reaches the missing-node base case:

```ts
function brokenCount(node: ListNode | undefined): number {
  if (!node) return 0;
  return 1 + brokenCount(node);
}
```

1. Circle the recursive call.
2. Explain why the input is not smaller.
3. Write the corrected return line.
4. Add one check that proves the fixed function stops.

## Programming Challenge

Complete at least two coding exercises. For each one:

1. Fill the base case first.
2. Write the recursive call on the smaller input.
3. Trace one empty or missing case.
4. Trace one multi-node case.
5. Run or write the checks before moving on.


## Extra Practice Bank

- `reverseString(text: string): string`: return the characters in reverse order. Check `""`, `"a"`, and `"game"`.
- `countDigits(n: number): number`: count digits in a non-negative whole number. Decide and document why `countDigits(0)` should be `1`.
- `isPalindrome(text: string): boolean`: compare the first and last characters, then recurse on the middle. Check `""`, `"a"`, `"level"`, and `"game"`.
- Linked-list print forward: write `listToArrayForward(node: ListNode | undefined): string[]` so the output can be tested instead of read from the console.
- Linked-list print backward: write `listToArrayBackward(node: ListNode | undefined): string[]`; recurse to the end first, then add the current value as calls return.
- `getLast(node: ListNode | undefined): string | undefined`: return `undefined` for an empty chain and the final value for a non-empty chain.
- `countNodes` and `contains` variations: change the sample chain values and write expected outputs before running the helper.

## Common Bugs

- Forgetting the empty-chain base case.
- Calling the function again with the same node instead of `node.next`.
- Combining the current answer before checking whether the current node exists.