资讯专栏INFORMATION COLUMN

关于递归的思考

lyning / 2364人阅读

摘要:之前有接触过递归,看到别人写的递归函数的代码,好生羡慕,怎么就能写这么好呢我怎么就想不到这样写呢如此等等。

之前有接触过递归,看到别人写的递归函数的代码,好生羡慕,怎么就能写这么好呢?我怎么就想不到这样写呢?如此等等。

就拿fibonacci函数来说吧,一个普通的函数可能这样写:

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

我看到这个函数的思考方式是这样的:

1. 当n=0时:返回0
2. 当n=1时:返回1
3. 当n=2时:
    1. 首先去调用n=1,返回1
    2. 再去调用n=0,返回0
    3. 把0和1相加返回1
4. 当n=3时:
    1. 调用n=2
        1. 调用n=1,返回1
        2. 调用n=0,返回0
        3. 相加返回1
    2. 调用n=1,返回1
    3. 把1和1相加返回2
5. 等等

想到这我头都要爆了,彻底被人家的函数折服了,看来我是写不成这么好的函数了。

但我转念一想,这个函数的本质是fibnacci序列,我何不回归fibonacci本身呢?fibonacci用数学公式表示应该是这样:

看到公式我恍然大悟,上面那个函数不就是根据这个公式直接翻译的嘛!原来我一直思考都是顺着函数的代码思考,这样肯定会觉得很难,
正确的思考方式应该是从算法出发然后再写代码。

经过了上面的惨痛教训看看我能不能写出正确的fibonacci序列函数,分段函数的公式应该是这样的:

那么直接写成代码就应该是这样的:

def fib_seq(n):
    seq = []
    if n == 0:
        seq.append(0)
    else:
        seq.extend(fib_seq(n-1))
        seq.append(fib(n))
    return seq

咦,这两个append好像可以合并:

def fib_seq(n):
    seq = []
    if n > 0:
        seq.extend(fib_seq(n-1))
    seq.append(fib(n))
    return seq

哇,原来如此!

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/38075.html

相关文章

  • Python | 递归

    摘要:那假如我们用递归来描述这种情况呢定义基本情况其它情形所以在上述求和中的定义又用到了自己本身的定义,这就构成了递归。 说起递归,我觉得其实大部分人应该是不陌生的,递归广泛存在于生活中。比如: showImg(https://segmentfault.com/img/remote/1460000007420204?w=294&h=450); The woman in this image ...

    qieangel2013 评论0 收藏0
  • 《java 8 实战》读书笔记 -第十三章 函数式思考

    摘要:当我们希望能界定这二者之间的区别时,我们将第一种称为纯粹的函数式编程,后者称为函数式编程。函数式编程我们的准则是,被称为函数式的函数或方法都只能修改本地变量。另一种观点支持引用透明的函数式编程,认为方法不应该有对外部可见的对象修改。 一、实现和维护系统 1.共享的可变数据 如果一个方法既不修改它内嵌类的状态,也不修改其他对象的状态,使用return返回所有的计算结果,那么我们称其为纯粹...

    Donne 评论0 收藏0
  • leetcode100 Same Tree 引发对遍历?算法思考

    摘要:判断两棵树是否是相同题目要求传入两棵树的根节点,判断这两棵树是否相同此题的核心就在于如何遍历树。定义树的一种自然方式是递归的方式。一棵树是一些节点的集合,这个集合可以是空集。这个遍历算法可以用于场景如,计算一个节点的高度。 判断两棵树是否是相同 题目要求:传入两棵树的根节点,判断这两棵树是否相同此题的核心就在于如何遍历树。一旦我们解决了这个问题,题目也就迎刃而解了。下面就来介绍一下 关...

    cyrils 评论0 收藏0
  • 记一次XX前端面试

    摘要:面试官说那我问你一个哲学的问题,为什么有数据结构这种东西哇,这是啥,巴拉巴拉扯了一通,大致就是物以类聚,人以群分,先人积累下来的经验,这些让我们更方便处理数据啥的。 前因,没有比摸鱼有趣的事了 距离自己被外派(俗称外包)出去,已经过了快五个月,工作的话,很闲。人啊,一定保持好的习惯,懒惰是会上瘾,日常摸鱼,怀疑人生,我是谁,我在哪,我要干什么。 中午吃饭的时候,收到了boss直聘的一条...

    Shisui 评论0 收藏0
  • 数据结构与算法之精讲「递归系列」

    摘要:终止条件递推公式递归的分类通过做大量的题,根据递归解决不同的问题,引申出来的几种解决和思考的方式。我们通过层与层之间的计算关系用递推公式表达出来做计算,经过层层的递归,最终得到结果值。 showImg(https://segmentfault.com/img/remote/1460000019222330); 前言 几个月之前就想写这样一篇文章分享给大家,由于自己有心而力不足,没有把真...

    zhichangterry 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<