人理解循环,神理解递归!

 

本篇导航:

一、递归的定义

def story():
s = """
从前有个山,山里有座庙,庙里老和尚讲故事,
讲的什么呢?
"""
print(s)
story() story()

老和尚讲故事

递归的定义——在一个函数里再调用这个函数本身。这种魔性的使用函数的方式就叫做递归

递归的最大深度:997

1、python递归最大层数限制 997

2、最大层数限制是python默认的,可以做修改

3、但是我们不建议你修改

n = 0
def f():
global n
n += 1
print(n)
f() f()

测试递归最大深度

如何修改递归最大深度:

import sys #所有和python相关的设置和方法
sys.setrecursionlimit(10000000)
n = 0
def f():
global n
n += 1
print(n)
f() f()

修改递归最大深度

递归的小实践:

1、猜年龄:

#猜e的年龄
#e比d大两岁
#d比c大两岁
#c比b大两岁
#b比a大两岁
#a 40了 # 1.a age(1) = 40
# 2.b age(1) + 2
# 3.c age(2) + 2
# 4.d age(3) + 2
# 5.e age(4) + 2 def age(n):
if n == 1:
return 40
else:
ret = age(n-1)
return ret + 2
age(5)

猜年龄

2、一个数,除2到不能整除2为止:

#一个数,除2到不能整除2为止(以8为例)
def cal(num):
if num % 2 == 0:
num = num // 2
return cal(num)
else:
return num print(cal(8))

数字整除类1

3、整除类2

#如果一个数 可以整除2 就整除
#不能整除就*3+1
def func(num):
print(num)
if num == 1:
return
if num %2 == 0:
num = num //2
else:
num = num * 3 + 1
func(num) func(5)

数字整除类2

递归函数与三级菜单

menu = {
'北京': {
'海淀': {
'五道口': {
'soho': {},
'网易': {},
'google': {}
},
'中关村': {
'爱奇艺': {},
'汽车之家': {},
'youku': {},
},
'上地': {
'百度': {},
},
},
'昌平': {
'沙河': {
'老男孩': {},
'北航': {},
},
'天通苑': {},
'回龙观': {},
},
'朝阳': {},
'东城': {},
},
'上海': {
'闵行': {
"人民广场": {
'炸鸡店': {}
}
},
'闸北': {
'火车战': {
'携程': {}
}
},
'浦东': {},
},
'山东': {},
} def threeLM(dic):
while True:
for k in dic:print(k)
key = input('input>>').strip()
if key == 'b' or key == 'q':return key
elif key in dic.keys() and dic[key]:
ret = threeLM(dic[key])
if ret == 'q': return 'q'
elif (not dic.get(key)) or (not dic[key]) :
continue threeLM(menu)

递归函数实现三级菜单


二、二分查找算法

给你一个数列让你找出其中一个数的位置你怎么找?index?这是python给我们的内置函数。那他内部是怎么实现的呢?现在要求我们自己设计函数来实现这个功能。

数列例如:l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]

i = 0
for num in l:
if num == 66:
print(i)
i+=1

是不是感觉这个函数so easy但是我们所用的方法是循环列表然后一个一个对比。这个方法固然可以可是也只是适用于小的数组。如果这个数列很长里面上万甚至更多,一个一个找效率太低。必须有一个新的算法来解决这个问题。这就引出了今天另一个知识点二分查找

二分查找算法:

算法:计算的方法

二分查找前提:有序的递增列表

图示:

这就是二分查找算法

简单二分法:

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]

def func(l,aim):
mid = (len(l)-1)//2
if l:
if aim > l[mid]:
func(l[mid+1:],aim)
elif aim < l[mid]:
func(l[:mid],aim)
elif aim == l[mid]:
print("bingo",mid)
else:
print('找不到')
func(l,66)
func(l,6)

二分法基础版

二分法升级:

def func(l, aim,start = 0,end = len(l)-1 ):
mid = (start+end)//2
if not l[start:end+1]:
return
elif aim > l[mid]:
return func(l,aim,mid+1,end)
elif aim < l[mid]:
return func(l,aim,start,mid-1)
elif aim == l[mid]:
print("bingo")
return mid index = func(l,68)
print(index)

二分法查找升级版

小结:

递归解决的问题:

就是通过参数,来控制每一次调用缩小计算的规模

适合的场景:

数据的规模在减小,但是解决问题的思路没有改变

结束递归的标志:return


思维导图:

最新文章

  1. ORACLE DELETE数据慢的案例
  2. Windows请求连接 Vmware+Ubuntu14被拒绝 的幽怨诉说
  3. WCF绑定类型选择
  4. [笔记] Duke - 统计预测
  5. SqlServer表数据与excel中数据的互相复制
  6. C语言语句分类:大致可分为六大类
  7. sql server 2005 大数据量插入性能对比
  8. 52. 模版和设计元素——Lotus Notes的代码重用
  9. 轻松学会多线程(四)——synchronized同步keyword知多少
  10. Node.js基础知识
  11. STM32F4的FPU单元讲解
  12. poj3159 Candies SPFA
  13. gulp环境搭建
  14. 201621123057 《Java程序设计》第8周学习总结
  15. WPF 添加 Resources Dictionary 资源 一般类库项目中无法添加资源文件(ResourceDictionary)
  16. 利用本地浏览器远程服务器上的jupyter notebook
  17. Advanced Installer 14.9 – WPF或winform应用程序打包成exe文件
  18. linux系统下各类软件安装笔记
  19. python内置函数每日一学 -- any()
  20. SQLSERVER 查看操作系统内存

热门文章

  1. MyBatis介绍
  2. [转] 传说中的WCF(2):服务协定的那些事儿
  3. 开发抓包工具 Mac charles 3.11.5 破解版 安装包
  4. ecshop屏蔽wap功能
  5. 探索Windows命令行系列(5):几个实用的命令例解
  6. 如何利用php+android+新浪sae服务器做一个app下载应用
  7. php随机获取验证码
  8. 在MacOS中,Unity使用VSCode开发,4.7版本无法正常使用C#
  9. 不错的 HttpHelper类 c#
  10. Java多线程中join方法详解