递归函数

1. 使用递归函数实现sum

def mysum(mylist):
    if len(mylist)==0:
        return 0
    else:
        return mylist.pop()+mysum(mylist)

mylist=[1,2,2,3,4]
print(mysum(mylist))

2. 编写一个递归函数来计算列表中包含的元素数

def mysum(mylist):
    if len(mylist)==0:
        return 0
    else:
        mylist.pop()
        return 1+mysum(mylist)

mylist=[1,2,2,3,4]
print(mysum(mylist))

3.找出列表中的最大数字

 def max(list):
    if len(list)==2:
        return list[0] if list[0]>list[1] else list[1]
    sub_max=max(list[1:])
    return list[0] if list[0]>sub_max else sub_max 

print(max([1,3,0,7,8]))

通常编写涉及数组的递归函数时，基线条件就是数组为空或者只包含一个元素，陷入困境时，请检查基线条件是不是这样的。

4. 使用递归实现快排

def sort_by_q(mylist):
    if len(mylist)<2:
        return mylist
    else:
        select=mylist[0]
        left=[i for i in mylist[1:] if i<=select]
        right=[i for i in mylist[1:] if i>select]
        return sort_by_q(left)+[select]+sort_by_q(right)
print(sort_by_q([1,2,3,9,0,1,22,33]))