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

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

Fill the call table for sumTo(4).

Starter Chain

Use this shape for the node exercises:

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:

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

Coding Exercise 1: Count Nodes

Complete the helper.

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

  // TODO: recursive case
}

Check these cases:

Coding Exercise 2: Contains

Complete the helper.

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:

Coding Exercise 3: Count Matches

Complete the helper.

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:

Bug Fix Station

This function never reaches the missing-node base case:

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.