Skip to content

Nov 20: 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.

Announcements

Math Examples

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

See explanation on Wikipedia

  • 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 Trace

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
# Add the digits of a positive integer.


def sum_digits(n):
    if n == 0:
        return 0
    last = n % 10
    rest = n // 10
    return last + sum_digits(rest)


if __name__ == "__main__":
    print(f"{sum_digits(149) = }")
Example 2: n choose k
recur2.py
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
# Compute "n choose k" which is known as the binomial coefficient.


def choose(n, k):
    if k == 0 or k == n:
        return 1
    return choose(n-1, k-1) + choose(n-1, k)


if __name__ == "__main__":
    print(f"{choose(4, 2) = }")
Example 3: count string
recur3.py
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
# Count how many times "hi" is in a string.


def count_hi(string):
    if len(string) < 2:
        return 0
    add = 0
    if string[0] == 'h' and string[1] == 'i':
        add = 1
    return add + count_hi(string[1:])


if __name__ == "__main__":
    print(f'{count_hi("This hint") = }')
Example 4: search array
recur4.py
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
# Determine whether a list contains the number 6.


def has_six(nums, index):
    if index >= len(nums):
        return False
    return nums[index] == 6 or has_six(nums, index+1)


if __name__ == "__main__":
    print(f'{has_six([2, 5, 6], 0) = }')

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
import turtle


def sierpinski_triangle(order, size):

    if order == 0:
        for _ in range(3):
            turtle.forward(size)
            turtle.left(120)
        return

    size /= 2

    sierpinski_triangle(order - 1, size)
    turtle.forward(size)

    sierpinski_triangle(order - 1, size)
    turtle.backward(size)
    turtle.left(60)
    turtle.forward(size)
    turtle.right(60)

    sierpinski_triangle(order - 1, size)
    turtle.left(60)
    turtle.backward(size)
    turtle.right(60)


def main():

    screen = turtle.Screen()
    w = screen.window_width()
    h = screen.window_height()
    size = 0.9 * min(w, h)

    screen.bgcolor("white")
    screen.title("Sierpinski Triangle")

    turtle.speed(10)
    turtle.penup()
    turtle.goto(-size/2, -size/2)
    turtle.pendown()

    order = int(input("Enter the order of the Sierpinski triangle: "))

    sierpinski_triangle(order, size)
    screen.exitonclick()


if __name__ == "__main__":
    main()

Going Further

Just for fun, check out this Introduction to Turtle and Graphical Recursion from Williams College (Fall 2022).