w-01-recursion-call-stack.yml · YAML

# Recursion call stack: chapter 0.2 worked example: factorial(n).
# Animates the push/base/pop trace of a linear recursion so the reader sees
# the call stack as a physical artifact (frames pushed, base case fires,
# frames pop with deferred multiplications running in reverse).

id: w-01-recursion-call-stack
title: "Recursion call stack (factorial; three-shapes comparison)"
type: dual-panel-shared
level: 1
modes: [preset, edit]

caps:
  n: { min: 0, max: 8 }
  # Hard cap n=8 keeps step count <= 25 (1 init + 8 push + 1 base + 8 pop + 1 done = 19 steps).

commands:
  - name: pushFrame
    payload: { name: 'string', n: 'integer' }
    description: "Push a new frame onto the stack. Active highlight moves to the new top."
  - name: baseCase
    payload: { name: 'string', returns: 'integer' }
    description: "Active frame matches the base-case predicate. Highlight switches to bluish-green; frame returns its constant answer."
  - name: popFrame
    payload: { name: 'string', computed: 'string', returns: 'integer' }
    description: "Top frame returns. Pop the stack; the frame below resumes with the returned value and runs its deferred combine step."
  - name: done
    payload: { answer: 'integer' }
    description: "Last frame popped. Stack empty; final answer displayed."

static_fallback:
  generator: jsdom
  output: site/static/widgets/w-01-recursion-call-stack-fallback.svg
  keyframes_used: [0, 5, 6, 11]
  # Four stills: empty stack at start; full 5-frame stack just before base case;
  # base-case highlight (orange + bluish-green); final unwound state.

