Chapter 3. Control Flow, Functions, Recursion, and Counting Operations

Learning objectives

After this chapter you should be able to:

Do unaided:

Write if, switch, while, do-while and for statements, and predict which branch runs and how often a loop body runs.
Write functions with prototypes, and explain why changing a parameter does not change the caller's variable.
Draw the call stack, one frame per call, for nested and recursive calls, including the deepest point of a recursion.
Trace a recursive function by hand, name its base case, and name the inputs that never reach it.
Compute how many times a line in a loop runs as a formula in n, and classify the count as 1, n, n² or input-dependent.

May delegate:

Asking the Drill maker for tracing and counting drills, answered before you see any solution.
Asking the tutor to explain a count you got wrong, after writing your own explanation.

Opening case

A composite case, not a real student or course.

Sam is writing the display code for the field station. Every minute, the small screen on the box should show the mean temperature since midnight. Sam reads one minute's sample with a function called sample and writes the loop the obvious way: at minute i, add up the samples for minutes 1 through i, then divide. It is Sam's first code that will run on the real box on the pole rather than on a laptop.

The chapter continues from here.

The loop in this chapter

Open a step to see what it asks of you and how it plays out in the Tutor phase.

Predictcounts for the three lab loops, as formulas and for n = 7, with confidence.

Step 1 of 6 · You, no AI

What you hand in: A written prediction: the output, the memory state, the operation count, and how sure you are.

Why this step: A prediction written before the run is the only way to learn whether your model of the machine is right. A miss is the most useful result there is, because it shows exactly where the model is wrong.

The first prediction is never delegated.

Ask yourself: What will this print, what will memory look like when it ends, and how many operations will it take?

Log the prediction in your work log · Predict in every chapter · ← Predict in Chapter 2 · Predict in Chapter 4 →
Writea recursive function by hand: stn_factorial (or a recursive helper for stn_ipow), overflow check first, with its stack drawing. You may submit a loop version instead (Section 3.1.9). PA1 begins.

Step 2 of 6 · You, no AI

What you hand in: One small piece written by hand, to build the mental model.

Why this step: You can only check what you could have built. Writing a small piece yourself gives you the model you will need to judge the agent's version later.

Ask yourself: Could I write this piece again tomorrow without notes?

Browse the companion code · Write in every chapter · ← Write in Chapter 2 · Write in Chapter 4 →
Specifya tutor question about one wrong count: your prediction, the counter's result, your explanation.

Step 3 of 6 · You

What you hand in: The header or class interface, unit tests, a complexity budget and the ownership rules.

Why this step: The specification is the contract the code will be held to. Tests written first, a cost budget and ownership rules turn "looks right" into something you can check.

Tutor In the Tutor phase you specify a question instead of code: what you want explained, quizzed or drilled.

The ownership and lifetime section of a specification is never delegated.

Ask yourself: Who allocates, who frees, what does it cost, and what input would break it?

Prompt and specification templates · Specify in every chapter · ← Specify in Chapter 2 · Specify in Chapter 4 →
Delegatethe tutor explains with questions and hints; no code.

Step 4 of 6 · The agent

What you hand in: The implementation from your specification, or an explanation in the Tutor phase, with the prompts and transcript saved.

Why this step: The agent does the typing; you keep the judgment. Saving the prompts and the transcript makes the delegation something you can audit afterward.

Tutor Tutor phase: the agent explains, quizzes and makes practice problems. It writes no code you submit.

Ask yourself: Did I hand over my specification and tests, and did I save what the agent said?

Prompt templates · Delegate in every chapter · ← Delegate in Chapter 2 · Delegate in Chapter 4 →
Auditthe counter, a gdb backtrace at the deepest call, and the sanitizer build on Table 3.5.

Step 5 of 6 · You and the tools

What you hand in: The Audit Report: tests, sanitizer and Valgrind output, your own cost derivation against a timing plot, the defects found, and a keep-or-rewrite decision.

Why this step: What the agent says is testimony until an instrument confirms it. Tests, sanitizers, Valgrind and a timing plot are evidence.

Tutor In the Tutor phase the audit checks the tutor's claims as well as your own code.

The final judgment that the code is correct is never delegated.

Ask yourself: What did the sanitizer report, does the timing plot match my derivation, and would I keep this code or rewrite it?

The Audit Report template · Audit in every chapter · ← Audit in Chapter 2 · Audit in Chapter 4 →
Defendexplain the count formula to the TA in two minutes.

Step 6 of 6 · You, live

What you hand in: A five-minute oral defense.

Why this step: If you can explain it live, you own it. The oral checks that the understanding is yours and not the agent's.

Ask yourself: Why this bound, what input breaks it, and where is this memory freed?

How the loop works · Defend in every chapter · ← Defend in Chapter 2 · Defend in Chapter 4 →

What agents get wrong here

Patterns observed in agent-written code, to test for, not guarantees. If the agent no longer makes the mistake, your job is to prove it got it right, with the same instrument.

