递归练习

这几道题目难度都不大，甚至有些不用递归会有更简洁的方式实现。但强制自己用递归实现出来，对于学习这种解决问题的方法还是有帮助的。
对于判断出能用递归解决的问题，可以先把“归”确定下来，然后再想如何“递”，并把“递”的各种情况考虑清楚、完善，整道题目应该就解决得差不多了。

题目

cube_vals_rec()

question:

wrire a function cube_vals_rec(values) that takes as input a list of numbers called values, and that uses recursion to create and return a list containing the cubes of the numbers in values. For example:

cube_vals_rec([-2,5,4,-3])   # return [-8,125,64,-27]

resolution:

# python 3.5
def cube_vals_rec(values):
if(len(values)==0):
    return []
else :
    return [values[0]**3]+(cube_vals_rec(values[1:]))

if __name__=="__main__":
    print(cube_vals_rec([-2,5,4,-3]))

num_greater()

question:

3)write a function called num_greater(threshold, values) that takes as inputs a number threshold and a list of numbers values, and that returns the number of elements of values that are greater than threshold that threshold. For example:

num_greater(5,[1,7,3,5,10])     # return    2
num_greater(10,[1,7,3,5,10])    # return    0

resolution:

def num_greater(threshold, values):
if len(values)==0:
   return 0
if values[0]<= (threshold):
   return num_greater(threshold, values[1:])
else:
    return 1+ num_greater(threshold, values[1:])

if __name__=="__main__":
    print(num_greater(5,[1,7,3,5,10]))
    print(num_greater(10,[1,7,3,5,10]))

index_last()

question:

4.1)write a function index_last(c, s) that takes as inputs a character c and a string s and that uses recursion to find and return the index of the last occurrence of c(if any) in the string s.If the character c is not found in s,please return -1. For example:

index_last('a','banana')        # return    5
index_last('x','hello')         # return    -1

resolution:

def index_last(c,s):
if(len(s)==0):
    return -1
elif(c==s[-1]):
    return len(s)-1
else:
    return index_last(c,s[:-1])

if __name__=="__main__":
    print( index_last('a','banana'))
    print( index_last('x','hello'))

lcs()

question:

4.3)write a function lcs(s1, s2) that takes two strings s2 and s2 and uses recursion to return the longest common subsequence(LCS) that they share.The LCS is a string whose letters appear in both s1 and s2; these letters must appear in the same order in both s1 and s2,but not necessarily comsecutively. For example:

lcs('human', 'chimp')           # return    'hm'
lcs('abcdefg','efghabcd')       # return    'abcd' ('efgh' would also be fine)

resolution:

def lcs(s1,s2):
if(len(s1)==0 or len(s2)==0):
    return ''
elif(s1[0]==s2[0]):
    return s1[0]+lcs(s1[1:],s2[1:])
else:
    result1 = lcs(s1[1:],s2)
    result2 = lcs(s1,s2[1:])
    if (len(result1)>len(result2)):
        return result1
    else:
        return result2

if __name__=="__main__":
    print( lcs('human', 'chimp'))
    print( lcs('gattaca','tacgaata'))
    print( lcs('','whew'))
    print( lcs('abcdefg','efghabcd'))