第七章:递归算法
7.1 理解递归
※第一个算法:
累加求和递归算法
def increase(n=3):
if n==1:
return 1
else:
return n+increase(n-1)
print('递归结果:%d'%(increase(3)))
※第二个算法:
递归方式二分法查找值
def bin_search(value,line,start=0,end=0):
mid=(end-start)//2+start
if start>end:
return None
elif line[mid]>value:
return bin_search(value,line,start,mid-1)
elif line[mid]<value:
return bin_search(value,line,mid+1,end)
elif line[mid]==value:
return mid
L=[0,2,3,5,6,8,9,10,21,52,82,100]
maxl=len(L)
result=bin_search(10,L,0,maxl-1)
print('查找结果为:',result)
注:这里的列表必须有序,如果没有有序,使用排序算法重建列表。这是一个下标查找函
数,索引从 0 开始。代码分析:第一次调用函数(10,L,0,11) mid=5 走第三条路径 第二
次调用函数(10,L,6,11) mid=8 走第二条路径 第三次调用函数(10,L,6,7) mid=6 走第
三条路径 第四次调用函数(10,L,7,7) mid=7 递归结束 返回 mid mid 的值为 7 解题思路
采用二分思想拆办查找需要的值。若查找范围内没有此值,返回空值;若比较结果在左边
对左边进行一次调用;若比较结果在右边,对右边进行一次调用。直到有值返回或者超过
递归次数限制。偶数就找偶数除以二就好了,奇数就找奇书除以二向上取整就好了。
※第三个算法:
用递归函数求斐波那契数列
def solve_fibona(n):