# 递归算法的三大特点
# 1、递归过程一般通过函数或子过程来实现
# 2、递归算法在函数或子过程的内部，直接或间接调用自己的算法
# 3、递归算法实际上是把问题转换为规模缩小的同类问题的子问题，然后递归调用函数或过程来表示问题的解
# 递归算法要注意的事项
# 1、递归是在过程或函数中调用自身的过程
# 2、递归必须有一个明确的递归结束条件，成为递归出口
# 3、递归算法比较简洁，但运行效率较低
# 4、递归调用过程，系统用栈来存储每一层的返回点和局部量，如果递归次数过多，容易造成栈溢出
#递归算法的三大特点#1、递归过程一般通过函数或子过程来实现#2、递归算法在函数或子过程的内部，直接或间接调用自己的算法#3、递归算法实际上是把问题转换为规模缩小的同类问题的子问题，然后递归调用函数或过程来表示问题的解#递归算法要注意的事项#1、递归是在过程或函数中调用自身的过程#2、递归必须有一个明确的递归结束条件，成为递归出口#3、递归算法比较简洁，但运行效率较低#4、递归调用过程，系统用栈来存储每一层的返回点和局部量，如果递归次数过多，容易赵成栈溢出#斐波那契数列fiblist={}deffibnum(n):if(n<=1):return1ifnnotinfiblist:fiblist[n]=fibnum(n-1)+fibnum(n-2)returnfiblist[n]deffibrecur(n):assertn>=0,"n>0"ifn<=1:return1returnfibrecur(n-1)+fibrecur(n-2)defmove(n,a,b,c):ifn==1:print(a,'-->',c)returnelse:move(n-1,a,c,b)move(1,a,b,c)move(n-1,b,a,c)defbinary_search(alist,item):iflen(alist)==0:returnFalseelse:midpoint=len(alist)//2ifalist[midpoint]==item:returnTrueelse:ifitem<alist[midpoint]:returnbinary_search(alist[:midpoint],item)else:returnbinary_search(alist[midpoint+1:],item)defbinary_search2(min,max,d,n):#min表示有序列表头部索引#max表示有序列表尾部索引#d表示有序列表#n表示需要寻找的元素mid=(min+max)//2ifmax<min:print('未找到%s'%d[mid])elifd[mid]<n:print('向右侧找！')binary_search2(mid+1,max,d,n)elifd[mid]>n:print('向左侧找！')binary_search2(min,mid-1,d,n)elifd[mid]==n:print('索引{0}找到了目标值{1}'.format(mid,n))if__name__=='__main__':foriinrange(0,20):print('loop-',i,fibnum(i))foriinrange(0,20):print(i,':',fibrecur(i),end='')#12:23:34:55:86:137:218:349:5510:8911:144#12:23313:37714:61015:98716:159717:258418:418119:676589print(fibrecur(6))#13num=4print('把',num,'个盘子全部移到C柱子的顺序为：')move(num,'A','B','C')data=[1,3,6,13,56,123,345,1024,3223,6688]print(binary_search(data,3223))print(binary_search(data,3333))binary_search2(0,len(data)-1,data,3223)binary_search2(0,len(data)-1,data,3333)
