DSE ICT | Recursion and algorithm efficiency lesson plan (for tutors)

DSE ICT | Recursion and algorithm efficiency lesson plan (for tutors) | Why binary search needs only 20 steps

2026-11-04

Tutor lesson-prep guides · Secondary ICT

Students can write a for loop but freeze when asked for a recursive version, or hand in a function with no stopping condition. This lesson draws the call stack first, then compares linear and binary search so efficiency becomes a number.

Objectives — Students can: (1) trace the call stack of factorial(4) and state 4 frames and the answer 24; (2) write a recursive function with a base case and explain why a missing base case raises RecursionError; (3) state that binary search on 1,048,576 sorted records needs at most 20 comparisons against 1,048,576 for linear search, a factor of about 52,429; (4) classify a double loop as O(n squared) and a halving loop as O(log n).

01 Prerequisites (3-minute check)

If any of these fails, fix it before the lesson starts.

Skill	Quick check	Pass mark
Functions and parameters	Where does a parameter live when a function is called?	In the stack frame of that call
For loops	How do you add the numbers from 1 to n?	Start an accumulator at 0 and add each term
Sorting	What must data be before binary search?	Already sorted

02 Lesson flow (60 minutes)

Time	Stage	Tutor does	Student does
0-8 min	Opener	A phone book has a million names. How many pages do you turn to find one?	Most say they would scan page by page
8-20 min	Trace factorial	Write factorial(4) leads to 4 times factorial(3) and so on down to 1	Four stack frames, answer 24
20-32 min	Base case and depth	Delete the line if n equals 1 and ask what happens	RecursionError, depth equals n
32-44 min	Binary search steps	2 to the power 20 is 1,048,576, so each halving removes one factor of 2	At most 20 comparisons
44-54 min	Four question types	Trace, repair a base case, classify complexity, count comparisons	One of each
54-60 min	Exit check	Three items, spoken or written	Two or fewer correct means repeat

03 Teaching script (read it out)

Scene 1: Recursion is not magic, it is unfinished calls stacked up

Write factorial(n): if n equals 1 return 1, otherwise return n times factorial(n-1). To finish factorial(4) the machine must wait for factorial(3), which waits for factorial(2), which waits for factorial(1). Only when 1 is returned do the multiplications unwind: 1, then 2, then 6, then 24. Draw four boxes side by side, arrows down for waiting and arrows up for returning, and the phrase “recursion keeps unfinished work on a stack” lands.

Board: four stack frames, arrows down for waiting and up for returning

Scene 2: Efficiency is a step count, not the length of the code

Put two sheets side by side. Linear search scans from the first record to the last, at worst 1,048,576 comparisons. Binary search halves the list each time and 1,048,576 is 2 to the power 20, so at worst 20 comparisons. The gap of 52,429 times is not slightly faster, it is one hour versus one second. Add the catch: unsorted data cannot be halved meaningfully, and sorting itself costs time.

Two sheets side by side: 1,048,576 linear comparisons against 20 binary comparisons

Scene 3: Both versions must be handed in

Ask students to write sum(n) with a for loop, then again with recursion, then compare. The loop keeps one accumulator and constant memory. The recursive version puts one frame on the stack per level, and n equal to 1,000 is already near the default Python recursion limit. The conclusion must be explicit: recursion is a style of expression, it does not make a program faster by itself.

Board: the loop version and the recursive version, with frame counts

04 Question types and worked steps

Type	Example	Steps	Answer
Trace	Write the call order and answer for factorial(4)	Start at factorial(1) and multiply back up	Four frames, answer 24
Repair	Add the missing base case to a recursive function	Ask what the smallest case returns	if n equals 0 return 1
Classify	Two nested loops each running n times	Count executions of the innermost line	O(n squared)
Calculate	Worst case comparisons for binary search on 1,048,576 sorted records	Find the power of 2, or halve repeatedly	20 comparisons

Sanity check (teach this): Check: log base 2 of 1,048,576 is 20 because 2 to the power 20 is 1,048,576, so answers of 21 or 19 mean an off-by-one halving. The stack depth of factorial(4) is 4, not 24; 24 is the answer, not the number of frames. Naive fib(6) makes 25 calls (2 times fib(7) minus 1, and fib(7) is 13) while the answer is only 8, which is the cleanest evidence that elegant recursion can be slow.

05 Independent practice (3 questions)

Question	Answer	What to watch
How many function calls does naive fib(6) make?	25 calls	2 times fib(7) minus 1
For 1,000,000 records, worst case for linear and binary search?	1,000,000 and 20 comparisons	2 to the power 20 just exceeds one million
What is wrong here: def total(n): return n + total(n-1)	No base case	It raises RecursionError because n never stops

06 Common mistakes and what to say

Mistake	Student writes	Say this
Missing base case	“The program explodes and the computer is broken”	“Write the stopping line first, then the going-down line; recursion without a stop is an infinite loop.”
Assuming recursion is always faster	“Recursion is more advanced so it is quicker”	“Recursion is only a style; fib(6) by recursion needs 25 calls to produce 8.”
Binary search on unsorted data	“I still cut it in half until it matches”	“Halving unsorted data is guessing; sort first or use linear search.”
Calling O(log n) twice as fast	“log n means half the time”	“n grows from 1,024 to 1,048,576, about 1024 times, while steps go from 10 to 20, only 10 more.”

07 Homework (paper, section and question numbers)

ICT chapter index — All chapters
Practice paper — Questions 5 to 8: recursion traces and step counts

08 Exit check (last 5 minutes)

Question	Answer	Decision
What is factorial(5), and how deep is the stack?	120, five frames	Wrong: redo act one
Binary search on 2 to the power 20 sorted records: worst case?	20 comparisons	One wrong: redo the substitution
How many calls does naive fib(6) make?	25 calls	Two wrong: restart act two

09 Tutor FAQ

Must recursion be taught?

The DSE syllabus expects students to read and repair recursive code; tracing and adding a base case are the common tasks.

Are the complexity symbols memorised?

Not the definitions, but students should map a double loop to O(n squared) and a halving loop to O(log n) within 30 seconds.

Why 20 comparisons and not 10?

Because 2 to the power 20 is 1,048,576; ten steps cover only 1,024 records.

Find a tutor — free Tutor Registration →

A TutorZone lesson-prep guide. Written by the TutorZone team; questions and lesson flow are original and are not taken from any school or publisher material.