#3. Hypothesis-Induction-Base Condition

Study notes from Aditya Verma's recursion playlist, video 3. The framework and the framing are his — this is my write-up for revision. Watch the original; these notes are no substitute for it.

Playlist: https://www.youtube.com/playlist?list=PL_z_8CaSLPWeT1ffjiImo0sYTcnLzo-wY

⚠️ Built from a timestamped AI summary of the video, not from watching it. The framework, its ordering, and the decision rule are consistent across the summary and the video's own title, so they are solid. Fine detail should still be checked. Timestamps are given so you can jump straight to any claim.

🎯 This is the video that settles the open question raised in video 2's notes: are the tree method and IBH one framework or two? They are two, and this video gives the rule for choosing. See §5.

#1 · The framework — 2:17 to 6:30

Three steps, and the order in the title is the order you apply them in:

The base condition is defined as the smallest invalid input, not the smallest valid one. For printing 1 to N, that is n == 0 — not n == 1. This framing is more reliable than "the smallest case I can answer", because you do not have to decide what the answer is, only where to stop.

"Recursion works like magic." The hypothesis step is the magic: you assume the function works on the smaller input without checking. That assumption is the entire method — and refusing to make it is why people find recursion hard.

The other repeated phrase is "input smaller" — the whole move is: make the input smaller, hand it to yourself, do one step with what comes back.

#2 · The worked example — 6:30 to 13:10

Print 1 to N, demonstrated with n = 7.

HYPOTHESIS   assume print(n-1) correctly prints 1 .. n-1
INDUCTION    so call print(n-1) first, then print n
BASE         if n == 0, return          <- smallest INVALID input

print(7)
  print(6)
    print(5)
      ...
        print(1)
          print(0)   -> base, returns immediately
          prints 1                        <- work happens on the way BACK UP
        prints 2
      ...
  prints 7

output: 1 2 3 4 5 6 7

void print(int n) {
    if (n == 0) return;      // base condition -- smallest invalid input
    print(n - 1);            // hypothesis -- trust that this prints 1..n-1
    cout << n << " ";        // induction  -- the one step for THIS n
}

def print_1_to_n(n):
    if n == 0:                 # base condition
        return
    print_1_to_n(n - 1)        # hypothesis -- trust it
    print(n, end=" ")          # induction -- one step, on the way up

The line order is the entire lesson. Put print(n) before the recursive call and you get 7 down to 1; put it after and you get 1 up to 7. Same three lines, opposite output — because code before the call runs on the way down and code after it runs on the way back up.

#3 · The recursion tree here is a chain — 13:10 to 16:50

Worth noticing, because it differs from the subsets tree:

IBH problems              CHOICE problems
  n                            []
  |                          /    \
 n-1                      take   skip
  |                        / \    / \
 n-2                     ...  ... ... ...
  |
 ...                     a BRANCHING tree -- 2^n nodes
  |
  0                      each level makes a DECISION

a CHAIN -- n nodes
no decision at any level,
only reduction

There is no choice being made at any level here. That is precisely why the input–output tree method does not apply, and why a separate framework exists. If you catch yourself trying to draw two branches for "sort an array", that is the signal you are in the wrong framework.

The return path is what produces the output — the printing happens as the stack unwinds, not as it builds.

#4 · The warnings

Both are worth taking seriously.

The second is the one that bites beginners. The instinct on seeing print(n-1) is to unroll it mentally into an iteration — and that is exactly the tracing habit that makes recursion feel impossible. Trust the hypothesis instead.

#5 · The decision rule — which framework, when

This answers the question left open in video 2.

Draw the tree if you can see it. Use IBH when you cannot.

So they are not two disjoint problem categories. IBH is a fallback method for when the tree is not apparent — which is a more practical rule than sorting problems into two bins up front.

This corrects my recursion page. That page presents the two as parallel frameworks selected by problem type ("can I see choices?" versus "can I reduce the input?"). His actual rule is sequential: try to see the tree; if you can't, fall back to IBH. The distinction matters, because under my version you might reject IBH for a problem that has choices — under his, IBH is always available when you are stuck.

#6 · Problems named for later

All three are the same reduce-and-rebuild shape as the worked example.

#7 · Triage — if you are short on time

Watch 7:10–10:10 first. The rest is framing you can pick up afterwards.

#8 · What tripped me up

Fill this in as you solve — this is the part that pays off later.

#9 · Problems to do

#Stop condition

I have got this video when I can:

1. name the three steps in the order they are applied,
2. define the base condition as the smallest invalid input and say why that framing is easier,
3. write print-1-to-N and print-N-to-1 by moving one line,
4. explain why this tree is a chain and not a branching tree, and
5. state the decision rule: draw the tree if you can see it, use IBH when you cannot.