python算法之递归思想

wulaxiaohei 2020-02-17

#递归思想#基本原理:函数内部调用函数本身,注意:至少有一个终止条件#例1.斐波那契数列def fib(x):    if x==1 or x==2:        return 1    else:        return fib(x-1) + fib(x-2)def fibList(x):    fibList = []    for i in range(x):        fibList.append(fib(i+1))    return fibListprint(fibList(9))#例2.n的阶乘(n*(n-1)*(n-2)*...2*1)def jiecheng(n):    if n==1:        return 1    else:        return n*jiecheng(n-1)print(jiecheng(4))#例3.用递归实现二分查找def binarysearch(numList, x, low, high):    if low > high:        return None    mid = (low + high) // 2    if x == numList[mid]:        return mid    elif x > numList[mid]:        return binarysearch(numList, x, mid+1, high)    else:        return binarysearch(numList, x ,low, mid-1)numList = [1,2,4,5,6,8,12,24,32,44]print(binarysearch(numList, 8, 0, len(numList)-1))

相关推荐