Day 12-13: Recursion

CMSC 201 Day 12-13: Recursion

Project #1

Project #1 is still out! It's due Friday 2024-11-01 (Nov 1) at 11:59:59 PM! (So you have about one and a half weeks.)

No other homework! Until next Friday (Nov 1), when HW6 (recursive problems) is released :)

"Fun": super mario 64 speedruns

Super Mario 64: one of the greatest games ever. Subjectively. Also the target of an immense amount of effort for "speedrunning."

Essentially, the goal of speedrunning is to complete the game as quick as possible. In doing so, speedrunners develop an insane understanding of the game and its programming. Especially with Super Mario 64! If you want to binge youtube for 5 hours but want to be vaguely educated in retro programming, I highly suggest Bismuth's History of the "A Button Challenge." (https://www.youtube.com/watch?v=yXbJe-rUNP8)

Who cares (about recursion)?

It's fun :) And also very useful for solving specific types of problems. Programming is hard... sometimes in Python, you mess up your parentheses, and it's hard to see that you did. Like... is this correct?

for x in range(int(input())): print(input().join(input().split(input())))

Let's use recursion it to match parentheses B)!

Recursion

Recursion is when a function calls itself.

That's pretty much it! But this can be used to solve problems in an elegant way.

Let's take an example problem. Factorials are a classic recursive example. A factorial of N is the product of every integer up to N. So 5! (factorial) is 5*4*3*2 == 120.

# Here's a normal or "iterative" solution
def factorial_iterative(n):
    result = 1
    for x in range(n, 0, -1):
        result *= x
    return result

We can make this into a recursive function, by calling the function itself.

# Recursion!
# (Assume positive integer n)
def factorial_recursive(n):
    if n <= 1:
        return n
    return n*factorial_recursive(n-1)

Recursion can happen in real life too:

Leafs and plants?! The fern is recursive :)

def next_leaf():
    grow_leaf()
    next_leaf()

When you write a recursive function, it is critical that it stops at some point. The check for when to stop is called the base case. Without it, the function would run forever.

# Recursion!
def factorial_recursive(n):
    if n <= 1: # <-- the base case
        return n
    return n*factorial_recursive(n-1)

def factorial_recursive(n):
    # No more base case :( What happens?
    return n*factorial_recursive(n-1)

Then it would never exit!

>>> factorial_recursive(5)
Traceback (most recent call last):
  File "", line 1, in 
  File "", line 3, in factorial_recursive
  File "", line 3, in factorial_recursive
  File "", line 3, in factorial_recursive
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
>>>

It may be helpful to think of the function call being replaced by what it returns.

factorial_recursive(4)

# Is the same as calling...
4*factorial_recursive(3)

# Is the same as...
4*3*factorial_recursive(2)

# Is the same as...
4*3*2*factorial_recursive(1)

# Until you reach the base case,
# which does not call itself.
4*3*2*1 # Done!

That's basically all there is to know about recursion! The hardest part, as with everything, is implementing it to solve an actual problem.

Another one (example stolen from Prof. Hamilton), let's do a countdown!

In Python functions, you can have an "optional parameter". This means you have a parameter that you do not need to specify an argument for, if you don't want to. You have to specify a default value instead. In this example, let's say we want to stagger the output, adding an additional space in front of each consecutive line.

n = int(input("Countdown from? "))

def countdown(n, spaces=0):
    for i in range(spaces):
        print(" ", end="")
    if n == 0:
        print("Blastoff")
    else:
        print(n)
        countdown(n-1, spaces+1)

countdown(n)

Since they're functions, they each have their own local scope. (Each one has its own "copy" of the variables).

Let's do the fibonacci sequence! (0, 1, 1, 2, 3, 5, 8, 13, 21... https://oeis.org/A000045) First, iteratively:

def fibonacci_iterative(x):
    n = 0
    n1 = 1
    n2 = 0
    for y in range(x):
        n = n1
        n1 = n2
        n2 = n + n1
    return n2

Then for recursive, we can break it down into what we think the "base case" is, and the recursive case.

def fibonacci_recursive(n):
    if n <= 1:
        return n 
    return fibonacci_recursive(n-2) + fibonacci_recursive(n-1)

So elegant 😌 Much less code!

