Python递归_百股精的博客-程序员秘密

技术标签: Python系统学习  

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

递归的特点

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

  • 递归就是在过程或函数里调用自身。
  • 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。
  • 递归算法解题通常显得很简洁,但递归算法解题的运行效率较低,所以一般不提倡用递归算法设计程序。
  • 在递归调用的过程中系统为每一层的返回点、局部量等开辟了栈来存储,递归次数过多容易造成栈溢出等。

递归的要求

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

  • 每次调用在规模上都有所缩小(通常是减半)
  • 是相邻两次重复之间有紧密的联系,前一次要为后一次做准备(通常前一次的输出作为后一次的输入)
  • 在问题的规模极小时必须用直接给出解答而不再进行递归调用,因而每次递归调用都是有条件的(以规模位达到直接解答的大小为条件)无条件递归调用将会成为死循环而不能正常结束。
def recursion():
    return recursion()

recursion()    # RecursionError: maximum recursion depth exceeded

Python 默认递归最大深度是1000层,可以自己设置递归深度限制:

import sys
sys.setrecursionlimit(100000)   # 将递归限制设置为10万层

实例

求正整数阶乘

正整数阶乘指从1*2*3*4…一直乘到所要求的数。如:5的阶乘(5!)是 1*2*3*4*5=120,120就是5的阶乘(factorial)。

# 非递归版本
def recursion(n):
    result = n    # n
    for i in range(1, n):    # 1~n-1
        result *= i    # n * 1 * 2 * 3 … * (n-1)
    return result

number = int(input('请输入一个正整数:'))
result = recursion(number)    # 此result是全局变量,并非def里的局部变量result,两者完全不同。
print('%d 的阶乘是:%d' % (number, result))

'''
请输入一个正整数:5
5 的阶乘是:120
'''
# 递归版本
def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)    #调用函数自身

number = int(input('请输入一个正整数:'))
result = factorial(number)
print("%d 的阶乘是:%d" % (number, result))

斐波那契数列

1、1、2、3、5、8、13、21、34、55、89、144…

# 迭代版本
def fab(n):
    n1 = 1
    n2 = 1
    n3 = 1

    if n < 1:
        print('输入有误!')
        return -1

    while (n-2) > 0:
        n3 = n2 + n1
        n1 = n2
        n2 = n3
        n -= 1    #循环次数-1
    
    return n3

result = fab(6)
if result != -1:
    print('斐波那契数为:%d' % result)
def fab(n):
    if n < 1:
        print('输入有误!')
        return -1

    if n == 1 or n == 2:
        return 1
    else:
        return fab(n-1) + fab(n-2)

result = fab(6)
if result != -1:
    print('斐波那契数为:%d' % result)

 

汉诺塔

def hanoi(n, x, y, z):
    if n == 1:
        print(x, ' --> ', z)
    else:
        hanoi(n-1, x, z, y)    # 将前n-1个盘子从x移动到y上
        print(x, ' --> ', z)     # 将最底下的最后一个盘子从x移动到z上
        hanoi(n-1, y, x, z)     # 将y上的n-1个盘子移动到z上

n = int(input('请输入汉诺塔的层数:'))
hanoi(n, 'X', 'Y', 'Z')

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_43403380/article/details/83352812

智能推荐

Guideline 3.2 - Business_lvmenglong888的博客-程序员秘密

iOS 上架3.2.0 被拒,求大神指点

技术方案解决总结_niu0147的博客-程序员秘密

Android 程序员资源开源项目介绍:一、oschina上的资源汇总http://my.oschina.net/luyao/blog/382330二、其他 http://www.trinea.cn/三、github项目汇总地址:https://github.com/Trinea/android-open-project四、开源项目解析:http://cod

git push时报错:packet_write_wait: Connection to 13.229.188.59 port 22: Broken pipe_ 颜 的博客-程序员秘密

git push时出错信息packet_write_wait: Connection to 13.229.188.59 port 22: Broken pipefatal: sha1 file '&lt;stdout&gt;' write error: Broken pipefatal: the remote end hung up unexpectedlyfatal: the remot...

