Assignment

########################################################

#

# This lab is about writing recursive functions when

# one of the parameters may be a list with possibly

# embedded lists, or a list which does not contain

# emedded lists, or possibly something which is not

# a list.

#

# I’ve included the examples of any kind of recursion

# that we have completed during lecture for your

# reference.  The lab problems can be found after

# the in-class examples.

#

# There are 4 functions in the lab, which you must

# complete.

# Please make sure that he can run lab_test.py

# (which imports the code that you write)

# all the way through without the program crashing.

#

#

########################################################

def factorial(n):

‘recursive version of factorial’

#start with base case which we know the answer to without any calculation

if n == 1:

return 1

else:

return n * factorial(n-1)

# a utility function, meant to help visualize recursion

defprint_with_space(var, level=0):

if level == 0:

print(var)

else:

print(‘   ‘, end=”)

print_with_space(var, level-1)

# so that we can see the levels of recursion

deffactorial_print(n, level=0):

print_with_space(‘factorial({})’.format(n), level)

answer = 1

if n > 1:

answer = n * factorial_print(n-1, level+1)

print_with_space(answer, level)

return answer

deffactorial_loop(n):

‘nonrecursive version of factorial’

answer = 1

for i in range(1,n+1):

answer *= i

return answer

# recursive version of exp

defexp(x, y):

if y == 0:

return 1

return x * exp(x, y-1)

# nonrecursive version of exp

defexp_loop(x,y):

‘iterative version of computing x to the y power’

answer = 1

for i in range(y,0,-1):

answer *= x

return answer

defexp_print(x,y,level=0):

print_with_space(‘exp({},{})’.format(x,y), level)

if y == 0:

print_with_space(1, level)

return 1

answer = x * exp_print(x,y-1,level+1)

print_with_space(answer, level)

return answer

# greatest common divisor (recursive)

# if y divides into x evenly, then gcd(x,y) => y

# otherwise, it’s gcd(y, x%y)

defgcd(x,y):

# base case

ifx%y == 0:

return y

# recursive

else:

returngcd(y, x%y)

#    if y == 0:

#        return x

#    else:

#        return gcd(y,x%y)

# now with a loop instead

defgcd_loop(x,y):

whilex%y != 0:

temp = x

x = y

y = temp % y

return y

# Fibonacci sequence (recursive):  1, 1, 2, 3, 5, 8, 13, 21, 34…

# fib(6) should return 8

def fib(n):

# base case

if n <= 2:

return 1

else:

# recursive case

return fib(n-1) + fib(n-2)

deffib_it(n):

fibs = [1, 1]

for i in range(2,n+1):

print(fibs)

fibs.append(fibs[-1] + fibs[-2])

return fibs[-1]

# write a function that returns [1, 2, 3, …, n-1, n] where n

# is passed as a parameter.  For example:

#

# >>>one_to_n(5)

# [1, 2, 3, 4, 5]

# >>>one_to_n(7)

# [1, 2, 3, 4, 5, 6, 7]

# >>>one_to_n(0)

# [ ]

# write a function that returns the list [1,2,…,n]

# where n is the parameter

# recursive version

defone_to_n(n):

#    print(‘call one_to_n {}’.format(n))

if n == 0:

return [ ]

else:

answer = one_to_n(n-1)

#       print(answer)

return answer + [ n ]

# much more efficient, because of append rather than

# list + operator

def one_to_n_v2(n):

if n == 0:

return [ ]

else:

lst = one_to_n_v2( n-1 )

lst.append(n)

returnlst

defone_to_n_loop(n):

lst = [ ]

for i in range(1,n+1):

lst.append(i)

# again we could have used  lst = lst + [i]

# but then n objects are created

returnlst

# write a recursive function called modulus. It is passed two positive

# integers x and y, and returns the remainder of  x // y.  You may not

# use the % or // operators.  For example:

#

# >>>modulus(7,3)

# 1

# >>>modulus(11,4)

# 3

# x%y

def modulus(x,y):

if x < y:

return x

#    elif x == y:

#        return 0

else:

return modulus( x-y , y)

defmodulus_loop(x,y):

while x >= y:

x -= y

return x

# try

# >>>vowels(‘computer)

# ‘omu’

def vowels(word):

#   print(word)

answer = None

if word == ”:

return ”

