COMP 202 Foundations of Programming • McGill University, Montreal

Revision sheet: Recursion, and when a loop is the better answer (COMP 202)

This sheet is not a summary of the recursion lectures of COMP 202: you already have the slides and the corrected set. It answers one question, what makes students lose marks on recursion, on the written midterm and final as much as under the autograder, and which precise line avoids each loss.

The angle of the chapter is that recursion is read like a proof by induction and never by unrolling the calls. Two obligations, a base case answered outright and a call on something strictly smaller, plus a return on every branch: check those three and the function is right; trace it by hand and you have checked one argument. The sheet ends with the honest question a loop deserves, since half the recursions asked in a first course are better written as three lines of for.

Mark this sheet as read or add it to your favourites: a free account, no password, keeps your read sheets and favourites from one visit to the next and tells you which chapter to tackle next. Create your space, an email is enough.

The thread of the chapter

Trust the call. A recursive function is checked on two lines only, the base case answered with no call and a call handed something STRICTLY smaller, and every branch of it must return; almost every mark lost on this chapter is one of those three lines missing, and no trace written by hand puts it back.

This chapter is part of COMP 202, Foundations of Programming (McGill)

The essentials

Two obligations and a return: the whole checklist of a recursive function

• A base case: the smallest problem, answered WITHOUT a call. Usually the empty structure, and its answer is usually the neutral element, $0$ for a sum, $1$ for a product, the empty string for a text, True for is_sorted.
• A step: a call on something STRICTLY smaller, values[1:], n - 1, n // 2, and the answer built from what comes back. If the argument of the call is the parameter itself, nothing shrinks.
• Every branch returns. A branch that computes n * factorial(n - 1) without the word return gives back None, and the caller crashes with TypeError one level up.
• Read the function like an induction: ASSUME the call is right on the smaller problem, check that the answer is built correctly from it. That assumption is the induction hypothesis, not optimism.
• No base case, or no shrinking, gives RecursionError after about $1000$ frames, Python's default limit. It is not an infinite loop: each call keeps a frame alive and the stack is finite.

Same function, same list: on the left each call is handed a shorter list and the fourth one hits the base case; on the right the call gets the same list and the thousandth frame raises RecursionError.

The marker looks for three things in that order, base case, shrinking argument, return on each branch. Writing the sentence 'the call is on values[1:], which is strictly shorter, so the base case is reached' earns the termination mark on its own.

What a call costs, and the three shapes that decide between a loop and a recursion

• Every call in progress keeps a frame: parameters, locals, return address. The depth of the recursion is the number of frames alive at once, and Python never eliminates tail calls, so a recursion always costs its depth in stack.
• Subtracting one gives depth $n$ ; halving gives depth $\log_2 n$ . On $n = 1024$ the slow power opens $1025$ frames, the fast one $12$ . Binary search takes $10$ steps on $1000$ values and $20$ on a million.
• A slice at every level copies: values[1:] on $100$ elements copies about $4950$ elements in all, quadratic. Pass an index instead, def sum_from(values, i), with the base case i == len(values).
• One path down, depth equal to the size of the data: the loop wins, three lines and one frame. The problem splits in two, or the structure is nested to an unknown depth: recursion is the right tool, and often the only one.
• Memoisation, one dictionary passed as a parameter, cures repeated subproblems only: naive Fibonacci makes $2F(n+1) - 1$ calls, $2692537$ for $n = 30$ , and the memoised one $2n - 1 = 59$ . Hanoi needs $2^n - 1$ moves and no dictionary saves one.

When a question says 'compare with a loop', the marks are for the depth and the copying, not for the word 'slower'. Name the number of frames and say whether a slice is copied at each level.

The rules in table form

Each row reads from left to right: the assumptions, then the result. A red cell is not an answer, it is the finding that the form settles nothing and the instruction to rewrite it. Every case is followed by a worked example.

Read the traceback: which of the three lines is missing

The autograder and the midterm give the same clues. Match what you see to the obligation that failed, then fix that line and no other; a red row is a rule students write that does not exist.

