专栏首页KEN DO EVERTHING【从0到1学算法】递归

【从0到1学算法】递归

今天我们将学习一种优雅的问题解决方式--递归。 对于它,通常有3个阵营:恨它的、爱它的以及恨了几年后又爱上它。你属于哪一个?

1、递归

递归就是函数自己调用自己,但写递归很容易出错而导致死循环。

循环和递归是可以相互转换,下面从一个简单例子学习递归。

现在需要编写一个倒计时函数。

效果如下:

3
2
1

循环方式代码:

def countdown(i):
    # 从i开始, 到0结束(不包括0),每次循环-1
    for j in range(i, 0, -1):
        print(j)

如何用递归方式写呢?一开始你可能会这样写:

def countdown(i)
    print(i)
     # 变量-1,调用自己
     countdown(i-1)

运行上面的代码,你会发现:这个函数运行起来没完没了!

如何正确编写递归?

编写递归,必须得告诉它如何停止。正因如此,递归函数都有这两部分:基线条件递归条件

递归条件指什么情况下调用自己,而基线条件指什么情况下停止调用自己。

我们只需要倒计时到1,所以这里它的基线条件便是:i<=1,其他情况都需要调用自己。

def countdown(i)
    print(i)
    if i <= 1:#<-----------基线条件
        return
    else:#<----------- 递归条件条件
        countdown(i-1)

循环和递归的作用是相同的,但递归逻辑更清晰。递归也是有缺点的,有时候递归的性能不如循环,甚至很糟糕。

如果使用循环,程序性能可能更高;如果使用递归,程序可能更容易理解。如何选择,还得结合实际需求。在逻辑不特复杂的情况下,推荐使用循环。

2、栈

接下来介绍一个重要概念--栈。(递归中使用到了栈,往下看会有分析)

假设这里有一叠便利条,用于记录待办事项,那么就只能做两个操作:在最上面插入待办事项(压入)或在最上面移除并读取待办事项(弹出),再专业点说就是入栈和出栈。

更形象的例子:桶装薯片,当薯片做好之后,它们会依次被添加到桶里,每一片都是从最上面添加,而每次我们取的时候也是只能去最上面的那一片(当然你不能帮桶底捅穿),所以第一个放入桶的薯片只能最后一个从桶里取出。 这个桶装薯片就是栈,放薯片是入栈,取薯片是出栈

3、调用栈

调用栈是在计算机内使用的栈,接下来我们看下计算机如何使用调用栈。

下面有一段简单代码。

def greet(name):
    print ("hello," + name + "!")
    greet2(name)
    print ("getting ready to say bye...")
    bye()

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

def bye()
    print ("ok bye!")

greet函数调用了另外两个函数greet2和bye。(这里,我们假设print不是一个函数,为了更简单了解调用栈的使用)

调用greet("maggie"),计算机首先会为该函数调用分配一块内存

然后将变量name设置为maggie,存储到这块内存中

每当函数被调用,计算机都会像这样将函数调用涉及的变量存储到内存中。接下来,程序打印"hello,maggie!",再调用greet2("maggie")。同样,分配内存后存储。

打印“how are you, maggie?”,greet2调用完成。此时,栈顶内存块出栈。

现在,栈顶的内存块为函数greet,意味着返回到了函数greet,继续执行未执行操作。首先打印“getting ready to say bye...”,再调用函数bye。

在栈顶添加了函数bye的内存块。然后,打印“ok bye!”,出栈并返回到函数greet。

此时,函数greet没有其他操作了, 执行完毕出栈。这便是计算机使用调用栈的过程。

4、递归调用栈

递归函数同样也使用调用栈。

下面我们以阶乘的递归函数为例,来看看递归函数中调用栈的使用。

ps: 栈顶内存块指出当前执行位置

def fact(n):
    if n == 1:
        return 1
    else:
        return n * fact(n-1)

调用fact(3)时,调用栈如何变化?