VxWorks开发环境-VxWorks6.8-VxWorks6.9-VxWorks7.0-各个CPU型号的BSP_vxworks支持的cpu_smartvxworks-V2的博客-程序员秘密

vxworks,vxworks下载,VxWorks开发环境,VxWorks6.8,VxWorks6.9,VxWorks7.0,各个CPU型号的,BSP;

接口-AuthenticationEntryPoint_疯狂马铃薯的博客-程序员秘密

AuthenticationEntryPoint简介AuthenticationEntryPoint是Spring Security Web一个概念模型接口,顾名思义,他所建模的概念是:“认证入口点”。它在用户请求处理过程中遇到认证异常时,被ExceptionTranslationFilter用于开启特定认证方案(authentication schema)的认证流程。该接口只定义了一个方法 :void commence(HttpServletRequest request, HttpServlet

PLSQL Developer导入Excel报错,ORA-01036-illegal variable name/number_chenmeng2192089的博客-程序员秘密

excel的表头(第一行)不能是中文,也不能没有表头,否则都会报这个错,解决方法是把表头字段名用英文描述。

随便推点

BZOJ.4825.[AHOI/HNOI2017]单旋(线段树)_weixin_30446613的博客-程序员秘密

BZOJLOJ洛谷这题不难啊,我怎么就那么傻,拿随便一个节点去模拟。。我们只需要能够维护,将最小值或最大值转到根。模拟一下发现,对于最小值,它的右子树深度不变(如果存在),其余节点深度全部\(+1\),且除右儿子外所有点的父子关系不会改变。最大值同理。因为右子树和右子树外的所有点的值域是连续的,所以按值域为下标维护线段树,区间加即可。至于怎么维护右子树的范围?不就是\((v...

Java维护常量方式的比较——接口、常量类与枚举_java 常量接口_得过且过的勇者y的博客-程序员秘密

而对于枚举,参数接收的是枚举中定义的静态对象(即传入的就是事先存在的、枚举中的对象),即常量值地址唯一(因为其构造函数是私有的,无法通过外部构造出对象),所以只要比较地址即可。而处于不同地址的两个对象是可以相同的,所以对于常量来说,用户传入的参数是自己写的(新创建的)常量,与常量类中定义的常量显然是不同的对象,所以要比较的是内容是否相同而非地址。每个枚举都是通过Class在内部实现的,且所有的枚举值都是publicstaticfinal的。常量能做的,枚举都能做,枚举能做的常量不一定能做。......

c++ 旋转矩阵(回型矩阵)_矩阵旋转c++_Dreamboat0707的博客-程序员秘密

c++旋转矩阵(回型矩阵)思路:1.从对角线切换开,如图例所示,从外圈向内圈循环,按着从左至右从上之下从右至左从下到上依次循环例如n=5,第一圈时从左到右 1,2,3,4从上之下 5,6,7,8从右至左 9,10,11,12从下到上 13,14,15,16第二圈:从左至右 17,18从上之下 19,20从右至左 21,22从下到上 23,24第三圈:可以...

Nginx服务器配置沃通免费SSL证书部署HTTPS网站_chicha8453的博客-程序员秘密

本文讲解服务器配置SSL证书部署HTTPS网站。环境是阿里云服务器ECS ,系统是CentOS6 64bit,Web服务器是Nginx。需要SSL模块的支持。签发SSL证书的CA机构是 沃通电子认证服务有限公司 WoSign CA Limited。部署HTTPS网站一般需要有服务器的控制...

matlab 水箱fuzzy,matlab中使用fuzzy工具箱_接近无线透明的灰的博客-程序员秘密

4步教你学会使用matlab模糊控制工具箱Matlab模糊控制工具箱为模糊控制器的设计提供了一种非常便捷的途径,通过它我们不需要进行复杂的模糊化、模糊推理及反模糊化运算,只需要设定相应参数,就可以很快得到我们所需要的控制器,而且修改也非常方便。下面将根据模糊控制器设计步骤,一步步利用Matlab工具箱设计模糊控制器。首先我们在Matlab的命令窗口(command window)中输入fuzzy,...

推荐文章

热门文章

相关标签