What you see	What failed	The fix
RecursionError	no shrinking, or no base case	call on values[1:] or n - 1; add the base case
Example: def f(n): return f(n) called on $5$ raises after about $1000$ frames; so does factorial(-1), whose n moves away from $0$ .
TypeError with NoneType	a branch without return	return on EVERY branch
Example: n * factorial(n - 1) without return: factorial(3) gives None, and the frame above computes $3 \times$ None.
IndexError on []	base case is the one-element case	base case on the EMPTY structure
Example: if len(values) == 1: return values[0] works on $[3, 1, 4]$ and crashes on $[]$ : values[0] does not exist.
wrong answer, no error	the answer is built in the wrong order	check the step on a 2-element input
Example: text[0] + reverse(text[1:]) returns 'abc' unchanged; reverse(text[1:]) + text[0] returns 'cba'. A test on $2$ characters settles it.
hangs on n = 30	the same subproblem is solved again and again	memo dictionary passed as a parameter
Example: Naive Fibonacci: $2692537$ calls for $n = 30$ ; memoised: $59$ ; a loop: $29$ additions.
'no base case means it loops for ever'	a rule students write	it STOPS, with RecursionError rule that does not exist
Example: def f(n): return f(n - 1) called on $5$ stops at frame $1000$ with a traceback naming f; an infinite while loop, by contrast, prints nothing and never returns. What to do: Write 'each call keeps a frame alive and the stack is finite, so the recursion raises RecursionError at the default limit of 1000'.

One traceback, one line to fix. Rewriting the whole function after a RecursionError is how a correct base case gets deleted along the way.

The mistakes that cost marks

These are the errors I correct most often in session. Each one costs marks on a paper, even when the reasoning behind it is right.

1. The recursive branch computes without returning

the whole question under the autograder, and half the marks on paper

What not to write

“if n == 0: return 1, else: n * factorial(n - 1)”

What to write

“if n == 0: return 1, else: return n * factorial(n - 1). Every branch of a recursive function returns.”

Same frames, same multiplications: with return the values 1, 1, 2, 6 climb back up; without it only the base case returns anything, and the frame of factorial(3) multiplies 3 by None.

Why: The product is computed and thrown away; the function falls off its end and gives None, so factorial(3) is None and the caller raises TypeError on 3 * None. It is the single most frequent recursion bug of a first course, and it is invisible on paper unless you read the word return on each branch.

2. The call is handed the same argument as its caller

the whole question: the function never returns

What not to write

“def sum_list(values): if values == []: return 0, return values[0] + sum_list(values)”

What to write

“return values[0] + sum_list(values[1:]): the call gets a list strictly shorter than values, so the base case is reached after len(values) calls.”

Why: The base case is present and correct, and it is unreachable: nothing gets smaller, and the thousandth frame raises RecursionError. Look at the argument INSIDE the recursive call and ask what makes it smaller; if the answer is nothing, the fix is there and not in the base case.

3. The base case is the one-element case instead of the empty one

2 to 3 marks on paper, a failed test under the autograder

What not to write

“if len(values) == 1: return values[0], then return values[0] + sum_list(values[1:])”

What to write

“if values == []: return 0, then return values[0] + sum_list(values[1:]). The base case is the empty list and its value is the neutral element 0.”

Why: The function works on every non-empty list and crashes on [] with IndexError, and the autograder always tests the empty input. The empty structure is the smallest one the function can be handed, which is why it is almost always the right base case, and why its answer is 0 for a sum, 1 for a product, '' for a text.

4. One base case when the step removes two elements

2 marks, and a wrong answer on every odd length

What not to write

“def is_palindrome(text): if text == '': return True, return text[0] == text[-1] and is_palindrome(text[1:-1])”

What to write

“if len(text) <= 1: return True: the step removes TWO characters, so an odd length shrinks to one character, and that one must stop the recursion too.”

Why: On 'aba' the recursion goes to 'b', then slices 'b'[1:-1], which is '', and answers True by luck; on 'abc' it goes to 'b' and the same luck hides that the base case was never designed. Count what the step removes, and write one base case per length it can leave behind: 0 and 1 here, 0 alone when the step removes one.

5. The mid index left inside the interval of a binary search

the whole question: on lo = hi the function calls itself for ever

What not to write

“if values[mid] < target: return search(values, target, mid, hi) else: return search(values, target, lo, mid)”

What to write