panels:
  default:
    chapter: "0.2"
    label: "factorial(n) call stack"
    canonical_input: |
      n = 4
    presets:
      - id: canonical
        label: "Canonical (n = 4)"
        input: { n: 4 }
      - id: immediate-base
        label: "Immediate base case (n = 0)"
        input: { n: 0 }
      - id: deeper-stack
        label: "Deeper stack (n = 6)"
        input: { n: 6 }
    n_steps: 12
    # Trace generated by hand-tracing the verified Python reference at
    # content/dsa/part-0-foundations/02-recursion-mental-model/sol.py against n=4.
    # Re-running the function on the same input produces an identical step
    # sequence (no randomness, no time-dependent state).
    keyframes:
      - step: 0
        kind: init
        state: { stack: [], active: null, n: 4 }
        narration: "About to call factorial(4). The call stack is empty."
      - step: 1
        kind: pushFrame
        payload: { name: "f(4)", n: 4 }
        state: { stack: ["f(4)"], active: "f(4)", n: 4 }
        narration: "Push frame f(4). n = 4 is not the base case; recurse on n - 1 = 3."
      - step: 2
        kind: pushFrame
        payload: { name: "f(3)", n: 3 }
        state: { stack: ["f(4)", "f(3)"], active: "f(3)", n: 3 }
        narration: "Push frame f(3). n = 3 is not the base case; recurse on n - 1 = 2."
      - step: 3
        kind: pushFrame
        payload: { name: "f(2)", n: 2 }
        state: { stack: ["f(4)", "f(3)", "f(2)"], active: "f(2)", n: 2 }
        narration: "Push frame f(2). n = 2 is not the base case; recurse on n - 1 = 1."
      - step: 4
        kind: pushFrame
        payload: { name: "f(1)", n: 1 }
        state: { stack: ["f(4)", "f(3)", "f(2)", "f(1)"], active: "f(1)", n: 1 }
        narration: "Push frame f(1). n = 1 is not the base case; recurse on n - 1 = 0."
      - step: 5
        kind: pushFrame
        payload: { name: "f(0)", n: 0 }
        state: { stack: ["f(4)", "f(3)", "f(2)", "f(1)", "f(0)"], active: "f(0)", n: 0 }
        narration: "Push frame f(0). About to check the base-case condition."
      - step: 6
        kind: baseCase
        payload: { name: "f(0)", returns: 1 }
        state: { stack: ["f(4)", "f(3)", "f(2)", "f(1)", "f(0)"], active: "f(0)", n: 0, returns: 1 }
        narration: "Base case reached: factorial(0) returns 1. Recursion terminates; the stack starts unwinding."
      - step: 7
        kind: popFrame
        payload: { name: "f(0)", computed: "1 * 1 = 1", returns: 1 }
        state: { stack: ["f(4)", "f(3)", "f(2)", "f(1)"], active: "f(1)", returns: 1 }
        narration: "Pop f(0). f(1) computes 1 * 1 = 1 and returns 1."
      - step: 8
        kind: popFrame
        payload: { name: "f(1)", computed: "2 * 1 = 2", returns: 2 }
        state: { stack: ["f(4)", "f(3)", "f(2)"], active: "f(2)", returns: 2 }
        narration: "Pop f(1). f(2) computes 2 * 1 = 2 and returns 2."
      - step: 9
        kind: popFrame
        payload: { name: "f(2)", computed: "3 * 2 = 6", returns: 6 }
        state: { stack: ["f(4)", "f(3)"], active: "f(3)", returns: 6 }
        narration: "Pop f(2). f(3) computes 3 * 2 = 6 and returns 6."
      - step: 10
        kind: popFrame
        payload: { name: "f(3)", computed: "4 * 6 = 24", returns: 24 }
        state: { stack: ["f(4)"], active: "f(4)", returns: 24 }
        narration: "Pop f(3). f(4) computes 4 * 6 = 24 and returns 24."
      - step: 11
        kind: done
        payload: { answer: 24 }
        state: { stack: [], active: null, answer: 24 }
        narration: "Pop f(4). Final answer: factorial(4) = 24."
  three_shapes:
    chapter: "7.0"
    label: "Three shapes side-by-side: linear, tree, divide-and-conquer"
    canonical_input: |
      linear: fib_linear(3); tree: fib_tree(3); dnc: merge_sort([3, 1, 2])
    presets:
      - id: canonical
        label: "Canonical (n=3 / n=3 / [3,1,2])"
        input:
          linear: { n: 3 }
          tree:   { n: 3 }
          dnc:    { nums: [3, 1, 2] }
      - id: tree-deeper
        label: "Tree deeper (n=4)"
        input:
          linear: { n: 3 }
          tree:   { n: 4 }
          dnc:    { nums: [3, 1, 2] }
      - id: dnc-larger
        label: "D&C larger ([4,1,3,2])"
        input:
          linear: { n: 3 }
          tree:   { n: 3 }
          dnc:    { nums: [4, 1, 3, 2] }
    n_steps: 30
    # Step buffer source: research/dsa/part-7-recursion-backtracking/00-recursion-patterns.md §4
    # Trace generated deterministically against the verified §2.2 Python reference;
    # re-running the function on the same input produces an identical event sequence.
    keyframes:
      - step: 0
        kind: pushFrame
        panel: linear
        payload: { name: "fib_linear(3)", n: 3, a: 0, b: 1 }
        narration: "Linear: push frame for n=3."
      - step: 1
        kind: pushFrame
        panel: linear
        payload: { name: "fib_linear(2)", n: 2, a: 1, b: 1 }
        narration: "Linear: push frame for n=2."
      - step: 2
        kind: pushFrame
        panel: linear
        payload: { name: "fib_linear(1)", n: 1, a: 1, b: 2 }
        narration: "Linear: push frame for n=1."
      - step: 3
        kind: pushFrame
        panel: linear
        payload: { name: "fib_linear(0)", n: 0, a: 2, b: 3 }
        narration: "Linear: push frame for n=0; base case will fire next."
      - step: 4
        kind: popFrame
        panel: linear
        payload: { returns: 2 }
        narration: "Linear: base case returns 2."
      - step: 5
        kind: popFrame
        panel: linear
        payload: { returns: 2 }
        narration: "Linear: tail return propagates."
      - step: 6
        kind: popFrame
        panel: linear
        payload: { returns: 2 }
        narration: "Linear: tail return propagates."
      - step: 7
        kind: popFrame
        panel: linear
        payload: { returns: 2 }
        narration: "Linear: final answer 2. Total 8 events; depth 3."
      - step: 8
        kind: pushFrame
        panel: tree
        payload: { name: "fib_tree(3)", n: 3 }
        narration: "Tree: push frame for n=3."
      - step: 9
        kind: pushFrame
        panel: tree
        payload: { name: "fib_tree(2)", n: 2 }
        narration: "Tree: recurse on n-1=2."
      - step: 10
        kind: pushFrame
        panel: tree
        payload: { name: "fib_tree(1)", n: 1 }
        narration: "Tree: left child recurses on n-1=1."
      - step: 11
        kind: popFrame
        panel: tree
        payload: { returns: 1 }
        narration: "Tree: base case returns 1."
      - step: 12
        kind: pushFrame
        panel: tree
        payload: { name: "fib_tree(0)", n: 0 }
        narration: "Tree: right child recurses on n-2=0."
      - step: 13
        kind: popFrame
        panel: tree
        payload: { returns: 0 }
        narration: "Tree: base case returns 0."
      - step: 14
        kind: popFrame
        panel: tree
        payload: { returns: 1 }
        narration: "Tree: fib_tree(2) = 1 + 0 = 1."
      - step: 15
        kind: pushFrame
        panel: tree
        payload: { name: "fib_tree(1)", n: 1 }
        narration: "Tree: fib_tree(3) recurses on its second child fib_tree(1)."
      - step: 16
        kind: popFrame
        panel: tree
        payload: { returns: 1 }
        narration: "Tree: base case returns 1 (recomputed)."
      - step: 17
        kind: popFrame
        panel: tree
        payload: { returns: 2 }
        narration: "Tree: fib_tree(3) = 1 + 1 = 2. Total 10 events; depth 2 max."
      - step: 18
        kind: pushFrame
        panel: dnc
        payload: { name: "merge_sort([3,1,2])", nums: [3, 1, 2] }
        narration: "D&C: enter merge_sort([3,1,2])."
      - step: 19
        kind: pushFrame
        panel: dnc
        payload: { name: "merge_sort([3])", nums: [3] }
        narration: "D&C: left half is the singleton [3] (base case)."
      - step: 20
        kind: popFrame
        panel: dnc
        payload: { returns: [3] }
        narration: "D&C: singleton returns [3]."
      - step: 21
        kind: pushFrame
        panel: dnc
        payload: { name: "merge_sort([1,2])", nums: [1, 2] }
        narration: "D&C: right half splits further."
      - step: 22
        kind: pushFrame
        panel: dnc
        payload: { name: "merge_sort([1])", nums: [1] }
        narration: "D&C: singleton."
      - step: 23
        kind: popFrame
        panel: dnc
        payload: { returns: [1] }
        narration: "D&C: returns [1]."
      - step: 24
        kind: pushFrame
        panel: dnc
        payload: { name: "merge_sort([2])", nums: [2] }
        narration: "D&C: singleton."
      - step: 25
        kind: popFrame
        panel: dnc
        payload: { returns: [2] }
        narration: "D&C: returns [2]."
      - step: 26
        kind: merge
        panel: dnc
        payload: { left: [1], right: [2], result: [1, 2] }
        narration: "D&C: combine step merges [1] + [2] into [1,2]."
      - step: 27
        kind: popFrame
        panel: dnc
        payload: { returns: [1, 2] }
        narration: "D&C: right-half merge returns [1,2]."
      - step: 28
        kind: merge
        panel: dnc
        payload: { left: [3], right: [1, 2], result: [1, 2, 3] }
        narration: "D&C: top-level combine merges [3] + [1,2] into [1,2,3]."
      - step: 29
        kind: popFrame
        panel: dnc
        payload: { returns: [1, 2, 3] }
        narration: "D&C: final answer [1,2,3]. Total 12 events; depth 2."

