Discussion 3: Recursion, Tree Recursion

Attendance

Your TA will come around during discussion to check you in.

If you miss discussion for a good reason (such as sickness or a scheduling conflict), email cs61a@berkeley.edu within one week to receive attendance credit.

Q1: Skip Factorial

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

Q2: 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!)

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) loop.

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.

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.

Q5: Maximum Subsequence

A subsequence of a number is a series of digits from the number (not necessarily contiguous). For example, 12345 has subsequences like 123, 234, 124, 245, etc. Your task is to find the largest subsequence that is under a specified length.

Hint: To add a digit (d) to an existing number (n), calculate: n * 10 + d. For instance, to add the digit 8 to 15 to get 158, compute 15 * 10 + 8.

Q6: 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

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 following:

  • 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).