“return search(values, target, mid + 1, hi) on the right, search(values, target, lo, mid - 1) on the left: mid has just been compared, it is excluded. The empty interval is lo > hi, which returns -1.”

After comparing values[7] = 56 to 23, hi = mid keeps index 7 in the next interval although it is known not to hold 23; hi = mid - 1 drops it, and on lo = hi = 7 only the second version stops.

Why: With lo = hi = 7, mid is 7 and hi = mid hands the call the same pair, which is the shrinking obligation broken in disguise. Excluding mid on both sides is the entire difficulty of binary search, and it is why the empty test is lo > hi and not lo == hi.

6. The memo dictionary written as a default argument

1 to 2 marks on paper, and a function that cannot be tested in isolation

What not to write

“def fib(n, memo={}): if n in memo: return memo[n] ...”

What to write

“def fib(n, memo): with the dictionary passed in by the caller, or def fib(n, memo=None): if memo is None: memo = {} as the first line.”

Why: A default value is evaluated ONCE, at definition time, so one hidden dictionary is shared by every call of the program, exactly like the default list of the functions chapter. The remembered values stay right, which is why the bug survives, but the function now carries state between unrelated calls and the marker knows the pattern.

7. A hand trace offered as the proof that the function is correct

all the justification marks, typically 2 to 3 of the question

What not to write

“I traced sum_list([1, 2]) and got 3, so the function is correct.”

What to write

“Base case: the empty list returns 0, the total of nothing. Step: assuming sum_list(values[1:]) is the total of the rest, values[0] + sum_list(values[1:]) is the total of the list, and values[1:] is strictly shorter, so the base case is reached.”

Why: A trace proves the answer for one argument; the question asks for every argument. The two sentences that earn the marks are the two steps of an induction, base case and step under the hypothesis that the call is right, and they take less time to write than the trace.

8. The recursion prints its answer instead of returning it

the whole question: the recursive call is None and the addition raises TypeError

What not to write

“def sum_list(values): if values == []: print(0) else: print(values[0] + sum_list(values[1:]))”

What to write

“A recursive function that computes a value RETURNS it: return values[0] + sum_list(values[1:]). Print the result once, in the caller.”

Why: print sends text to the screen and returns None, so the step adds values[0] to None. The rule of the functions chapter is sharper here than anywhere: only a returned value can be used by another call, and a recursion is nothing but calls using each other's values. Only a function that does something, like moving a Hanoi disk, prints inside its recursion.

9. The guard against a bad argument hidden in the base case

1 mark of rigour, and a wrong answer quietly returned

What not to write

“if n <= 0: return 1, so that factorial(-1) does not crash”

What to write

“if n < 0: raise ValueError('n must be non-negative') at the top of the function, then if n == 0: return 1.”

Why: n <= 0 makes factorial(-3) return 1, a wrong number that no test catches before it poisons a later computation. A guard is a separate line before the base case: it names the bad input and refuses it, and the base case keeps its exact meaning, the empty product.

Which method to choose

Which base case, which argument, loop or recursion, by the SHAPE of the data

Look at what the function is handed, and at what the step removes, before writing a line

If a list or a string, processed one element at a time → base case the EMPTY structure, step on values[1:], answer the neutral element; if the input can be long, pass an index and keep one list for every frame

Example: sum_list([]) is 0; sum_from(values, i) with base case i == len(values) copies nothing
If the step removes TWO elements, one at each end → two base cases in one condition, len <= 1, because an odd length ends on one element

Example: is_palindrome('aba') goes to 'b' and stops there
If a number decreased by one at each step → base case 0, depth n; and if n can exceed a thousand, this is a loop, not a recursion

Example: factorial(1024) opens 1025 frames; a for loop opens one
If a number halved, or a digit peeled off → base case n == 0 or n < 10, depth $\log_2 n$ or the number of digits: keep the recursion, it is the shape of the algorithm

Example: fast power on $n = 1024$ : $11$ halvings, $12$ frames; digit_sum(1234) makes $4$ calls

