Why does `void swap(int a, int b) { int t = a; a = b; b = t; }` fail to swap its caller’s variables?

Because C copies the arguments, so the function modifies copies

Because the temporary variable t goes out of scope

Because C copies the arguments, so the function modifies copies

Because the function returns void

Because ints cannot be swapped without a pointer type

Which of the following are true about arrays and pointers in C? (More than one may be correct.)

a[i] and *(a + i) are equivalent by definition

A function receiving an array parameter cannot determine its length

a[i] and *(a + i) are equivalent by definition

An array name can be reassigned to point elsewhere

A function receiving an array parameter cannot determine its length

Adding memoisation to the naive recursive Fibonacci changes its time complexity from:

It does not change the complexity, only the constant

Programming in C, and Recursion

This is Section 4 of the Computer Science paper; if you sit a different paper, check your own syllabus before treating these chapters as yours. What makes this section different from the rest of the paper is that its questions are traces: you are given ten lines of C and asked what they print, or how many times a function is called. There is no formula to reach for, and the marks go to whoever can be a careful interpreter on paper. Three things account for most of the losses. C passes everything by value, always — there is no reference parameter, and a function that appears to modify its caller's variable is really receiving a copy of a pointer and writing through it, which is why swap(a, b) cannot work and swap(&a, &b) can. An array is not a pointer, even though a[i] is defined as *(a + i): the name of an array is not a modifiable object, sizeof reports the whole array rather than a pointer's width, and the two come apart the moment an array is passed to a function, where it decays to a pointer and the size information is gone. And recursion questions are almost always about counting, not about the returned value. The naive Fibonacci is the standard example precisely because its cost is so much worse than it looks: computing fib(5) makes 15 calls, fib(6) makes 25, and inside fib(6) the value fib(3) is recomputed three separate times — the redundancy that memoisation removes, and the reason the naive version is exponential while the iterative one is linear.

Pointers, Arrays, and What Is Actually Passed

Where an array and a pointer come apart
Expression	For `int a[10]`	For `int *p = a`
`a[i]` / `p[i]`	Both mean `(a + i)` — identical*	Same
`sizeof`	40 — the whole array	8 — a pointer
Assignment	`a = ...` is illegal	`p = ...` is fine
Passed to a function	Decays to `int ` — size is lost*	Already a pointer

🎯 Why C has no call by reference, and why it does not need one

Every argument in C is copied into the parameter. So a function receiving an int cannot change the caller's int, full stop. What looks like call by reference is call by value applied to an address: pass &x, and the function has a copy of the address, which is enough to write to the original object. This is the whole explanation of the classic swap question — swap(int a, int b) shuffles two copies and the caller sees nothing, while swap(int *a, int *b) works. The same reasoning explains why arrays appear to be passed by reference: the array decays to a pointer, the pointer is copied, and writes through it land in the caller's array. Nothing special is happening to arrays; only the decay is.

Recursion, Counted Rather Than Admired

The naive Fibonacci, counted exactly
n	Total calls to compute fib(n)	Closed form 2·F(n+1) − 1
2	3	2×2 − 1 = 3
4	9	2×5 − 1 = 9
5	15	2×8 − 1 = 15
6	25	2×13 − 1 = 25

🧠 Count the calls by drawing the tree, then read the redundancy off it

The recursion tree for fib(6) has fib(5) and fib(4) as children, fib(4) and fib(3) below fib(5), and so on — and the same subproblems appear on several branches. Inside fib(6), fib(3) is computed three separate times, fib(2) five times. That repetition is the exponential cost, and it is what memoisation deletes: storing each result the first time makes the work linear, because each of the n subproblems is solved once. The examinable version of this insight is usually a counting question rather than a complexity question, so the practical skill is drawing the tree and adding up nodes. A useful check on the arithmetic: the number of calls is always odd, because every internal node has exactly two children and the total is 2·F(n+1) − 1.

Two other recursions are worth having by heart. Tower of Hanoi takes 2ⁿ − 1 moves for n disks — 7 for three, 1023 for ten — from the recurrence T(n) = 2T(n−1) + 1. And the depth of the call stack is a separate question from the number of calls: fib(n) makes exponentially many calls but its stack is only n deep, because the branches are explored one at a time. A question asking for maximum stack depth wants the height of the tree, not its size.

Key takeaways

C passes everything by value; passing &x is call by value applied to an address.
a[i] is defined as *(a + i), but an array name is not assignable and sizeof reports the whole array.
An array passed to a function decays to a pointer and its size is lost.
Naive fib(n) makes 2·F(n+1) − 1 calls: 15 for n = 5, 25 for n = 6.
Inside fib(6), fib(3) is recomputed three times — that repetition is the exponential cost.
Memoisation makes the work linear because each of the n subproblems is then solved once.
Tower of Hanoi needs 2ⁿ − 1 moves, from T(n) = 2T(n−1) + 1.
Stack depth is the height of the recursion tree, not the number of calls — fib(n) is n deep.

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

