Recursive Functions in Python
#############################################
# Lab assignment 6: Recursion
#############################################
#############################################
#
# The topic is recursion. Please write
# a recursive funcion for each of the problems
# below.
##############################################
#
# 1. This function is passed a string or a list, and
# returns its length. You MAY NOT use the Python len( ) function.
# >>>len_r([1,2,3])
3
# >>>len_r(‘abcdef’)
6
# >>>len_r(”)
deflen_r(item):
pass
# 2. Write a function called merge. It is passed 2
# lists of integers, both of which are already sorted in ascending
# order. The function should return a new list in which the original
# integers are sorted. Note that the method should be nondestructive.
# You may NOT use the build-in Python sort function or variants.
#
# For example:
#
# >>>merge([1, 3, 4, 6], [0, 1, 2, 5, 7, 8])
# [0, 1, 1, 2, 3, 4, 5, 6, 7, 8]
def merge(lst1, lst2):
if lst1 == []:
return lst2
if lst2 == []:
return lst1
if lst1[0] < lst2[0]:
return [ lst1[0] ] + merge(lst1[1:], lst2)
else:
return [ lst2[0] ] + merge(lst1, lst2[1:])
from copy import copy
# There are not points here. However, as an aside, the merge
# function above can be used as part of a recursive
# sorting algorithm, called merge_sort. Here is the function.
defmergesort(lst):
lst = copy(lst)
iflen(lst) < 2:
returnlst
mid = len(lst)//2
lst1 = mergesort(lst[0:mid])
lst2 = mergesort(lst[mid:])
lst = merge(lst1,lst2)
returnlst
# 3. Write a function which is passed an integer n and
# returns a string consisting of ‘0’s and ‘1’s which
# represent n in binary (base 2). For example:
#
# >>>int_to_binary_string(1)
# ‘1’
# >>>int_to_binary_string(2)
# ’10’
# >>>int_to_binary_string(5)
# ‘1001’
# >>>int_to_binary_string(25)
# ‘11001’
defint_to_binary_string(n):
return ”
# 4. Write a function called fib_list, which returns a list of
# the first n fibinacci numbers. n is passed as a paramter. For example:
#
# >>>fib_list(0)
# [ ]
# >>>fib_list(1)
# [ 1 ]
# >>>fib_list(2)
# [ 1, 1 ]
# >>>fib_list(3)
# [ 1, 1, 2]
# >>>fib_list(4)
# [ 1, 1, 2, 3]
# >>>fib_list(10)
# [ 1, 1, 2, 3, 5, 8, 13, 21, 44, 56 ]
# You may wish to change this code, for example if you
# think of a way to solve the problem with fewer base cases.
# It must still be recursive.
deffib_list(n):
# base case 1
if n == 0:
pass
# base case 2
elif n == 1:
pass
# base case 3
elif n == 2:
pass
else:
pass
# 5. Return the alphabetically last word in a sentence.
# For example:
# >>>last_word_alphabetically([‘it’, ‘was’, ‘the’, ‘best’, ‘of’, ‘times’, ‘it’, ‘was’, ‘the’, ‘worst’, ‘of’, ‘times’])
# ‘worst’
deflast_word_alphabetically(sentence, last_so_far=None):
iflast_so_far == None:
last_so_far = ”
pass
# 6. This function is passed a parameter
# called “expr”. The parameter shoudl be an arithmetic expression,
# An arithmetic expression (expr) is:
#
# (a) an integer, or
# (b) a list in which
# (i) expr[0] is a left parentheses
# (ii) expr[1] is an arithmetic expression
# (iii) expr[2] is an arithmetic operator (‘+’, ‘-‘, or ‘*’)
# (iv) expr[3] is a right parenthesis
#
# Here are some examples:
#
# >>>evaluate(0)
# 0
# >>>evaluate(10)
# 10
# >>> evaluate ( [1, ‘+’, 3] )
4
# >>>evaluate_r ( [ [ 1, ‘+’,3 ], ‘*’, [ [ 2, ‘+’, 3 ], ‘-‘, 1 ] ] )
16
defevaluate_r(expr):
if not isinstance(expr,list):
returnexpr
else:
pass
Solution
# 1. This function is passed a string or a list, and
# returns its length. You MAY NOT use the Python len( ) function.
# >>>len_r([1,2,3])
3
# >>>len_r(‘abcdef’)
6
# >>>len_r(”)
0
deflen_r(item):
if item:
return 1 + len_r(item[1:])
return 0
# 2. Write a function called merge. It is passed 2
# lists of integers, both of which are already sorted in ascending
# order. The function should return a new list in which the original
# integers are sorted. Note that the method should be nondestructive.
# You may NOT use the build-in Python sort function or variants.
#
# For example:
#
# >>>merge([1, 3, 4, 6], [0, 1, 2, 5, 7, 8])
# [0, 1, 1, 2, 3, 4, 5, 6, 7, 8]
def merge(lst1, lst2):
if lst1 == []:
return lst2[:]
if lst2 == []:
return lst1[:]
if lst1[0] <= lst2[0]:
return [ lst1[0] ] + merge(lst1[1:], lst2)
else:
return [ lst2[0] ] + merge(lst1, lst2[1:])
from copy import copy
# There are not points here. However, as an aside, the merge
# function above can be used as part of a recursive
# sorting algorithm, called merge_sort. Here is the function.
defmergesort(lst):
lst = copy(lst)
iflen(lst) < 2:
returnlst
mid = len(lst)//2
lst1 = mergesort(lst[0:mid])
lst2 = mergesort(lst[mid:])
lst = merge(lst1,lst2)
returnlst
# 3. Write a function which is passed an integer n and
# returns a string consisting of ‘0’s and ‘1’s which
# represent n in binary (base 2). For example:
#
# >>>int_to_binary_string(1)
# ‘1’
# >>>int_to_binary_string(2)
# ’10’
# >>>int_to_binary_string(5)
# ‘1001’
# >>>int_to_binary_string(25)
# ‘11001’
# assuming n >= 0
defint_to_binary_string(n):
if n == 0:
return ‘0’
if n == 1:
return ‘1’
returnint_to_binary_string(n // 2) + str(n % 2)
# 4. Write a function called fib_list, which returns a list of
# the first n fibinacci numbers. n is passed as a paramter. For example:
#
# >>>fib_list(0)
# [ ]
# >>>fib_list(1)
# [ 1 ]
# >>>fib_list(2)
# [ 1, 1 ]
# >>>fib_list(3)
# [ 1, 1, 2]
# >>>fib_list(4)
# [ 1, 1, 2, 3]
# >>>fib_list(10)
# [ 1, 1, 2, 3, 5, 8, 13, 21, 44, 56 ]
# You may wish to change this code, for example if you
# think of a way to solve the problem with fewer base cases.
# It must still be recursive.
deffib_list(n):
# base case 1
if n == 0:
return [ ]
# base case 2
elif n == 1:
return [ 1 ]
# base case 3
elif n == 2:
return [ 1, 1 ]
else:
lst = fib_list(n – 1)
returnlst + [ lst[-2] + lst[-1] ]
# 5. Return the alphabetically last word in a sentence.
# For example:
# >>>last_word_alphabetically([‘it’, ‘was’, ‘the’, ‘best’, ‘of’, ‘times’, ‘it’, ‘was’, ‘the’, ‘worst’, ‘of’, ‘times’])
# ‘worst’
deflast_word_alphabetically(sentence, last_so_far=None):
if sentence == []:
returnlast_so_far
iflast_so_far == None or last_so_far< sentence[0]:
last_so_far = sentence[0]
returnlast_word_alphabetically(sentence[1:], last_so_far)
# 6. This function is passed a parameter
# called “expr”. The parameter shoudl be an arithmetic expression,
# An arithmetic expression (expr) is:
#
# (a) an integer, or
# (b) a list in which
# (i) expr[0] is a left parentheses
# (ii) expr[1] is an arithmetic expression
# (iii) expr[2] is an arithmetic operator (‘+’, ‘-‘, or ‘*’)
# (iv) expr[3] is a right parenthesis
#
# Here are some examples:
#
# >>>evaluate(0)
# 0
# >>>evaluate(10)
# 10
# >>> evaluate ( [1, ‘+’, 3] )
# 4
# >>>evaluate_r ( [ [ 1, ‘+’,3 ], ‘*’, [ [ 2, ‘+’, 3 ], ‘-‘, 1 ] ] )
# 16
defevaluate_r(expr):
if not isinstance(expr,list):
returnexpr
else:
v1 = evaluate_r(expr[0])
op = expr[1]
v2 = evaluate_r(expr[2])
if op == ‘+’:
return v1 + v2
if op == ‘-‘:
return v1 – v2
if op == ‘*’:
return v1 * v2
return 0 # should not happen