The shape of the lesson
By the end of the lesson, learners can
- The three features: Factorial is the classic first example: 4! = 4 × 3 × 2 × 1, and 4! = 4 × 3!.
- Winding and unwinding: Where the work happens matters.
- What the compiler does: Recursion only works because each call gets its own copy of its parameters and local variables, and remembers where to return to.
- Features: calls itself; a base case that stops; a general case that moves towards it.
- Trace: one row per call; fill in its result only when the call it made returns.
- Compiler: a stack frame per call (return address, parameters, locals); popped on return.
- Judge: shorter and clearer for recursive problems; more memory and stack overflow risk.
One picture every idea returns to
A recursive subroutine is one that is defined in terms of itself: it calls itself. It must have a base case, a condition where it returns a result without calling itself, and a general (recursive) case that calls itself with a value that moves closer to the base case. Each call is placed on the call stack as a stack frame holding its return address, parameters and local variables. When the base case is reached the calls return one by one in reverse order: the stack unwinds. With no reachable base case the stack fills up: stack overflow.
Forty-five minutes, phase by phase
| Time | Phase | What happens in the room | Grouping |
|---|---|---|---|
| 0 to 5 min | Hook: predict | Open with the question in the title, It calls itself.. A recursive subroutine solves a problem by calling itself on a smaller version of the same problem until it reaches a case it can answer directly. Put the figure on the board: it is the one picture every idea in the lesson returns to. | Whole class, then pairs |
| 5 to 13 min | Teach and check: The three features | Factorial is the classic first example: 4! = 4 × 3 × 2 × 1, and 4! = 4 × 3!. Model the worked example Trace Factorial(4) on the board, one line at a time. Your turn: Power(Base, Exp) returns 1 if Exp = 0, otherwise Base * Power(Base, Exp - 1). How many calls are made by Power(3, 4), and what is returned? | Whole class, then pairs |
| 13 to 21 min | Teach and check: Winding and unwinding | Where the work happens matters. Project tab 4 of the lab (Binary tree traversals) and let a student drive it while the class predicts. Model the worked example Trace Mystery(13) on the board, one line at a time. Your turn: A procedure Show(n) does: IF n > 0 THEN OUTPUT n, CALL Show(n - 2), OUTPUT n * 10, ENDIF. What is output by CALL Show(5)? | Pairs |
| 21 to 30 min | Teach and check: What the compiler does | Recursion only works because each call gets its own copy of its parameters and local variables, and remembers where to return to. Model the worked example Count the calls on the board, one line at a time. Your turn: Write an iterative version of Factorial, and state one advantage it has over the recursive version. | Corners |
| 30 to 36 min | Check | The four Stage 1 questions from the student lesson, answered on mini whiteboards or by show of fingers. Re-teach the one most get wrong. | Individual, then whole class |
| 36 to 43 min | Plenary | The exam-style questions from Stage 2, one at a time: thirty seconds alone, then a random call. The feedback lines in the key give the examiner's wording. | Individual, random call |
| 43 to 45 min | Exit and homework | Set the worksheet below (6 questions, 23 marks). Learners self-assess against the objectives before they leave. | Individual |
Protect the parts that carry the learning
The sequence carries about fifty minutes of material, so the lab is driven by one student while the class predicts rather than explored freely. Times are a guide.
Protected: the check at 30 minutes. It is the only individual read on whether the key idea landed, and it is not cut.
Cut first if the build overruns: the last check in What the compiler does, never the check or the plenary.
In a 60 minute block: run worksheet questions 1 to 3 in class as a Rally Coach set and model both the hardest worked example and its check live.
Corners
Put one answer or viewpoint in each corner of the room. Students move to the corner they agree with, justify the choice to a partner there, then hear one voice from each corner before the reveal.
The full structure, with its variations and the other twelve, is on the cooperative-learning page.
What to head off, and how
| Trap learners fall into | Teaching move that pre-empts it |
|---|---|
| A base case that is never reached is as bad as none. | Factorial(−1) calls Factorial(−2), then −3,... and never meets n = 0, so the stack overflows. State that each call must move towards the base case. |
| In a trace, do not output a value when a call is made if the OUTPUT is after the recursive call. | Write each call on a new row, and fill in its output only when control returns to it. |
| "Recursion is faster" is usually wrong. | A recursive solution is often shorter and clearer, but it normally uses more memory and more time than an equivalent loop because of the stack frames. |
Recursion and the call stack: worksheet
6 questions, 23 marks. Written in the style of the papers; no past paper question is reproduced.
State the three essential features of a recursive subroutine.
Trace the function below for DigitSum(4721), showing each call, the value it waits for and the value it returns.
FUNCTION DigitSum(n : INTEGER) RETURNS INTEGER
IF n < 10 THEN
RETURN n
ELSE
RETURN (n MOD 10) + DigitSum(n DIV 10)
ENDIF
ENDFUNCTIONData : ARRAY[1:100] OF INTEGER is a global array in ascending order. Write pseudocode for a recursive function RBinarySearch(Target : INTEGER, Low : INTEGER, High : INTEGER) RETURNS INTEGER that returns the index of Target, or −1 if it is not present. It is first called as RBinarySearch(Target, 1, 100).
The array in the binary search lesson holds 3, 8, 12, 17, 21, 26, 30, 34, 39, 42, 47, 51, 58, 63, 70 in elements 1 to 15. For your function in the previous question (adapted to this array), state the arguments of every call made by RBinarySearch(9, 1, 15) and the value finally returned.
Explain how a compiler handles a recursive call, and why recursion can cause a run-time error.
A student writes a recursive function to add up the 1 000 000 values in an array, one element per call. Evaluate this design.
Answer key and marking notes
- It calls itself (is defined in terms of itself).
- It has a base case / stopping condition that returns a value without a recursive call.
- It has a general case that calls itself with arguments that move towards the base case.
- DigitSum(4721) waits for 1 + DigitSum(472); DigitSum(472) waits for 2 + DigitSum(47).
- DigitSum(47) waits for 7 + DigitSum(4); DigitSum(4) is the base case and returns 4.
- Unwinding: DigitSum(47) returns 11, DigitSum(472) returns 13.
- DigitSum(4721) returns 14.
- Base case:
IF Low > High THEN RETURN -1. Mid ← (Low + High) DIV 2.- If
Data[Mid] = Target,RETURN Mid(second base case). - If
Data[Mid] < Target,RETURN RBinarySearch(Target, Mid + 1, High). - Otherwise
RETURN RBinarySearch(Target, Low, Mid - 1). - Correct function header, local Mid declared, matching ENDIF / ENDFUNCTION.
- (9, 1, 15): Mid 8, 34 > 9; then (9, 1, 7): Mid 4, 17 > 9.
- (9, 1, 3): Mid 2, 8 < 9; then (9, 3, 3): Mid 3, 12 > 9; then (9, 3, 2).
- Low > High in the fifth call, so −1 is returned and passed back up through every call.
- Each call pushes a stack frame onto the call stack.
- The frame holds the return address, the parameters and the local variables for that call.
- When a call ends its frame is popped, the return value is passed back and execution continues at the return address (unwinding).
- If the recursion is too deep or never reaches a base case, the stack runs out of memory: stack overflow.
- It works in principle: base case at the end of the array, general case adds one element to the sum of the rest.
- But it would need about 1 000 000 stack frames held at once (O(n) space), which is likely to cause a stack overflow, and each call adds time overhead.
- A simple loop is O(1) space and clearer for this problem, so iteration is the better choice.
6 multiple-choice questions on this lesson
From the topic question bank. Assign them in the app for a marked score in your gradebook, or run the topic as a class game.
Which is an essential feature of a recursive subroutine?
- AA base case that returns without making a further call
- BA FOR or WHILE loop that repeats the calls
- CA return value, so it must be a function
- DExactly one parameter that is decreased by 1
FUNCTION Sum(n : INTEGER) RETURNS INTEGER
IF n = 0 THEN
RETURN 0
ELSE
RETURN n + Sum(n - 1)
ENDIF
ENDFUNCTIONWhat does Sum(5) return, and how many calls to Sum are made in total?- A15, from 6 calls
- B15, from 5 calls
- C120, from 6 calls
- D5, from 6 calls
PROCEDURE R(n : INTEGER)
OUTPUT n MOD 10
IF n >= 10 THEN
CALL R(n DIV 10)
ENDIF
ENDPROCEDUREWhat is output by CALL R(472)?- A2, 7, 4
- B4, 7, 2
- C472, 47, 4
- D2, 7
A recursive call returns. What happens to its stack frame?
- AIt is popped, and execution continues at the return address with the caller's variables
- BIt is copied into the caller's frame so the values can be reused
- CIt stays on the stack until the whole program finishes
- DIt is pushed again so that the call can be repeated
FUNCTION F(a : INTEGER, b : INTEGER) RETURNS INTEGER
IF b = 0 THEN
RETURN a
ELSE
RETURN F(b, a MOD b)
ENDIF
ENDFUNCTIONWhat does F(84, 36) return, and how many calls to F are made in total?- A12, from 3 calls
- B12, from 2 calls
- C0, from 3 calls
- D36, from 2 calls
These values are inserted, in this order, into an empty binary search tree (smaller values go left, others go right): 40, 25, 60, 30, 10, 55, 70, 35.
PROCEDURE Visit(Node : INTEGER)
IF Node <> NullPointer THEN
CALL Visit(Tree[Node].LeftPointer)
CALL Visit(Tree[Node].RightPointer)
OUTPUT Tree[Node].Data
ENDIF
ENDPROCEDUREWhat is output when Visit is called with the root?- A10, 35, 30, 25, 55, 70, 60, 40
- B40, 25, 10, 30, 35, 60, 55, 70
- C10, 25, 30, 35, 40, 55, 60, 70
- D10, 30, 35, 25, 55, 70, 60, 40
Quiz key
A recursive subroutine calls itself, has a base case that stops the recursion, and a general case that moves towards the base case. It needs no loop (the calls do the repeating), a procedure can be recursive just as a function can (tree traversals are procedures), and it may have several parameters that change in other ways, such as halving.
The calls are Sum(5), Sum(4), Sum(3), Sum(2), Sum(1) and Sum(0): 6 calls. Unwinding returns 0, 1, 3, 6, 10 and finally 15. 5 calls forgets the base case call Sum(0), 120 multiplies as a factorial would, and 5 is only the parameter of the first call.
R(472) outputs 472 MOD 10 = 2 and calls R(47), which outputs 7 and calls R(4); 4 >= 10 is FALSE, so R(4) outputs 4 and the calls return with nothing more to do. The output happens on the way down, giving the digits in reverse: 2, 7, 4. 4, 7, 2 would need the OUTPUT after the call, 472, 47, 4 outputs n instead of n MOD 10, and 2, 7 forgets that R(4) still outputs before testing n.
On return the frame is popped, any return value is passed back, and the caller carries on from the stored return address with its own parameters and local variables, which were never overwritten: this is unwinding. Frames are not copied into the caller, are not kept until the program ends (that would quickly overflow the stack), and are not pushed again.
F(84, 36) calls F(36, 84 MOD 36) = F(36, 12), which calls F(12, 36 MOD 12) = F(12, 0). Now b = 0, so 12 is returned and passed back unchanged through both earlier calls: 3 calls, result 12 (the highest common factor of 84 and 36). 2 calls leaves out the base case call, 0 returns b instead of a, and 36 stops after the first call.
This is a post-order traversal (left, right, node). The tree has 25 and 60 under 40, 10 and 30 under 25, 35 as the right child of 30, and 55 and 70 under 60. Left subtree of 40: 10, then 30's subtree (35, then 30), then 25. Right subtree: 55, 70, 60. Finally 40. 40, 25, 10, ... is pre-order, the ascending list is in-order, and 10, 30, 35, ... outputs 30 before its own child 35.
What to project
The student lesson embeds these tabs. Open them full screen on the projector; every slider has a drag handle on the stage.
Slides for this lesson
A projectable deck for every pack is on the way. Until then, present the student lesson full screen: its sections, figure and lab tabs follow the same order as the plan above.