# 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