专栏首页一个爱吃西瓜的程序员每天学习一点儿算法--递归

每天学习一点儿算法--递归

递归是很多算法都使用的一种编程方法。听说递归是一种十分优雅的问题解决办法,可是对于初涉递归的我,还没有形成这种独特的体会。

学习使用递归的关键在于:如何将问题分为基线条件和递归条件。

基线条件和递归条件

由于递归函数调用自己,因此编写这样的函数时很容易出错,进而导致无限循环。

例如下面这个函数:

def countdown(i):   
    """倒计时"""
    print (i)
    countdown(i-1)

假设i的初始值为3,运行上述代码后:

3, 2, 1, 0, -1, -2, .........

它会一直运行下去,(可按Ctrl+C停止)

所以,编写递归函数必须要让函数能在某个时候停止递归。

让递归函数停止递归的条件就是基线条件。

递归条件指函数调用自己;基线条件指函数不再调用自己。

现在我们给函数countdown添加基线条件:

def count_down(i):    
    """倒计时"""
    print(i)    
    if i <= 1:  # 基线条件(指函数不再调用自己)
        return
    else:  # 递归条件(指函数调用自己)
        count_down(i-1)

count_down(3)

运行结果:

3
2
1

使用递归必须就要理解一个名为“调用栈”的编程概念。因为递归函数在运行的过程中是存储在栈中的。

栈是一种数据结构,只有两种基本操作:压入(进栈)和弹出(出栈)。且遵循后进先出的规则。

计算机在内部使用的栈被称为调用栈。下面用一个函数来看看计算机如何使用调用栈:

def greet(name):    
    """问候1"""
    # greet函数问候用户,再调用了另外两个函数
    print("hello " + name + " !")
    greet2(name)
    print("getting reading to say bye...")
    bye()

这个函数问候用户,再调用了另外两个函数,这两个函数的代码如下:

def greet2(name):    
    """问候2"""
    print("how are you, " + name + " ?")

def bye():    
    """拜拜"""
    print("ok, bye!")

注释:在python中,print也是一个函数,但我们先暂且不考虑它。

假设我们调用greet(“you”)。计算机先为其分配一块内存:

接下来,打印出 hello you ! 。再调用函数greet2(“you”)。同样,计算机也为这个函数调用分配一个内存块:

然后打印出 how are you, you ? 。然后从函数调用返回。此时,栈顶的内存块被弹出:

执行完函数greet2后,回到函数greet,并从离开的地方接着往下执行:首先打印 getting ready to say bye... 。再调用函数bye:

然后打印 ok bye ! 。并从这个函数返回。

现在又回到了函数greet。由于没有别的事要做,就从函数greet返回。这个被用于存储多个函数变量的栈,称之为调用栈。

递归调用栈的另一个应用就是计算阶乘。下面是一个计算阶乘的递归函数:

def fact(x):    
    """计算阶乘的函数"""
    if x == 1:        
        return 1
    else:        
        return x * fact(x-1)

我们来分析一下调用fact(3)时,调用栈是如何变化的:

说明:

  • 使用递归不能提高程序的性能,它只是让程序更容易理解。
  • 使用栈很方便,但会占据很多的内存

尾递归

最后介绍一个尾递归。尾递归是一种高级递归,它和普通递归函数的区别在于:尾递归在函数执行的最后一步调用自身,而其他递归函数在函数的最后一步不仅调用了自身,还掺杂着其他表达式。

举个例子: 计算阶乘:

def fact(x):    
    """计算阶乘的函数"""
    if x == 1:        
        return 1
    else:        
        return x * fact(x-1)

这不是尾递归函数。

def fact(x):
    """尾递归"""    
    if x == 1:        
        return 1
    else:        
        return fact(x-1)

这就是尾递归函数。

小结

  • 递归指调用自己的函数
  • 每个递归函数都有两个条件:基线条件和递归条件
  • 栈有两种操作:压入和弹出
  • 所有的函数调用都进入调用栈

每天学习一点点,每天进步一点点。

本文分享自微信公众号 - 小白客(youcoding),作者:爱吃西瓜的番茄酱

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-01-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 利用requests和正则表达式抓取猫眼电影top100

    刚学了正则表达式,赶紧用它来练练手,以防搞忘了。这次练习的目标比较简单,就是爬取猫眼电影top100,具体包括电影排名,片名,主演,上映时间,评分等信息。最后存...

    爱吃西瓜的番茄酱
  • Web前端基础【4】--HTTP标准

    HTTP协议(超文本传输协议),是用于从www服务器传输超文本到本地浏览器的传送协议。它可以使浏览器更加高效,减少网络传输。 一:HTTP请求过程 HTTP协议...

    爱吃西瓜的番茄酱
  • Python基础学习-函数

    一:定义函数: ① 函数是带名字的代码块,用于完成具体的工作。 ② 函数使用关键字def来定义,最后,定义以冒号结尾。 ③ 每个函数后面都应紧跟一个文档字符串,...

    爱吃西瓜的番茄酱
  • Python数据结构与算法笔记(3)

    递归是一种解决问题的方法,将问题分解为更小的子问题,直到得到一个足够小的问题可以被很简单地解决,通常递归设计函数调用自身。递归允许我们编写优雅的解决方案,解决可...

  • SQL 的递归表达式

    MySQL 在 8.0 的版本引入了公共表表达式(Common Table Expressions),简称 CTE。CTE 在一些方面可以简化我们的 SQL 语...

    白日梦想家
  • C++的四种强制转换

            C++中的四种转换,是一个老生常谈的话题。但是对于初学者来说,该如何选择哪种转换方式仍然会有点困惑。而且我总是觉得“纸上得来终觉浅”,于是便“绝...

    方亮
  • init,__construct区别以及PHP魔术方法大汇总

    init()是框架设置为初始化函数,当然框架内部还是用的___construct()内置函数;如果你是框架开发者,你当然也可以把初始化函数写成__init(),...

    苦咖啡
  • 不规则图形的碰撞检测

    public static class CheckHit { public static bool CheckCollision(FrameworkEl...

    用户1172164
  • JavaScript 数据结构与算法之美 - 递归

    现实例子:周末你带着女朋友去电影院看电影,女朋友问你,咱们现在坐在第几排啊 ?电影院里面太黑了,看不清,没法数,现在你怎么办 ?

    夜尽天明
  • 循环、递归与魔术(一)——递归与循环的数理逻辑

    今天我们开启一段新的旅程,聊聊循环(circulation)和递归(recursion)背后的数理逻辑以及艺术应用。

    magic2728

扫码关注云+社区

领取腾讯云代金券