elif word[0] in ‘aeiou’:

answer = word[0] + vowels(word[1:])

else:

answer = vowels(word[1:])

#   print(answer)

return answer # word[0] + vowels(word[1:])

# iterative; without the “in” operator

# return True if item is in x (which might be

# a list or str) or False otherwise.  Do not use

# the Python “in” operator in this problem.

# Write it iteratively and then recursively.

# In the iterative version, use a while loop

# No loops are allowed in the recursive version.

defsimplest_occur(item, lst):

return item in lst

# recursive

def occur(item, lst):

# print(lst)

# base cases

iflen(lst) == 0:   # lst == []

return False

eliflst[0] == item:

return True

# one recursive case

else:

return occur(item, lst[1:])

# Count the number of times item appears in x.

# Do NOT use the Python built-in “in” operator or the

# count method.  For the iterative method, use a while loop.

def count(item, lst):

‘recursive’

# base case

iflst == [ ]:

return 0

# 2 recursive cases

eliflst[0] == item:

return 1 + count(item, lst[1:])

else:

return count(item, lst[1:])

defcount_loop(item, lst):

i = 0

for member in lst:

if item == member:

i += 1

return i

# Recursive:  return True if word is a palindrome, or False otherwise

def pal(word):

print(word)

#    if word == ”:

#        return True

iflen(word) <= 1:

return True

elif word[0] != word[-1]:

return False

else:

return pal(word[1:-1])

# Recursive:  return a copy of lst

defcopy_r(lst):

iflst == []:

return list()

else:

return [ lst[0] ] + copy_r(lst[1:])

##############################################

##############################################

# THIS IS THE BEGINNING OF THE LAB

##############################################

##############################################

# Please start the lab by looking at the

# completed example below.  If you don’t understand

# how it works, please ask your TA to explain.

# Then you can use this as example for the

# functions which you must complete below

# >>>len_embed(2)

# 1

# >>>len_embed([])

# 0

# >>>len_embed([[1,2], [3, [4, 5], 6]])

# 6

deflen_embed(x):

# note that eventually in the recursion, we will

# get to the point where x is not a list.

if not isinstance(x, list):

return 1

elif x == [ ]:

print(0)

return 0

else:

sum = len_embed(x[0]) + len_embed(x[1:])

print(sum)

return sum

##############################################

# Lab problem 1

##############################################

# return True if item occurs somewhere in x.

#

# >>>occurs_embed(5, 5)

# True

# >>>occurs_embed(5, 10)

# False

# >>>occurs_embed(5, [1, 3, 5])

# True

# >>>occurs_embed(4, [[1, 2], [3, [4, 5]]])

# True

# >>>occurs_embed(6, [[3, 1, 2], [[3, 6, 2], [6, 1, 0, 6]]]])

# True

# >>>occurs_embed(7, [[3, 1, 2], [[3, 6, 2], [6, 1, 0, 6]]]])

# False

defoccurs_embed(item, x):

if not isinstance(x, list):

return item == x

elif False:

pass

else:

pass

##############################################

# Lab problem 2

##############################################

# return the maximum number in x (including embedded lists)

#

# For example:

# >>>maximum_embed(1)

# 1

# >>>maximum_embed([1, 2, 3, 1, 6, 4, 5])

# 6

# >>>maximum_embed([1, [2, 3], [[1, [6, 4]], 5]])

# 6

defmaximum_embed(x):

pass

##############################################

# Lab problem 3

##############################################

# return the sum of numbers in x (including embedded lists)

#

# For example:

# >>>sum_embed(1)

# 1

# >>>sum_embed([6, 4, 5])

# 15

# >>>sum_embed([1, [2, 1], [[1, [0, 3]], -1]])

# 7

defsum_embed(x):

pass

##############################################

# Lab problem 4

##############################################

# “flatten” a list. Ideally, flatten should be

# nondestructive

# For example:

# >>>flatten(1)

# 1

# >>>flatten([])

# []

# >>>flatten([1, 3, 2])

# [1, 3, 2]

# >>>flatten([0 [3, 2], [1, [8, 7, [6]]]])

def flatten(x):

pass

 Solution

 lab7.py

 ########################################################

def factorial(n):

‘recursive version of factorial’

#start with base case which we know the answer to without any calculation

if n == 1:

return 1

