# CS61A Homework 3-Recursion, Tree Recursion Solved

30.00 \$

Category:
Click Category Button to View Your Next Assignment | Homework

You'll get a download link with a: . ` zip` solution files instantly, after Payment

## Description

Rate this product

## Instructions

Download hw03.zip (hw03.zip). Inside the archive, you will nd a le called hw03.py (hw03.py), along with a copy of the ok autograder.

Submission: When you are done, submit with python3 ok –submit . You may submit more than once before the deadline; only the nal submission will be scored. Check that you have successfully submitted your code on okpy.org (https://okpy.org/). See Lab 0 (/lab/lab00#submitting-the-assignment) for more instructions on submitting assignments.

Using Ok: If you have any questions about using Ok, please refer to this guide. (/articles/using-ok)

Readings: You might nd the following references useful:

Grading: Homework is graded based on correctness. Each incorrect problem will decrease the total score by one point. There is a homework recovery policy as stated in the syllabus. This homework is out of 2 points.

# Required Questions

## Q1: Num eights

Write a recursive function num_eights that takes a positive integer pos and returns the number of times the digit 8 appears in pos .

Important: Use recursion; the tests will fail if you use any assignment statements. (You can however use function de nitions if you so wish.)

def num_eights(pos):

“””Returns the number of times 8 appears as a digit of pos.

>>> num_eights(3)

0

>>> num_eights(8)

1

>>> num_eights(88888888)

8

>>> num_eights(2638)

1

>>> num_eights(86380)

2

>>> num_eights(12345)

0

>>> from construct_check import check

>>> # ban all assignment statements

>>> check(HW_SOURCE_FILE, ‘num_eights’,

…Â Â Â Â Â Â  [‘Assign’, ‘AnnAssign’, ‘AugAssign’, ‘NamedExpr’])

True

“””

“*** YOUR CODE HERE ***”

Use Ok to test your code:

python3 ok -q num_eightsÂ Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â  âœ‚

## Q2: Ping-pong

The ping-pong sequence counts up starting from 1 and is always either counting up or counting down. At element k , the direction switches if k is a multiple of 8 or contains the digit 8. The rst 30 elements of the ping-pong sequence are listed below, with direction swaps marked using brackets at the 8th, 16th, 18th, 24th, and 28th elements:

 Index 1 2 3 4 5 6 7 [8] 9 10 11 12 13 14 15 [16] 17 [18] 19 20 21 22 23 PingPong Value 1 2 3 4 5 6 7 [8] 7 6 5 4 3 2 1 [0] 1 [2] 1 0 -1 -2 -3 Index (cont.) [24] 25 26 27 [28] 29 30 PingPong Value [-4] -3 -2 -1 [0] -1 -2

Implement a function pingpong that returns the nth element of the ping-pong sequence without using any assignment statements. (You are allowed to use function de nitions.)

You may use the function num_eights , which you de ned in the previous question.

Important: Use recursion; the tests will fail if you use any assignment statements. (You can however use function de nitions if you so wish.)

“””Return the nth element of the ping-pong sequence.

>>> pingpong(8)

8

>>> pingpong(10)

6

>>> pingpong(15)

1Â Â Â  >>> pingpong(21)

-1

>>> pingpong(22)

-2

>>> pingpong(30)

-2

>>> pingpong(68)

0Â Â Â  >>> pingpong(69)

-1

>>> pingpong(80)

• >>> pingpong(81)
• >>> pingpong(82)

0

>>> pingpong(100)

-6

>>> from construct_check import check

>>> # ban assignment statements

>>> check(HW_SOURCE_FILE, ‘pingpong’,

…Â Â Â Â Â Â  [‘Assign’, ‘AnnAssign’, ‘AugAssign’, ‘NamedExpr’])

True

“””

“*** YOUR CODE HERE ***”

Use Ok to test your code:

python3 ok -q pingpongÂ Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â  âœ‚

## Q3: Missing Digits

Write the recursive function missing_digits that takes a number n that is sorted in non-decreasing order (for example, 12289 is valid but 15362 and 98764 are not). It returns the number of missing digits in n . A missing digit is a number between the rst and last digit of n of a that is not in n .

Important: Use recursion; the tests will fail if you use any loops.

def missing_digits(n):

“””Given a number a that is in sorted, non-decreasing order,Â Â Â  return the number of missing digits in n. A missing digit isÂ Â Â  a number between the first and last digit of a that is not in n.Â Â Â  >>> missing_digits(1248) # 3, 5, 6, 7

4Â Â Â  >>> missing_digits(19) # 2, 3, 4, 5, 6, 7, 8

7Â Â Â  >>> missing_digits(1122) # No missing numbers

0Â Â Â  >>> missing_digits(123456) # No missing numbers

0Â Â Â  >>> missing_digits(3558) # 4, 6, 7

3Â Â Â  >>> missing_digits(35578) # 4, 6

2Â Â Â  >>> missing_digits(12456) # 3

1Â Â Â  >>> missing_digits(16789) # 2, 3, 4, 5

4

>>> missing_digits(4) # No missing numbers between 4 and 4

0

>>> from construct_check import check

>>> # ban while or for loops Â Â Â >>> check(HW_SOURCE_FILE, ‘missing_digits’, [‘While’, ‘For’])

True

“””

“*** YOUR CODE HERE ***”

Use Ok to test your code:

python3 ok -q missing_digitsÂ Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â  âœ‚

## Q4: Count coins

Given a positive integer change , a set of coins makes change for change if the sum of the values of the coins is change . Here we will use standard US Coin values: 1, 5, 10, 25. For example, the following sets make change for 15 :

15 1-cent coins

10 1-cent, 1 5-cent coins

5 1-cent, 2 5-cent coins

5 1-cent, 1 10-cent coins

3 5-cent coins

1 5-cent, 1 10-cent coin

Thus, there are 6 ways to make change for 15 . Write a recursive function count_coins that takes a positive integer change and returns the number of ways to make change for change using coins.

You can use either of the functions given to you:

ascending_coin will return the next larger coin denomination from the input, i.e. ascending_coin(5) is 10 . descending_coin will return the next smaller coin denomination from the input, i.e. descending_coin(5) is 1 .

There are two main ways in which you can approach this problem. One way uses ascending_coin , and another uses descending_coin .

Important: Use recursion; the tests will fail if you use loops.

functions.html#example-partitions) of count_partitions for an example of how to count the ways to sum up to a nal value with smaller parts. If you need to keep track of more than one value across recursive calls, consider writing a helper function.

def ascending_coin(coin):

“””Returns the next ascending coin in order.Â Â Â  >>> ascending_coin(1)

5Â Â Â  >>> ascending_coin(5)

10Â Â Â  >>> ascending_coin(10)

25 Â Â Â >>> ascending_coin(2) # Other values return None

“”” Â Â Â if coin == 1:Â Â Â Â Â Â Â  return 5Â Â Â  elif coin == 5:Â Â Â Â Â Â Â  return 10 Â Â Â elif coin == 10:Â Â Â Â Â Â Â  return 25

def descending_coin(coin):

“””Returns the next descending coin in order.

>>> descending_coin(25)

10

>>> descending_coin(10)

5Â Â Â  >>> descending_coin(5)

1Â Â Â  >>> descending_coin(2) # Other values return None

“”” Â Â Â if coin == 25:Â Â Â Â Â Â Â  return 10 Â Â Â elif coin == 10:Â Â Â Â Â Â Â  return 5Â Â Â  elif coin == 5:Â Â Â Â Â Â Â  return 1

def count_coins(change):

“””Return the number of ways to make change using coins of value of 1, 5, 10, 25.

>>> count_coins(15)

6

>>> count_coins(10)

4

>>> count_coins(20)

9 Â Â Â >>> count_coins(100) # How many ways to make change for a dollar?

242Â Â Â  >>> count_coins(200)

1463Â Â Â  >>> from construct_check import check

>>> # ban iterationÂ Â Â  >>> check(HW_SOURCE_FILE, ‘count_coins’, [‘While’, ‘For’])

True

“””

“*** YOUR CODE HERE ***”

Use Ok to test your code:

python3 ok -q count_coinsÂ Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â  âœ‚

# Just for fun Questions

## Q5: Towers of Hanoi

A classic puzzle called the Towers of Hanoi is a game that consists of three rods, and a number of disks of di erent sizes which can slide onto any rod. The puzzle starts with n disks in a neat stack in ascending order of size on a start rod, the smallest at the top, forming a conical shape.

Complete the de nition of move_stack , which prints out the steps required to move n disks from the start rod to the end rod without violating the rules. The provided print_move function will print out the

step to move a single disk from the given origin to the given destination .

Hint: Draw out a few games with various n on a piece of paper and try to nd a pattern of disk movements that applies to any n . In your solution, take the recursive leap of faith whenever you need to move any amount of disks less than n from one rod to another. If you need more help, see the following hints.

def print_move(origin, destination):

“””Print instructions to move a disk.”””

print(“Move the top disk from rod”, origin, “to rod”, destination)

def move_stack(n, start, end):

“””Print the moves required to move n disks on the start pole to the endÂ Â Â  pole without violating the rules of Towers of Hanoi.

n — number of disksÂ Â Â  start — a pole position, either 1, 2, or 3Â Â Â  end — a pole position, either 1, 2, or 3

There are exactly three poles, and start and end must be different. AssumeÂ Â Â  that the start pole has at least n disks of increasing size, and the endÂ Â Â  pole is either empty or has a top disk larger than the top n start disks.

>>> move_stack(1, 1, 3)

Move the top disk from rod 1 to rod 3

>>> move_stack(2, 1, 3)

Move the top disk from rod 1 to rod 2

Move the top disk from rod 1 to rod 3

Move the top disk from rod 2 to rod 3

>>> move_stack(3, 1, 3)

Move the top disk from rod 1 to rod 3

Move the top disk from rod 1 to rod 2

Move the top disk from rod 3 to rod 2

Move the top disk from rod 1 to rod 3

Move the top disk from rod 2 to rod 1

Move the top disk from rod 2 to rod 3Â Â Â  Move the top disk from rod 1 to rod 3

“”” Â Â Â assert 1 <= start <= 3 and 1 <= end <= 3 and start != end, “Bad start/end”Â Â Â  “*** YOUR CODE HERE ***”

Use Ok to test your code:

python3 ok -q move_stackÂ Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â  âœ‚

## Q6: Anonymous factorial

>>> fact = lambda n: 1 if n == 1 else mul(n, fact(sub(n, 1)))

>>> fact(5)

120

However, this implementation relies on the fact (no pun intended) that fact has a name, to which we refer in the body of fact . To write a recursive function, we have always given it a name using a def or assignment statement so that we can refer to the function within its own body. In this question, your job is to de ne fact recursively without giving it a name!

Write an expression that computes n factorial using only call expressions, conditional expressions, and

lambda expressions (no assignment or def statements).

The sub and mul functions from the operator module are the only built-in functions required to solve this problem.

from operator import sub, mul

def make_anonymous_factorial():

“””Return the value of an expression that computes factorial.

>>> make_anonymous_factorial()(5)

120

>>> from construct_check import check

>>> # ban any assignments or recursion

>>> check(HW_SOURCE_FILE, ‘make_anonymous_factorial’,

…Â Â Â Â  [‘Assign’, ‘AnnAssign’, ‘AugAssign’, ‘NamedExpr’, ‘FunctionDef’, ‘Recursion’])

True

“”” Â Â Â return ‘YOUR_EXPRESSION_HERE’

Use Ok to test your code:

python3 ok -q make_anonymous_factorialÂ Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â  âœ‚