If you do not have an in-person TA, you can reach your TA using this Zoom link.

If there are fewer than 3 people in your group, feel free to merge your group with another group in the room.

Now switch to Pensieve:

• Everyone: Go to pensieve.co, log in with your @berkeley.edu email, and enter your group number (which was in the email that assigned you to this lab).

Once you're on Pensieve, you don't need to return to this page; Pensieve has all the same content (but more features). If for some reason Penseive doesn't work, return to this page and continue with the discussion.

Getting Started

Say your name and share a food that you really liked as a child. (It's ok if you still like that food now.)

Recursion

Many students find this discussion challenging. Everything gets easier with practice. Please help each other learn.

VERY IMPORTANT: In this discussion, don't check your answers until your whole group is sure that the answer is right. Figure things out and check your work by thinking about what your code will do. Your goal should be to have all checks pass the first time you run them! If you need help, ask.

Q1: Swipe

Implement swipe, which prints the digits of argument n, one per line, first backward then forward. The left-most digit is printed only once. Do not use while or for or str. (Use recursion, of course!)

Q2: Skip Factorial

Define the base case for the skip_factorial function, which returns the product of every other positive integer, starting with n.

Q3: Is Prime

Implement is_prime that takes an integer n greater than 1. It returns True if n is a prime number and False otherwise. Try following the approach below, but implement it recursively without using a while (or for) statement.

def is_prime(n):
    assert n > 1
    i = 2
    while i < n:
        if n % i == 0:
            return False
        i = i + 1
    return True

You will need to define another "helper" function (a function that exists just to help implement this one). Does it matter whether you define it within is_prime or as a separate function in the global frame? Try to define it to take as few arguments as possible.

def is_prime(n):
    def f(i):
        if n % i == 0:
            return ____
        elif ____:
            return ____
        else:
            return f(____)
    return f(2)

Documentation: Come up with a one sentence docstring for the helper function that describes what it does. Don't just write, "it helps implement is_prime." Instead, describe its behavior. If you need help, ask!

Q4: Recursive Hailstone

Recall the hailstone function from Homework 1. First, pick a positive integer n as the start. If n is even, divide it by 2. If n is odd, multiply it by 3 and add 1. Repeat this process until n is 1. Complete this recursive version of hailstone that prints out the values of the sequence and returns the number of steps.

Recommended: Once your group has converged on a solution, it's time to practice your ability to describe your own code. Nominate someone to describe how your solution works and have them present to the group for practice. Then, tell this description to your TA for feedback (on Zoom if your TA is remote).

Document the Occasion

Please all fill out the attendance form (one submission per person per week).

Extra Questions

The questions below are recommended but optional. Don't worry if you don't get to them (but at least read the first one).

You'll need your whole discussion group for this question. At least try it out. You might have fun.

Q5: Sevens

The Game of Sevens: Players in a circle count up from 1 in the clockwise direction. (The starting player says 1, the player to their left says 2, etc.) If a number is divisible by 7 or contains a 7 (or both), switch directions. Numbers must be said on the beat at 60 beats per minute. If someone says a number when it's not their turn or someone misses the beat on their turn, the game ends.

For example, 5 people would count to 20 like this:

Player 1 says 1
Player 2 says 2
Player 3 says 3
Player 4 says 4
Player 5 says 5
Player 1 says 6  # All the way around the circle
Player 2 says 7  # Switch to counterclockwise
Player 1 says 8
Player 5 says 9  # Back around the circle counterclockwise
Player 4 says 10
Player 3 says 11
Player 2 says 12
Player 1 says 13
Player 5 says 14 # Switch back to clockwise
Player 1 says 15
Player 2 says 16
Player 3 says 17 # Switch back to counterclockwise
Player 2 says 18
Player 1 says 19
Player 5 says 20

Play a few games. Post the highest score your group reached on Discord.

Then, implement sevens which takes a positive integer n and a number of players k. It returns which of the k players says n. You may call has_seven.

An effective approach to this problem is to simulate the game, stopping on turn n. The implementation must keep track of the final number n, the current number i, the player who will say i, and the current direction that determines the next player (either increasing or decreasing). It works well to use integers to represent all of these, with direction switching between 1 (increase) and -1 (decreasing).

Q6: Karel the Robot

Karel the robot starts in the corner of an n by n square for some unknown number n. Karel responds to only four functions:

• move() moves Karel one square forward if there is no wall in front of Karel and errors if there is.
• turn_left() turns Karel 90 degrees to the left.
• front_is_blocked() returns whether there is a wall in front of Karel.
• front_is_clear() returns whether there is no wall in front of Karel.

Implement a main() function that will leave Karel stopped halfway in the middle of the bottom row. For example, if the square is 7 x 7 and Karel starts in position (1, 1), the bottom left, then Karel should end in position (1, 4) (three steps from either side on the bottom row). Karel can be facing in any direction at the end. If the bottom row length is even, Karel can stop in either position (1, n // 2) or (1, n // 2 + 1).

Important You can only write if or if/else statements and function calls in the body of main(). You may not write assignment statements, def statements, lambda expressions, or while/for statements.