Reference
for
Introduction to the Theory of Computation
CSC236 — 2026 Fall
Gary Baumgartner
,
, Contents
Chapter 1. Tracing Recursion — Review 4
1.1. More Exercises 9
1.2. Solutions 15
Chapter 2. Correctness of Recursions 25
2.1. Review: Designing a Recursive Algorithm 25
2.2. Review: Correctness of Algorithms 26
2.3. Review: Correctness of Recursive Algorithms 26
2.4. Component: Valid Recursive Structure 27
2.5. Template: Valid Recursive Structure 30
2.6. Algorithm: Greatest Common Divisor 30
2.7. Component: Correct Return Value 31
2.8. Template: Correct Return Value 33
2.9. Component: Valid Non-Recursive Calls 33
2.10. Algorithm: Prime-Factorization 34
Exercises 36
Solutions 38
Chapter 3. Complete Induction 42
3.1. Change-Making Revisited 42
3.2. Prime Factorization Revisited 44
3.3. Induction on a Measure 44
3.4. The Principle of Complete Induction (Optional) 48
Exercises 49
Solutions 51
Chapter 4. Recursive Data 54
4.1. Structural Set Definition 54
4.2. Structural Inductions 55
4.3. Derivational Ambiguity 57
4.4. Binary Trees, Structurally 58
Exercises 60
Solutions 62
3
, CHAPTER 1
Tracing Recursion — Review
In this course we will prove the correctness of recursive algorithms, apply recursive proof techniques, prove properties of
recursively defined data, and determine the running times of recursive algorithms.
The recursive algorithms we will consider will typically be designed to return a value, and not modify objects nor perform I/O.
We assume that in a prerequisite course you learned to trace the execution of (i.e., manually execute) any call of any algorithm,
line by line, step by step. So, in particular, for a call of a recursive algorithm you can list:
All the recursive calls that occur during execution:
· in order
· with their arguments
· and their returned values
And the returned value of the entire call itself.
In a previous course1 you traced the following algorithm:
# Precondition: L is a non-empty sequence of comparable elements.
def S (L):
if len(L) == 1: return (L[0],)
else: return M ( S (L[0 : len(L)//2]) , S (L[len(L)//2 : len(L)]) )
# Return a tuple containing the elements of LL and LR, sorted together.
def M (LL, LR): # implementation omitted
Regardless of whether you recognize it or saw it in this form, make sure you can reliably trace such a small algorithm, and
practice (1.1) enough tracing to do it quickly:
Exercise 1. List all the recursive calls that occur during execution of call S ((8, 0, 1, 4)), in the order they occur, with their
arguments and returned values, and the final returned value.
When we ask for the trace of a call of a recursive function this is the information from your manual execution that we are
asking for, organized as shown in our solution to this Exercise (see section §1.2). This includes indentation showing which calls
are children of which parent. (We will remind you of this form and the other tracing forms on tests)
With the indentation, if you look at the trace sideways it looks much like the call tree of a call of a recursive function (you drew
this kind of tree in a previous course2, in particular to understand the execution and running time of the previous algorithm):
S((8, 0, 1, 4)) = (0, 1, 4, 8)
S((8, 0)) = (0, 8) S((1, 4)) = (1, 4)
S((8, )) = (8, ) S((0, )) = (0, ) S((1, )) = (1, ) S((4, )) = (4, )
1https://www.teach.cs.toronto.edu/~csc110y/fall/notes/18-sorting/05-mergesort.html
2https://www.teach.cs.toronto.edu/~csc148h/notes/recursion/branching_recursion.html#branching-recursion
4
for
Introduction to the Theory of Computation
CSC236 — 2026 Fall
Gary Baumgartner
,
, Contents
Chapter 1. Tracing Recursion — Review 4
1.1. More Exercises 9
1.2. Solutions 15
Chapter 2. Correctness of Recursions 25
2.1. Review: Designing a Recursive Algorithm 25
2.2. Review: Correctness of Algorithms 26
2.3. Review: Correctness of Recursive Algorithms 26
2.4. Component: Valid Recursive Structure 27
2.5. Template: Valid Recursive Structure 30
2.6. Algorithm: Greatest Common Divisor 30
2.7. Component: Correct Return Value 31
2.8. Template: Correct Return Value 33
2.9. Component: Valid Non-Recursive Calls 33
2.10. Algorithm: Prime-Factorization 34
Exercises 36
Solutions 38
Chapter 3. Complete Induction 42
3.1. Change-Making Revisited 42
3.2. Prime Factorization Revisited 44
3.3. Induction on a Measure 44
3.4. The Principle of Complete Induction (Optional) 48
Exercises 49
Solutions 51
Chapter 4. Recursive Data 54
4.1. Structural Set Definition 54
4.2. Structural Inductions 55
4.3. Derivational Ambiguity 57
4.4. Binary Trees, Structurally 58
Exercises 60
Solutions 62
3
, CHAPTER 1
Tracing Recursion — Review
In this course we will prove the correctness of recursive algorithms, apply recursive proof techniques, prove properties of
recursively defined data, and determine the running times of recursive algorithms.
The recursive algorithms we will consider will typically be designed to return a value, and not modify objects nor perform I/O.
We assume that in a prerequisite course you learned to trace the execution of (i.e., manually execute) any call of any algorithm,
line by line, step by step. So, in particular, for a call of a recursive algorithm you can list:
All the recursive calls that occur during execution:
· in order
· with their arguments
· and their returned values
And the returned value of the entire call itself.
In a previous course1 you traced the following algorithm:
# Precondition: L is a non-empty sequence of comparable elements.
def S (L):
if len(L) == 1: return (L[0],)
else: return M ( S (L[0 : len(L)//2]) , S (L[len(L)//2 : len(L)]) )
# Return a tuple containing the elements of LL and LR, sorted together.
def M (LL, LR): # implementation omitted
Regardless of whether you recognize it or saw it in this form, make sure you can reliably trace such a small algorithm, and
practice (1.1) enough tracing to do it quickly:
Exercise 1. List all the recursive calls that occur during execution of call S ((8, 0, 1, 4)), in the order they occur, with their
arguments and returned values, and the final returned value.
When we ask for the trace of a call of a recursive function this is the information from your manual execution that we are
asking for, organized as shown in our solution to this Exercise (see section §1.2). This includes indentation showing which calls
are children of which parent. (We will remind you of this form and the other tracing forms on tests)
With the indentation, if you look at the trace sideways it looks much like the call tree of a call of a recursive function (you drew
this kind of tree in a previous course2, in particular to understand the execution and running time of the previous algorithm):
S((8, 0, 1, 4)) = (0, 1, 4, 8)
S((8, 0)) = (0, 8) S((1, 4)) = (1, 4)
S((8, )) = (8, ) S((0, )) = (0, ) S((1, )) = (1, ) S((4, )) = (4, )
1https://www.teach.cs.toronto.edu/~csc110y/fall/notes/18-sorting/05-mergesort.html
2https://www.teach.cs.toronto.edu/~csc148h/notes/recursion/branching_recursion.html#branching-recursion
4