A close but inexact operation count read from the loop header

How to catch it List trips for n = 1, 2, 3 by hand; add a counter

Section 3.3.1 · Your own trace

A base case that tests one value, so negative input never reaches it

How to catch it Edge tests (0, 1, negative, largest valid); ASan stack-overflow

Section 3.3.2 · AddressSanitizer, Tests

Returning the address of a local, or "fixing" it with static

How to catch it -Werror=return-local-addr; draw the frame; check for shared state

Section 3.3.3 · Compiler warnings, Your own trace

What the chapter covers

3.1 The concept, by hand
- 3.1.1 Choosing a path: if, else and switch
- 3.1.2 Repeating: while, do-while and for
- 3.1.3 Functions, prototypes and pass by value
- 3.1.4 Scope and lifetime
- 3.1.5 The stack frame, drawn
- 3.1.6 Recursion and the base case
- 3.1.7 When the stack runs out
- 3.1.8 Counting operations: 1, n, n² and "it depends on the input"
- 3.1.9 PA1 begins: the stn_math library
3.2 Predict and check: a recursion in gdb
3.3 What agents get wrong here
- 3.3.1 The off-by-one count
- 3.3.2 A base case that negative input skips
- 3.3.3 Returning the address of a local (preview)
3.4 Working with the agent
3.5 Lab: Count Before You Trust
3.6 Defend it

Cost thread

The unit of cost this week is the count of one chosen line. Sam's display made 1,037,520 flash reads a day instead of 1,440; keeping a running sum cuts it to 1,440, about 720 times fewer (Exercise 3.6).

Summary

Every call gets a stack frame with its parameters, locals and return address; on return the frame is popped and its locals die.
C passes arguments by value: the callee gets a copy, and nothing it does to the copy reaches the caller.
Scope is where a name is visible in the text; lifetime is when its storage exists. A static local has block scope and whole-run lifetime.
A correct recursion progresses toward its base case for every accepted input; otherwise, or when too deep, it overflows the stack.
Count one chosen line as a function of n: 1, n, n(n + 1)/2, n², or best and worst case. Check each formula on n = 1, 2, 3 and against a counter.
gdb's bt, frame and info locals confirm or correct your drawing; the drawing is the explanation.

Key terms

base case: the input a recursive function answers directly, without calling itself.
call stack: the memory holding one frame per unfinished call.
fall-through: in a switch, running into the next case because no break ended the current one.
lifetime: the part of a program's run during which a variable's storage exists.
operation count: the number of times a chosen line runs, as a function of the input size.
pass by value: copying each argument's value into a new parameter variable.
prototype: a function declaration stating its return and parameter types.
recursion: solving a problem by a function calling itself on a smaller instance.
return address: the point in the caller's code where execution resumes after a call.
scope: the part of the program text where a name can be used.
stack frame: the stack memory for one call: parameters, locals and return address.
stack overflow: a crash when the call stack exceeds its limit, usually from runaway or very deep recursion.
static local: a local variable declared static, initialized once and kept for the whole run.

Companion code

3 files for this chapter, compiled with the book's flags.

Read the code Download ch03.zip

Connections

Where this chapter and another point to each other most often.

Chapter 1: From Python to C: What Python Was Hiding
The loop's step, 2.5, is exact in binary (0.1 is not; Chapter 1).
Chapter 4: Pointers
A C function handed a double cannot reach your variable at all, unless you pass its address (Chapter 4). ### 3.1.4 Scope and lifetime > The scope of a name is the part of the program text where the name can be used.
Chapter 5: Arrays, Strings, and Matrices: n, n², n³
In Chapter 5 an agent-written version arrives for comparison only, and your Audit Report compares the two on negative input, zero, NaN, non-convergence, float equality and overflow.
Chapter 6: The Stack and the Heap: Dynamic Memory and Ownership
With an int parameter, the honest fix rejects n < 0; changing the base case to n <= 1 stops the crash but reports that (−3)! is 1. ### 3.3.3 Returning the address of a local (preview) This lifetime error needs pointers (Chapter 4), and Chapter 6 explains it fully.
Chapter 10: Complexity and Sorting: Your First Delegation
Table 3.4. Informal counts for the line you choose. | Shape of the code | Count | Double n, and the count… | |---|---|---| | No loop | 1 | stays the same | | One loop over n | n (or n/2, n + 1) | doubles | | Inner loop up to i | n(n + 1)/2 | about quadruples | | Two full nested loops | n² | quadruples | | Loop that can stop early | best and worst case | depends on the input | Chapter 10 turns these into Big-O.
Chapter 17: Binary Search Trees
Recursion earns its place when the problem's shape is recursive and the depth small, as with Chapter 17's trees. ### 3.1.7 When the stack runs out The stack has a limit.

See it on the map

03 Control Flow, Functions, Recursion, and Counting Operations