Challenge: Use recursion to output the padovan sequence (the same problem from HW4, https://oeis.org/A000931). It's fibonacci but with the second and third previous number rather than the first and second.

def padovan_seq(n):
    # Base case
    if n == 0:
        return 1
    if n <= 2:
        return 0
    return padovan_seq(n-3) + padovan_seq(n-2)

# Driver code
if __name__ == "__main__":
    for x in range(20):
        print(padovan_seq(x))

Trees, graphs, and traversals

Trees, oh my! Let's traverse some. Traversing a tree means visiting the nodes, usually in search of something (like a path between two points, or a certain value). This will become pretty relevant in project 3.

Here's an example tree we'll use:

                      ┌─────┐           
                      │  6  │ (the root)          
                      │     │           
             ┌────────┴──┬──┴───────┐   
             │           │          │   
             ▼           ▼          ▼   
          ┌─────┐    ┌─────┐     ┌─────┐
          │  8  │    │  5  │     │ 14  │ (leaf node)
          │     │    │     │     │     │
   ┌──────┴──┬──┘    └──┬──┴───┐ └─────┘
   │         │          │      │        
   ▼         ▼          ▼      ▼        
┌─────┐   ┌─────┐    ┌────┐ ┌──────┐    
│  -1 │   │  2  │    │ 6  │ │  36  │    
│     │   │     │    │    │ │      │    
└─────┘   └──┬──┘    └────┘ └──────┘    
             ▼                          
          ┌─────┐                       
          │  87 │ (another leaf node)                      
          │     │                       
          └─────┘                       

Trees are "acyclic", meaning there are no paths that are loops. Notice how each node nicely only leads downwards. Graphs on the other hand, can have as many loops as it wants. Don't worry too much about the terminology, the purpose of this is more to expose you to the concept of trees and traversals. There are a couple ways to represent a tree, but let's do a big dictionary of dictionaries.

my_cool_tree = {
    6: {
        8: {
            -1: {},
            2: {
                87: {},
            },
        },
        5: {
            6: {},
            36: {},
        },
        14: {},
    }
}

Let's write some code to visit every node. Recursion is SUPER powerful for this. (This is the only time I've actually had to use recursion in the real world...)

This is called a depth-first search, or DFS. (Breadth-first search, or BFS, doesn't work well with recursion...) What order are the nodes printed in?

def dfs(node):
    # Base case (not technically required!)
    if not node:
        return
    for key in node:
        print(key)
        dfs(node[key])

dfs(my_cool_tree)

Think of the functions being called like:

dfs(6)
    dfs(8)
        dfs(-1)
            dfs({})
        dfs(2)
            dfs(87)
                dfs({})
    dfs(5)
        dfs(6)
            dfs({})
        dfs(36)
            dfs({})
    dfs(14)

Recursion is very powerful! A small change can result in an entirely different result. Let's do postorder!

def dfs(node):
    if not node:
        return
    for key in node:
        dfs(node[key])
        print(key)

dfs(my_cool_tree)

Wow, just moving one line! Very cool, recursion :)

Let's use this knowledge for something. Can we solve this problem with a DFS?

Make a function, def generate_abc(i, j, n, k), that generates all strings of length i containing the given number of a's (j), b's (n), and c's (k).

You can have this starter code:

def generate_abc(i, j, n, k, tree={}, depth=0):
    # generate tree
    tree = {"a": {}, "b": {}, "c": {}}
    last_row = [tree]
    next_last_row = []
    for x in range(i):
        for node in last_row:
            for char in ["a", "b", "c"]:
                new_node = {}
                next_last_row.append(new_node)
                node[char] = new_node
        last_row = next_last_row[:]
        next_last_row = []

    generate_abc_dfs(i, j, n, k, tree=tree)

# Recursive helper function
def generate_abc_dfs(i, j, n, k, tree={}, depth=0, text="", a=0, b=0, c=0):
    # your code here!

# helper function
def generate_abc(i, j, n, k, tree={}, depth=0):
    # generate tree
    tree = {"a": {}, "b": {}, "c": {}}
    last_row = [tree]
    next_last_row = []
    for x in range(i):
        for node in last_row:
            for char in ["a", "b", "c"]:
                new_node = {}
                next_last_row.append(new_node)
                node[char] = new_node
        last_row = next_last_row[:]
        next_last_row = []

    generate_abc_dfs(i, j, n, k, tree=tree)

def generate_abc_dfs(i, j, n, k, tree={}, depth=0, text="", a=0, b=0, c=0):
    if a == j and b == n and c == k and i == depth:
        print(text)

    if not tree:
        return

    for key in tree:
        if key == "a":
            generate_abc_dfs(i, j, n, k, tree[key], depth+1, text+key, a+1, b, c)
        elif key == "b":
            generate_abc_dfs(i, j, n, k, tree[key], depth+1, text+key, a, b+1, c)
        elif key == "c":
            generate_abc_dfs(i, j, n, k, tree[key], depth+1, text+key, a, b, c+1)

if __name__ == "__main__":
    generate_abc(2, 1, 1, 0)
    generate_abc(5, 2, 2, 1)

Let's match some parentheses!

Take some string input. Return True if all parentheses are matched correctly, or False if they are not.

def match(text, index=0, count=0):
    # Base case
    if index >= len(text) or count < 0:
        return count == 0
    # Otherwise, match
    if text[index] == "(":
        return match(text, index+1, count+1)
    elif text[index] == ")":
        return match(text, index+1, count-1)
    return match(text, index+1, count)

print(match("(((aa))"))