python之路(七)-递归算法

递归

特点

递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解。

递归算法解决问题的特点:

(1) 递归就是在过程或函数里调用自身。

(2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。

(3) 递归算法解题通常显得很简洁,但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。

(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。

要求

递归算法所体现的“重复”一般有三个要求:

一是每次调用在规模上都有所缩小(通常是减半);

二是相邻两次重复之间有紧密的联系,前一次要为后一次做准备(通常前一次的输出就作为后一次的输入);

三是在问题的规模极小时必须用直接给出解答而不再进行递归调用,因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件),无条件递归调用将会成为死循环而不能正常结束。

实例:2分查找

现有列表 primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97], 要求尔等 用最快的方式 找出23

def find(args1,args2):
    coun = len(args1)
    mid = int(coun/2)
    if coun >=  1:
        if args1[mid] > args2:
            find(args1[:mid],args2)

        elif args1[mid] < args2:
            find(args1[mid:],args2)
        else:
            print(‘找到了!‘)
    else:

        print(‘没找到‘)
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
find(primes,71)
时间: 01-23

python之路(七)-递归算法的相关文章

PYTHON之路(七)

多态 看到每个动物类都有自己的talk方法,调用时需明确指定是那个动物实例要调用talk方法,才不会错.这时定义一个函数,提供统一的调用接口,是猫就调用猫类的talk方法.完成对多态的模拟.obj参数未指定类型,即可传递任何参数. 比如java语言, 他的统一接口是这样写的: def animalTalk(object obj): print(obj.name,": ", obj.talk()) object obj意思即所有基类都来调用.要不然的明确指明: dog obj 则只能do

Python之路【第七篇】:线程、进程和协程

Python之路[第七篇]:线程.进程和协程 Python线程 Threading用于提供线程相关的操作,线程是应用程序中工作的最小单元. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 #!/usr/bin/env python # -*- coding:utf-8 -*- import threading import time   def show(arg):     time.sleep(1)     print 'thread'+str(arg)   for i in

Python之路【第二篇】:Python基础(一)

Python之路[第二篇]:Python基础(一) 入门知识拾遗 一.作用域 对于变量的作用域,执行声明并在内存中存在,该变量就可以在下面的代码中使用. 1 2 3 if 1==1:     name = 'wupeiqi' print  name 下面的结论对吗? 外层变量,可以被内层变量使用 内层变量,无法被外层变量使用 二.三元运算 1 result = 值1 if 条件 else 值2 如果条件为真:result = 值1如果条件为假:result = 值2 三.进制 二进制,01 八进

Python之路_Day5

Python之路_Day5_课堂笔记 ---------------------------------------------------------------------------------------------------- 前期回顾: 一.python基础 二.基本数据类型 int str list tuple dict set 三.函数式编程 四.装饰器 1.将func当作参数传递给装饰器,并执行 2.将装饰器函数的返回值重新赋值给func ------------------

Python之路_Day12

Python之路_Day12_课堂笔记 上节回顾 一.线程 线程 基本线程使用 队列-消息队列 线程池 进程 基本使用 进程数据共享 进程池 协程 更适用IO操作 二.Memcache.Redis Memcache 集群: (C1,1) (C2,2) (C3,1) [C1,C2,C2,C3] gets/cas Redis 一. 默认支持连接池 支持事务 发布和订阅 二.Redis基本操作 三.自定义 Redis列表类型 默认全部取 根据索引取值 本节预告 一.线程池 二.redis,发布订阅 三

Python之路【第十七篇】:Django【进阶篇 】

Python之路[第十七篇]:Django[进阶篇 ] Model 到目前为止,当我们的程序涉及到数据库相关操作时,我们一般都会这么搞: 创建数据库,设计表结构和字段 使用 MySQLdb 来连接数据库,并编写数据访问层代码 业务逻辑层去调用数据访问层执行数据库操作 import MySQLdb def GetList(sql): db = MySQLdb.connect(user='root', db='wupeiqidb', passwd='1234', host='localhost')

Python之路【第九篇】:Python操作 RabbitMQ、Redis、Memcache、SQLAlchemy

Python之路[第九篇]:Python操作 RabbitMQ.Redis.Memcache.SQLAlchemy Memcached Memcached 是一个高性能的分布式内存对象缓存系统,用于动态Web应用以减轻数据库负载.它通过在内存中缓存数据和对象来减少读取数据库的次数,从而提高动态.数据库驱动网站的速度.Memcached基于一个存储键/值对的hashmap.其守护进程(daemon )是用C写的,但是客户端可以用任何语言来编写,并通过memcached协议与守护进程通信. Memc

七日Python之路--第十二天(Django Web 开发指南)

<Django Web 开发指南>.貌似使用Django1.0版本,基本内容差不多,细读无妨.地址:http://www.jb51.net/books/76079.html (一)第一部分 入门 (1)内置数字工厂函数 int(12.34)会创建一个新的值为12的整数对象,而float(12)则会返回12.0. (2)其他序列操作符 连接(+),复制(*),以及检查是否是成员(in, not in) '**'.join('**')   或  '***%s***%d' % (str, int)

七日Python之路--第九天

众所周知,代码这东西不是看出来的.程序这东西只哟一个标准. 下面找点开源的东西看看,学习一下大婶们的犀利编码...... 推荐一下: 虽然有点老了:http://www.iteye.com/topic/405150,还有就是GitHub上面搜索一下Django就能出来很多,当然还有OSChina.只是有个问题,就是Django版本不同,具体的内容可能会有些不同,但大概还是相同的.领略即可,然后书写自己的代码. 首要的还是官方文档. 看着还是有些难度的.偶然发现一个不错的Blog:http://w

Python爬虫实战七之计算大学本学期绩点

大家好,本次为大家带来的项目是计算大学本学期绩点.首先说明的是,博主来自山东大学,有属于个人的学生成绩管理系统,需要学号密码才可以登录,不过可能广大读者没有这个学号密码,不能实际进行操作,所以最主要的还是获取它的原理.最主要的是了解cookie的相关操作. 本篇目标 1.模拟登录学生成绩管理系统 2.抓取本学期成绩界面 3.计算打印本学期成绩 1.URL的获取 恩,博主来自山东大学~ 先贴一个URL,让大家知道我们学校学生信息系统的网站构架,主页是 http://jwxt.sdu.edu.cn: