python算法-递归
#递归思想
#基本原理：函数内部调用函数本身，注意：至少有一个终止条件
#例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 fibList
print(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))
版权声明：本文为xhw19950606原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。