# Discussion 4: Recursion

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 the year of your life you think you enjoyed most (Kindergarten, senior year of high school, etc.).

# 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!)

`print`

the first line of the output, then make a recursive call, then `print`

the last line of the output.
### Q2: Skip Factorial

Define the base case for the `skip_factorial`

function, which returns the product of **every other positive integer**, starting with `n`

.

`n`

is even, then the base case will be 2. If `n`

is odd, then the base case will be 1. Try to write a condition that handles both possibilities.
### Q3: 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.

`even`

always makes a recursive call to `hailstone`

and returns one more than the length of the rest of the hailstone sequence.
An odd number might be 1 (the base case) or greater than one (the recursive case). Only the recursive case should call `hailstone`

.

# 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**. If you don't get to them, it's a great idea to schedule some time outside of lab to work on them together.

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

### Q4: 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).

First check if `i`

is a multiple of 7 or contains a 7, and if so, switch
directions. Then, add the direction to `who`

and ensure that `who`

has not
become smaller than 1 or greater than `k`

.

### Q5: 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.

`i`

and `n`

evenly divides `n`

. Then you can call it starting with `i=2`

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