Nov 18: Tracing Recursion by Hand
Learning Objectives
After today's class, you should be able to:
- Explain how a return statement works in a recursive function.
- Describe the process of tracing a recursive function on paper.
- Step through a recursive function using Thonny's debugger.
Reminders¶
- Project 3 (due Dec 03)
- Part A due Monday, 11/18
- Part B due Thursday, 11/21
- Part C due Tuesday, 12/03
- Chapter 12: Recursion
- Read by Tuesday, 11/19
Math Examples¶
- Quick review of Friday's activity
- Demo: Recursion Tree Visualizer
Factorial Function
-
In Math:
- \(0! = 1\)
- \(n! = n * (n-1)!\)
-
In Python:
def fn(n): if (n == 0): return 1 return n * fn(n - 1)
Binomial Coefficient
- In Math:
- \({n \choose 0} = {n \choose n} = 1\)
- \({n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}\)
- In Python:
def fn(n, k): if (k == 0 or n == k): return 1 return fn(n-1, k-1) + fn(n-1, k)
How to Read¶
How to read a recursive function:
- On paper: drawing a diagram
- On computer: Thonny debugger
Example 1: sum digits
recur1.py | |
---|---|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
Example 2: n choose k
recur2.py | |
---|---|
1 2 3 4 5 6 7 8 9 10 11 |
|
Example 3: count string
recur3.py | |
---|---|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
Example 4: search array
recur4.py | |
---|---|
1 2 3 4 5 6 7 8 9 10 11 |
|
Recursive Art¶
Example 5: SierpiĆski Triangle
sierpinski.py | |
---|---|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
|
Going Further
Just for fun, check out this Introduction to Turtle and Graphical Recursion from Williams College (Fall 2022).