# Default interaction model (DSH-18: no widget autoplays on page load).
default_state: paused-at-step-0
controls:
  primary: [step-forward, step-back, reset]
  secondary: [play-pause, speed]

accessibility:
  prefers_reduced_motion: static-keyframes-only
  aria_live: polite           # announces each step's `narration` field
  keyboard_shortcuts:
    step_forward: ArrowRight
    step_back: ArrowLeft
    reset: r
    play_pause: Space

# Wong palette tokens (Nature Methods 2011).
# No naked red/green pairs.
palette:
  active_frame: var(--wong-orange)        # the frame currently executing
  base_case_hit: var(--wong-bluish-green) # the moment factorial(0) returns 1
  popped_frame: var(--wong-blue)          # frames that have returned
  default_frame: var(--wong-black)        # frames pending on the stack

selector_default: default


notes: |
  Panel-a (chapter 0.2) animates a single linear-recursion call stack on
  factorial(n). The widget IS the worked example for that chapter; steps 5-7
  in panel-a are the load-bearing moments (full stack, base case fires, first
  pop with deferred multiplication). The trace matches the Python reference
  at content/dsa/part-0-foundations/02-recursion-mental-model/sol.py.

  Panel-b (chapter 7.0) shows three call-stack panels side-by-side: linear,
  tree, divide-and-conquer: at small canonical inputs (fib_linear(3),
  fib_tree(3), merge_sort([3,1,2])). The 30-event sequence (8 + 10 + 12) lets
  the reader see the three SHAPES of recursion as physically distinct stack
  behaviors: a chain that pushes then pops, a tree whose siblings push and
  pop independently, a balanced split with explicit merge events on the way
  up. Trace matches the Python reference at
  content/dsa/part-7-recursion-backtracking/00-recursion-patterns/sol.py.