The naive recursive Fibonacci is defined as fib(n) = n for n < 2, else fib(n−1) + fib(n−2). How many total calls to fib are made when computing fib(5), counting the initial call?
Numerical answer — type the value.
Show answer
Answer: 15
Drawing the recursion tree and counting nodes gives 15. The closed form is 2·F(n+1) − 1 where F is the Fibonacci sequence itself: F(6) = 8, so 2×8 − 1 = 15, and the same formula gives 25 for fib(6) and 9 for fib(4). Two checks catch most errors: the count is always odd, because every internal node has exactly two children; and it is far larger than n, which is the point — the number of distinct subproblems is only 6, and everything above that is recomputation.
For int a[10]; on a machine with 4-byte ints and 8-byte pointers, sizeof(a) and sizeof(&a[0]) are respectively:
1. 40 and 8
2. 8 and 8
3. 40 and 40
4. 10 and 8
Show answer
Answer: A — 40 and 8
sizeof(a) asks for the size of the whole array object: 10 × 4 = 40 bytes. &a[0] is a pointer to int, so its size is the pointer width, 8. This is the sharpest place where an array and a pointer differ, and it is why a function receiving an array cannot compute its length — inside the function the parameter really is a pointer and sizeof returns 8. Option B is what a candidate answers by believing "an array is a pointer"; option D counts elements instead of bytes, which sizeof never does.
Why does void swap(int a, int b) { int t = a; a = b; b = t; } fail to swap its caller’s variables?
1. Because the temporary variable t goes out of scope
2. Because C copies the arguments, so the function modifies copies
3. Because the function returns void
4. Because ints cannot be swapped without a pointer type
Show answer
Answer: B — Because C copies the arguments, so the function modifies copies
C has exactly one parameter-passing mechanism: the argument is copied into the parameter. So a and b inside the function are new objects, the swap happens correctly to them, and the caller's variables were never touched. The fix is to pass addresses — swap(int *a, int *b) with *a/*b inside — which is not a different mechanism but the same copying applied to pointer values. Option A is a real fact about t and irrelevant to the failure; the swap would fail identically if t were static. Option C confuses the return value with the parameters, and nothing about void prevents a function from writing through a pointer.
How many moves does the Tower of Hanoi require for 10 disks?
Numerical answer — type the value.
Show answer
Answer: 1023
The recurrence is T(n) = 2T(n−1) + 1 with T(1) = 1 — move n−1 disks across, move the largest, move the n−1 back — which solves to 2ⁿ − 1, so 2¹⁰ − 1 = 1023. The commonest wrong answer is 1024, from remembering the power and dropping the −1; the −1 is real and easy to see at n = 1, where the formula must give 1 rather than 2. Note also that the number of moves is exponential while the recursion depth is only 10, which is the distinction the next question turns on.
Computing naive fib(20) makes tens of thousands of calls. The maximum depth of the call stack during that computation is:
1. About 2²⁰
2. 20
3. Equal to the number of calls
4. About 13529
Show answer
Answer: B — 20
Stack depth is the height of the recursion tree, not its size. The deepest chain is fib(20) → fib(19) → … → fib(1), so the depth is about 20, even though the number of calls is 2·F(21) − 1 = 21,891. The reason is that the two recursive branches are explored one after the other, not simultaneously: when the left subtree returns, its frames are gone before the right subtree begins. This is why a naive Fibonacci is a time disaster and not a space one, and it is the standard way a question separates the two costs. Options A and D confuse size with height.
Which of the following are true about arrays and pointers in C? (More than one may be correct.)
1. a[i] and *(a + i) are equivalent by definition
2. An array name can be reassigned to point elsewhere
3. A function receiving an array parameter cannot determine its length
4. i[a] is a syntax error
Show answer
Answer: A — a[i] and *(a + i) are equivalent by definition; C — A function receiving an array parameter cannot determine its length
A and C. Subscripting is defined as pointer arithmetic, so a[i] means *(a + i) (A) — and since addition commutes, i[a] means *(i + a), which is the same thing and perfectly legal, so D is false and is a favourite trick question. C is true and follows from the decay rule: the parameter is a pointer, sizeof gives the pointer width, and the length has to be passed separately — which is why every C library function taking an array also takes a count. B is false: an array name is not a modifiable lvalue, which is the other half of "an array is not a pointer".
Adding memoisation to the naive recursive Fibonacci changes its time complexity from:
1. Exponential to linear
2. Exponential to logarithmic
3. Linear to constant
4. It does not change the complexity, only the constant
Show answer
Answer: A — Exponential to linear
The naive version is exponential because subproblems are recomputed — fib(3) three times inside fib(6), and far worse higher up. Memoisation stores each result the first time it is produced, so each of the n distinct subproblems is solved exactly once and every later request is a lookup: the work becomes linear in n. Option B is what a candidate reaches for by association with divide-and-conquer, but nothing here halves the problem — there are n subproblems and each is O(1) given its predecessors. Note the space cost that comes with it: O(n) for the table, where the naive version used only O(n) stack, so memoisation trades nothing away here, which is unusual and worth noticing.
Inside the naive computation of fib(6), how many times is fib(3) evaluated?
1. Once
2. Twice
3. Three times
4. Five times
Show answer
Answer: C — Three times
Three times. fib(6) calls fib(5) and fib(4); fib(5) calls fib(4) and fib(3); each fib(4) calls fib(3) and fib(2). So fib(3) is reached once directly from fib(5) and once from each of the two fib(4) calls — three in all. Tracing this by hand is the skill the question is testing, and the general pattern is worth seeing: the number of times fib(k) is evaluated inside fib(n) is itself a Fibonacci number, which is why the redundancy grows so fast. fib(2), by the same count, is evaluated five times.