write half = power(x, n // 2) once; calling power twice in the same line throws the saving away
If a SORTED list and a value to find → two indices lo and hi, never a slice; base case lo > hi returns -1; calls on mid + 1 and mid - 1

Example: $1000$ values in $10$ steps, a million in $20$
If a structure nested to an unknown depth: lists inside lists, folders inside folders → recursion, and nothing else works: the base case is the LEAF, tested with isinstance, and the step combines the results on the elements

Example: deep_sum([1, [2, [3, 4]], 5]) is 15, with three levels no fixed number of loops can walk
If the same subproblem comes back many times, as in Fibonacci → a memo dictionary passed as a parameter, lookup first, store just before the return; or the two-variable loop, which beats it

Example: fib(30): $2692537$ naive calls, $59$ memoised, $29$ additions in a loop

if nothing repeats, as in Hanoi, binary search or deep_sum, the dictionary saves nothing

Python has no tail-call elimination and a default limit of 1000 frames. A recursion whose depth equals the size of the data is a loop wearing a costume; a recursion whose problem splits or nests is the real thing.

How the answer is expected to be written

A marker ticks steps. Here they are in order, with the concluding sentence expected word for word.

Writing a recursive function on paper, in the order the marker reads it

When to use it: The question says 'write a recursive function that...' and gives an example call, on the midterm or in an assignment marked by hand

1 Write in ONE sentence what the function returns: 'sum_list returns the total of every number in values'. It is the sentence the step will trust.
2 Write the base case first, on the empty structure or on 0, answered with a return and no call: 'if values == []: return 0', the total of nothing.
3 Write the step as ONE call on something strictly smaller, and the answer built from it: 'return values[0] + sum_list(values[1:])', with return on the line.
4 Add the guard, if the input can be invalid, ABOVE the base case: 'if n < 0: raise ValueError', never as n <= 0 inside the base case.
5 Check on paper: every branch has a return, the argument of the call is smaller than the parameter, and the base case gives the right answer on the empty input.

Concluding sentence

“sum_list returns the total of the list. Base case: the empty list has total 0. Step: values[0] + sum_list(values[1:]), where values[1:] is strictly shorter than values, so the base case is reached after len(values) calls.”

The trap: Writing the step before the base case, then forgetting the base case altogether because the step 'already works' on the example.

Marking: Typically 1 mark for the base case, 2 for the step with its return, 1 for the shrinking argument named, 1 for the guard or the empty-input check.

Justifying that a recursion is correct and terminates

When to use it: The question says 'explain why your function is correct', 'show that it terminates', or 'why does the base case matter'

1 Termination: name the quantity that shrinks at every call and say what it reaches. 'The second argument of gcd is replaced by a mod b, strictly smaller, so it reaches 0.'
2 Base case: state that the smallest problem is answered with no call, and that the answer is right there: 'gcd(a, 0) is a'.
3 Step: ASSUME the call is right on the smaller problem, then show the answer is built correctly: 'if gcd(b, a mod b) is the gcd of b and a mod b, it is also the gcd of a and b'.
4 Say in one line why a trace is not enough: it checks one argument, the induction checks them all.

Concluding sentence

“The second argument strictly decreases and reaches 0, where the function returns a without a call; assuming the call gives the gcd of the smaller pair, the step returns the gcd of the original pair, so the function is correct for every pair.”

The trap: Answering 'it works because I tested it on 48 and 18', which earns the trace's mark and none of the justification's.

Check before you hand in

Five minutes of checking recover more marks than one more problem started in a hurry.

The word return on every branch

Read each branch of the function and find its return. A branch that ends on a call or a product without one gives None.

A branch that reads 'else: n * factorial(n - 1)' fails the check; the function returns 1 on 0 and None everywhere else.
The argument of the call is smaller than the parameter

Compare what is inside the recursive call with the parameter of the header: values[1:] against values, n - 1 against n, mid + 1 against lo. Identical means RecursionError.

search(values, target, mid, hi) with lo = hi = mid fails the check: the pair handed down is the pair received.
The empty input, by hand

Run the function in your head on [] or '' or 0. It must return, without indexing anything. The autograder always tries it.

if len(values) == 1: return values[0] fails the check: on [] the function reaches values[0] and raises IndexError.
As many base cases as the step can leave behind

Count what the step removes. Removing one element needs the empty case; removing two needs the empty case AND the one-element case.

is_palindrome with text == '' as the only base case fails the check: 'abc' shrinks to 'b', which the step slices instead of answering.
The depth against the limit of 1000

Estimate the number of frames: the size of the data for a linear recursion, log of it for a halving one. Above a thousand, the question wants a loop or an index.

A recursive palindrome test on a string of a million characters fails the check: half a million frames, RecursionError long before the end.

The typical problem, taken apart

is_sorted, written recursively, then justified and compared with a loop

Write a recursive function is_sorted(values) that returns True when the list of numbers values is in non-decreasing order and False otherwise. is_sorted([2, 5, 4, 9]) is False, is_sorted([1, 3, 7]) is True.

Give the base case or cases, follow the calls on [2, 5, 4, 9], justify that the function is correct, and say whether a loop would be the better answer.

On [2, 5, 4, 9] the first comparison passes and the call goes on; the second fails, and the and operator stops there: is_sorted([4, 9]) is never called, which is why the trace has two calls and not four.

Python

def is_sorted(values):
    if len(values) <= 1:
        return True
    return values[0] <= values[1] and is_sorted(values[1:])

Step 1

The sentence: is_sorted returns True when every element is at most the next one. The step will compare the FIRST TWO elements and trust the call on the rest.

Why

Writing the sentence first decides the base case: the step needs two elements, so the smallest problems it can leave behind are the empty list and the one-element list.

Step 2

Base cases: if len(values) <= 1: return True. An empty list and a list of one element are sorted, there is nothing to compare.

Why

One condition, two base cases, exactly as for the palindrome: the step removes one element but READS two, so a one-element list would index values[1] and crash with IndexError.

Step 3

Step: return values[0] <= values[1] and is_sorted(values[1:]). The list handed down is values[1:], strictly shorter, so the base case is reached after at most len(values) - 1 calls.

Why

The return is on the line, the call is on something smaller, and the answer is built with and: the three checks of the chapter in one line. Naming the shrinking argument earns the termination mark.

Step 4

Trace on [2, 5, 4, 9]: 2 <= 5 is True, so is_sorted([5, 4, 9]) is called; 5 <= 4 is False, and the and operator short-circuits, so is_sorted([4, 9]) is never called. Two calls, answer False. On [1, 3, 7]: three calls, the last on [7], the base case, True.

Why

The trace is here to check the base case and the short circuit, not to prove correctness: two calls and not four is the fact a marker wants to see you noticed.

Step 5

Justification: base case, an empty or one-element list is sorted. Step: assuming is_sorted(values[1:]) is right, the list is sorted exactly when its first two elements are in order AND the rest is sorted, which is what the line returns.

Why

This is the induction, and it is worth the justification marks that the trace above is not. It takes two sentences.

Step 6

Loop or recursion: the recursion walks one path with depth len(values) and slices at every level, about $n^2/2$ elements copied. The loop, for i in range(len(values) - 1): if values[i] > values[i + 1]: return False, then return True, has one frame and copies nothing.

Why

The honest answer the question wants: the loop is the better tool, and the recursion was asked to test the three obligations. Saying so, with the depth and the copying named, earns the comparison mark.

The conclusion, written out

“Base cases len(values) <= 1 return True; the step returns values[0] <= values[1] and is_sorted(values[1:]), on a strictly shorter list; on [2, 5, 4, 9] the second comparison fails and the recursion stops after two calls. The loop over adjacent pairs does the same with one frame and no copying.”

The classic mistake on this problem: Writing if values == []: return True as the only base case: is_sorted([7]) then evaluates values[1] and raises IndexError, and the autograder tests the one-element list every time.

Learn by heart

• A recursive function has a base case answered with NO call, and a step that calls on something STRICTLY smaller; every branch RETURNS.
• The base case is the empty structure and its answer the neutral element: 0 for a sum, 1 for a product, '' for a text, True for a property.
• A step that removes two elements needs two base cases: len <= 1.
• No base case or no shrinking: RecursionError after about 1000 frames, not an infinite loop.
• Depth $n$ when subtracting one, $\log_2 n$ when halving: binary search does 10 steps on 1000 values, 20 on a million. Python never eliminates tail calls.
• Binary search: indices lo and hi, base case lo > hi returns -1, calls on mid + 1 and mid - 1.
• Memoisation, dictionary passed as a parameter, lookup first, store before the return: fib(30) goes from $2692537$ calls to $59$ . Hanoi, $2^n - 1$ moves, is helped by nothing.
• Correctness is an induction, base case then step trusting the call; a trace checks one argument.

Frequently asked questions

Why does my recursive function return None in COMP 202?

Because one branch computes without the word return. A Python function that reaches the end of a branch gives back None, so n times factorial of n minus 1 without return produces None, and the caller then crashes with a TypeError when it multiplies by None. Put return on every branch of the function, the recursive one included, and check it by reading each branch on paper before running anything.

What is the base case of a recursive function and how do I choose it?

The base case is the smallest input, answered directly with no recursive call. Choose the empty structure whenever the function is handed a list or a string, and give it the neutral answer: zero for a sum, one for a product, the empty string for a text, True for a property like is sorted. When the step removes two elements at once, add the one element case as a second base case, otherwise an odd length crashes.

Why do I get RecursionError maximum recursion depth exceeded?

Either the base case is missing, or the recursive call is handed the same argument as its caller, so nothing gets smaller and the base case is never reached. Each call keeps a frame alive and Python stops at about a thousand frames rather than crashing silently. Look inside the recursive call: the argument must be strictly smaller than the parameter, values from index one onward instead of values, n minus 1 instead of n.

When should I use a loop instead of recursion in Python?

When the recursion walks one path whose depth equals the size of the data, such as summing a list or computing a factorial: the loop does the same work with one frame, no copying, and no depth limit. Keep the recursion when the problem splits in two, as in binary search or the fast power, or when the data is nested to an unknown depth, as in lists inside lists, where no fixed number of loops can reach every level.

How do I prove that a recursive function is correct on an exam?

Write the two steps of an induction, not a trace. First the base case: the smallest input is answered correctly with no call. Then the step: assuming the recursive call gives the right answer on the smaller input, show that the line builds the right answer from it, and name what makes the argument strictly smaller so that the base case is reached. A hand trace only checks one particular input and earns none of the justification marks.

Practise it

Corrected exercises: Recursion, and when a loop is the better answer, COMP 202

A method is proved on a paper, not on a sheet. The set for the same chapter takes each of these traps into a problem, with the solution written out step by step.

10 corrected exercises
100 points
150 minutes

Do the exercises

Previous sheet Files, exceptions and real data Next sheet Classes and objects

© Ahmed Squalli Houssaini. Revision sheet published at www.letuteurscientifique.ca/en/fiches/comp202-recursion. Free for personal and classroom use; republishing it elsewhere requires written permission (legal notice).

Stuck in COMP 202?

I tutor COMP 202 at McGill in English or in French, in person in Montreal or online. Get in touch for a first session: we take the recursion questions of past midterms and write them the way the marker reads them.

Book a session WhatsApp

Site by Studio Squalli

Revision sheet: Recursion, and when a loop is the better answer (COMP 202)

The essentials

Two obligations and a return: the whole checklist of a recursive function

What a call costs, and the three shapes that decide between a loop and a recursion

The rules in table form

Read the traceback: which of the three lines is missing

The mistakes that cost marks

1. The recursive branch computes without returning

2. The call is handed the same argument as its caller

3. The base case is the one-element case instead of the empty one

4. One base case when the step removes two elements

5. The mid index left inside the interval of a binary search

6. The memo dictionary written as a default argument

7. A hand trace offered as the proof that the function is correct

8. The recursion prints its answer instead of returning it

9. The guard against a bad argument hidden in the base case

Which method to choose

Which base case, which argument, loop or recursion, by the SHAPE of the data

How the answer is expected to be written

Writing a recursive function on paper, in the order the marker reads it

Justifying that a recursion is correct and terminates

Check before you hand in

The typical problem, taken apart

is_sorted, written recursively, then justified and compared with a loop

Learn by heart

Frequently asked questions

Why does my recursive function return None in COMP 202?

What is the base case of a recursive function and how do I choose it?

Why do I get RecursionError maximum recursion depth exceeded?

When should I use a loop instead of recursion in Python?

How do I prove that a recursive function is correct on an exam?

Corrected exercises: Recursion, and when a loop is the better answer, COMP 202

See also

Stuck in COMP 202?