else:

return n * factorial(n-1)

# a utility function, meant to help visualize recursion

defprint_with_space(var, level=0):

if level == 0:

print(var)

else:

print(‘   ‘, end=”)

print_with_space(var, level-1)

# so that we can see the levels of recursion

deffactorial_print(n, level=0):

print_with_space(‘factorial({})’.format(n), level)

answer = 1

if n > 1:

answer = n * factorial_print(n-1, level+1)

print_with_space(answer, level)

return answer

deffactorial_loop(n):

‘nonrecursive version of factorial’

answer = 1

for i in range(1,n+1):

answer *= i

return answer

# recursive version of exp

defexp(x, y):

if y == 0:

return 1

return x * exp(x, y-1)

# nonrecursive version of exp

defexp_loop(x,y):

‘iterative version of computing x to the y power’

answer = 1

for i in range(y,0,-1):

answer *= x

return answer

defexp_print(x,y,level=0):

print_with_space(‘exp({},{})’.format(x,y), level)

if y == 0:

print_with_space(1, level)

return 1

answer = x * exp_print(x,y-1,level+1)

print_with_space(answer, level)

return answer

# greatest common divisor (recursive)

# if y divides into x evenly, then gcd(x,y) => y

# otherwise, it’s gcd(y, x%y)

defgcd(x,y):

# base case

ifx%y == 0:

return y

# recursive

else:

returngcd(y, x%y)

#    if y == 0:

#        return x

#    else:

#        return gcd(y,x%y)

# now with a loop instead

defgcd_loop(x,y):

whilex%y != 0:

temp = x

x = y

y = temp % y

return y

# Fibonacci sequence (recursive):  1, 1, 2, 3, 5, 8, 13, 21, 34…

# fib(6) should return 8

def fib(n):

# base case

if n <= 2:

return 1

else:

# recursive case

return fib(n-1) + fib(n-2)

deffib_it(n):

fibs = [1, 1]

for i in range(2,n+1):

print(fibs)

fibs.append(fibs[-1] + fibs[-2])

return fibs[-1]

# write a function that returns [1, 2, 3, …, n-1, n] where n

# is passed as a parameter.  For example:

#

# >>>one_to_n(5)

# [1, 2, 3, 4, 5]

# >>>one_to_n(7)

# [1, 2, 3, 4, 5, 6, 7]

# >>>one_to_n(0)

# [ ]

# write a function that returns the list [1,2,…,n]

# where n is the parameter

# recursive version

defone_to_n(n):

#    print(‘call one_to_n {}’.format(n))

if n == 0:

return [ ]

else:

answer = one_to_n(n-1)

#       print(answer)

return answer + [ n ]

# much more efficient, because of append rather than

# list + operator

def one_to_n_v2(n):

if n == 0:

return [ ]

else:

lst = one_to_n_v2( n-1 )

lst.append(n)

returnlst

defone_to_n_loop(n):

lst = [ ]

for i in range(1,n+1):

lst.append(i)

# again we could have used  lst = lst + [i]

# but then n objects are created

returnlst

# write a recursive function called modulus. It is passed two positive

# integers x and y, and returns the remainder of  x // y.  You may not

# use the % or // operators.  For example:

#

# >>>modulus(7,3)

# 1

# >>>modulus(11,4)

# 3

# x%y

def modulus(x,y):

if x < y:

return x

#    elif x == y:

#        return 0

else:

return modulus( x-y , y)

defmodulus_loop(x,y):

while x >= y:

x -= y

return x

# try

# >>>vowels(‘computer)

# ‘omu’

def vowels(word):

#   print(word)

answer = None

if word == ”:

return ”

elif word[0] in ‘aeiou’:

answer = word[0] + vowels(word[1:])

else:

answer = vowels(word[1:])

#   print(answer)

return answer # word[0] + vowels(word[1:])

# iterative; without the “in” operator

# return True if item is in x (which might be

# a list or str) or False otherwise.  Do not use

# the Python “in” operator in this problem.

# Write it iteratively and then recursively.

# In the iterative version, use a while loop

# No loops are allowed in the recursive version.

defsimplest_occur(item, lst):

return item in lst

# recursive

def occur(item, lst):

# print(lst)

# base cases

iflen(lst) == 0:   # lst == []

return False

eliflst[0] == item:

