PhoneGap中文网

 找回密码
 立即注册
查看: 15583|回复: 0
打印 上一主题 下一主题

Python中的递归函数及二分查找算法如何使用?

[复制链接]

87

主题

87

帖子

327

积分

中级会员

Rank: 3Rank: 3

积分
327
跳转到指定楼层
楼主
发表于 2017-8-4 17:52:15 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式

本文和大家分享的主要是python的递归函数及二分查找算法相关内容,一起来看看吧,希望对大家学习python有所帮助。

  一、递归的定义

  def story():

  s = """

  从前有个山,山里有座庙,庙里老和尚讲故事,

  讲的什么呢?

  """

  print(s)

  story()

  story()

  老和尚讲故事

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

  递归的最大深度:997

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

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

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

  n = 0def f():

  global n

  n += 1

  print(n)

  f()

  f()

  测试递归最大深度

  如何修改递归最大深度:

  import sys #所有和python相关的设置和方法

  sys.setrecursionlimit(10000000)

  n = 0def 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+1def 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

  递归函数与三级菜单

  递归函数实现三级菜单

  二、二分查找算法

  给你一个数列让你找出其中一个数的位置你怎么找?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 = 0for 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



来源:博客园


it营
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

站长推荐 上一条 /1 下一条

ionic4视频教程

Archiver|手机版|小黑屋| PhoneGap中文网 ( 京ICP备13027796号-1 )  

GMT+8, 2024-12-22 16:11 , Processed in 0.043044 second(s), 28 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表