注意,栈中每个内存块相互独立,每个fact都有自己的x变量。

So easy 吧!?

通过分析调用栈在递归中的变化,我们可以得出这样的结论:递归很耗内存,每个函数调用都要占用一定的内存,如果栈很高,就意味着需要占用很大的内存。

当发现使用递归占用很大内存时,你有两种选择:

  1. 放弃递归,使用循环
  2. 使用尾递归

尾递归

这里也稍微提一下尾递归,尾递归的实质是开源节流,下面将阶乘的普通递归改为尾递归。

def fact(n, result):
    if n == 1:
        return result
    else:
        return fact(n - 1, n * result)

可以看到,在调用自己时,只有函数自身的调用,而没有其他运算,这样它就可以不在栈顶添加一个新的栈帧(栈的内存单位),而是更新它。

编写思路:尾递归需要多一个参数result用于存储每次运算的结果,最后输出结果;而n则更像是用于记录循环次数的变量。

缺点:尾递归是通过编译器优化的方式来实现效率的提升,但是有些语言或者有些编译器可能就不支持(比如python)。

5、总结
  • 递归指自己调用自己。
  • 递归函数都有两个条件:基线条件和递归条件(写递归时,首先找这2个条件)。
  • 所有函数的调用都会进入调用栈。
  • 循环的性能可能更高,递归则更容易理解,结合实际选择。

本文分享自微信公众号 - KEN DO EVERTHING(KENDOEVERTHING),作者:a丶ken

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

原始发表时间:2020-02-20

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 「 互联网笔试题 」2018华为笔试编程题

    1.输入任意个字符串,将其中的小写字母变为大写,大写字母变为小写,其他字符不用处理; 输入描述: 任意字符串:abcd12#%XYZ 输出描述: 输出字符串:A...

    KEN DO EVERTHING
  • java小心机(3)| 浅析finalize()

    本例的终结条件是:所有的Book对象在被当作垃圾回收前都应该被签入(check in)。 在main()方法中可看到,一次误操作未对Book对象进行签入,导致有...

    KEN DO EVERTHING
  • java小心机(5)| 浅谈类成员初始化顺序

    类成员什么时候会被初始化呢?一般来说:"类的代码在初次使用时才被加载",加载过程包括了初始化。 比如说new A()调用构造函数时,类中全部成员都会被初始化。

    KEN DO EVERTHING
  • 探索c#之尾递归编译器优化

    蘑菇先生
  • Java的递归算法

    递归:无限调用自身这个函数,每次调用总会改动一个关键变量,直到这个关键变量达到边界的时候,不再调用。

    用户5224393
  • Linux 内存管理

    Linux内存清理:绝大多数情况下都不需要此操作,因为cache的内存在需要的时候是可以自动释放的~

    Alfred Zhao
  • 递归算法复杂度Ω分析-分享

    1. 深入认识递归 (1) 递归执行过程 例子:求N!。 这是一个简单的"累乘"问题,用递归算法也能解决。 n! ...

    ACM算法日常
  • 一道小学三年级的题目把我困住了

    由于这次考试太仓促,往届真题搞到了,答案没搞到、更别说挤时间自己去做一份正常答案了。这些反复考的题目,的确有点让人反胃,相反,有一道全新的题目,...

    Ed_Frey
  • PHP程序员:你过来,给我说说 $this,self,static 有什么区别?

    我们每天都在敲代码,对着各种各样的类与继承。面向对象的编程设计方式,裹挟着PHP程序员加入 OOP 大军。

    程序员小助手
  • 音乐号将成在线音乐标配,QQ音乐如何诠释强用户导向思维?

    6月初,我发现常用的QQ音乐改版了,体验了半个月,有些想法跟大家分享下。 我习惯于在线听歌,最常用的界面电台焕然一新,电台分类从纵向变为横向,为新增的主播电台和...

    罗超频道

扫码关注云+社区

领取腾讯云代金券