return True

# one recursive case

else:

return occur(item, lst[1:])

# Count the number of times item appears in x.

# Do NOT use the Python built-in “in” operator or the

# count method.  For the iterative method, use a while loop.

def count(item, lst):

‘recursive’

# base case

iflst == [ ]:

return 0

# 2 recursive cases

eliflst[0] == item:

return 1 + count(item, lst[1:])

else:

return count(item, lst[1:])

defcount_loop(item, lst):

i = 0

for member in lst:

if item == member:

i += 1

return i

# Recursive:  return True if word is a palindrome, or False otherwise

def pal(word):

print(word)

#    if word == ”:

#        return True

iflen(word) <= 1:

return True

elif word[0] != word[-1]:

return False

else:

return pal(word[1:-1])

# Recursive:  return a copy of lst

defcopy_r(lst):

iflst == []:

return list()

else:

return [ lst[0] ] + copy_r(lst[1:])

##############################################

##############################################

# THIS IS THE BEGINNING OF THE LAB

##############################################

##############################################

# Please start the lab by looking at the

# completed example below.  If you don’t understand

# how it works, please ask your TA to explain.

# Then you can use this as example for the

# functions which you must complete below

# >>>len_embed(2)

# 1

# >>>len_embed([])

# 0

# >>>len_embed([[1,2], [3, [4, 5], 6]])

# 6

deflen_embed(x):

# note that eventually in the recursion, we will

# get to the point where x is not a list.

if not isinstance(x, list):

return 1

elif x == [ ]:

print(0)

return 0

else:

sum = len_embed(x[0]) + len_embed(x[1:])

print(sum)

return sum

##############################################

# Lab problem 1

##############################################

# return True if item occurs somewhere in x.

#

# >>>occurs_embed(5, 5)

# True

# >>>occurs_embed(5, 10)

# False

# >>>occurs_embed(5, [1, 3, 5])

# True

# >>>occurs_embed(4, [[1, 2], [3, [4, 5]]])

# True

# >>>occurs_embed(6, [[3, 1, 2], [[3, 6, 2], [6, 1, 0, 6]]]])

# True

# >>>occurs_embed(7, [[3, 1, 2], [[3, 6, 2], [6, 1, 0, 6]]]])

# False

defoccurs_embed(item, x):

if not isinstance(x, list):

return item == x

elif x == [ ]:

return False

else:

returnoccurs_embed(item, x[0]) or occurs_embed(item, x[1:])

##############################################

# Lab problem 2

##############################################

# return the maximum number in x (including embedded lists)

#

# For example:

# >>>maximum_embed(1)

# 1

# >>>maximum_embed([1, 2, 3, 1, 6, 4, 5])

# 6

# >>>maximum_embed([1, [2, 3], [[1, [6, 4]], 5]])

# 6

defmaximum_embed(x):

if not isinstance(x, list):

return x

elif x == [ ]:

return None

else:

x1 = maximum_embed(x[0])

x2 = maximum_embed(x[1:])

if x1 == None:

return x2

elif x2 == None:

return x1

elif x1 > x2:

return x1

else:

return x2

##############################################

# Lab problem 3

##############################################

# return the sum of numbers in x (including embedded lists)

#

# For example:

# >>>sum_embed(1)

# 1

# >>>sum_embed([6, 4, 5])

# 15

# >>>sum_embed([1, [2, 1], [[1, [0, 3]], -1]])

# 7

defsum_embed(x):

if not isinstance(x, list):

return x

elif x == [ ]:

return 0

else:

returnsum_embed(x[0]) + sum_embed(x[1:])

##############################################

# Lab problem 4

##############################################

# “flatten” a list. Ideally, flatten should be

# nondestructive

# For example:

# >>>flatten(1)

# 1

# >>>flatten([])

# []

# >>>flatten([1, 3, 2])

# [1, 3, 2]

# >>>flatten([0 [3, 2], [1, [8, 7, [6]]]])

def flatten(x):

if not isinstance(x, list):

return x

elif x == [ ]:

return x

else:

x1 = flatten(x[0])

x2 = flatten(x[1:])

ifisinstance(x1, list):

ifisinstance(x2, list):

return x1 + x2

else:

return x1 + [x2]

elifisinstance(x2, list):

return [x1] + x2

else:

return [x1, x2]