V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
unforgiven
V2EX  ›  算法

递归属于算法范畴吗

  •  
  •   unforgiven · 2019-09-30 13:17:01 +08:00 · 5871 次点击
    这是一个创建于 1641 天前的主题,其中的信息可能已经有所发展或是发生改变。

    如果说递归属于算法范畴,那么二叉树的遍历等如果使用递归的方式来解决仿佛都可以算在递归算法里面,这样一来貌似迭代也算是算法,因为递归可以实现的迭代都可以

    38 条回复    2019-10-01 00:06:23 +08:00
    cabing
        1
    cabing  
       2019-09-30 13:32:53 +08:00
    为啥不随呢?递归是算法的一种解法。

    通常递归的效率的很低 ,有些场景下要求使用循环展开递归。
    est
        2
    est  
       2019-09-30 13:34:48 +08:00
    怎么不能算。算啊。
    Melodyer
        3
    Melodyer  
       2019-09-30 13:36:29 +08:00
    解决问题的办法
    smdbh
        4
    smdbh  
       2019-09-30 13:48:50 +08:00
    不算吧,这个算是语言的特性。
    for 和 while 的实现,能算两种算法?
    misaka19000
        5
    misaka19000  
       2019-09-30 13:55:20 +08:00
    我觉得不算
    unforgiven
        6
    unforgiven  
    OP
       2019-09-30 14:11:26 +08:00
    @cabing 你也说了递归是具体算法的一种解法,那么迭代是不是也算算法
    unforgiven
        7
    unforgiven  
    OP
       2019-09-30 14:12:52 +08:00
    @misaka19000 我也是这么觉得的,如果说递推算是算法我还能理解,递归只是实现方式而已,不知道他们为什么都喜欢说递归算法
    unforgiven
        8
    unforgiven  
    OP
       2019-09-30 14:13:22 +08:00
    @est 如果算的话,迭代算不算?
    lvybupt
        9
    lvybupt  
       2019-09-30 15:33:39 +08:00
    当然算。 不管是现在的计算机科学,还是数学,系统科学的定义,递归都是经典的算法之一。

    迭代也算算法。 经典的辗转相除法就是一个典型的迭代算法。
    lance6716
        10
    lance6716  
       2019-09-30 15:52:55 +08:00 via Android
    前几天刚看了个使用 y 组合子在非递归语言中实现递归
    unforgiven
        11
    unforgiven  
    OP
       2019-09-30 15:58:50 +08:00
    @lvybupt 你的话是不是可以描述为辗转相除法是一个是用迭代的算法,另外辗转相除法是不是还可以使用递归算法,那么辗转相除法到底是迭代算法还是递归算法?
    unforgiven
        12
    unforgiven  
    OP
       2019-09-30 16:00:00 +08:00
    @lvybupt 你的话是不是可以描述为辗转相除法是一个是用迭代的算法,另外辗转相除法是不是还可以使用递归来实现,那么辗转相除法到底是迭代算法还是递归算法?
    Raymon111111
        13
    Raymon111111  
       2019-09-30 16:04:45 +08:00
    算啊

    递归是一种算法思想
    wqzjk393
        14
    wqzjk393  
       2019-09-30 16:10:42 +08:00
    本身不算是一个算法吧,只能说是一种实现方式或者说是技巧。
    wqzjk393
        15
    wqzjk393  
       2019-09-30 16:14:51 +08:00
    和其他算法合起来可以叫 xx 的递归实现算法,但是单独拿出来说,感觉就更像是一种内置功能
    passerbytiny
        16
    passerbytiny  
       2019-09-30 16:27:01 +08:00
    一、递归放在实现方式的语境中是实现方式,放到算法的语境中是算法。
    二、递归是迭代,迭代包含递归。
    三、算法分类,以及绝大部分事物的分类,都不可能是一个“A、B、C、……”的列表就能分好的。
    四、能不能算出结果是算法的必要条件,但算法首先要考虑的是时间、空间两个复杂度。
    lvybupt
        17
    lvybupt  
       2019-09-30 16:28:45 +08:00
    @unforgiven 辗转相除法就是一个具体的算法,你用递归实现相同的求同余功能那不叫辗转相除法了。
    其实你自己陷入了一个逻辑的怪圈。
    我举个例子类比,白羽鸡是鸟,乌鸡是鸟,那么鸡是不是鸟呢?
    你认为一个具体的计算过程叫算法,某一类具有共性的计算过程的统称就不叫算法了。
    unforgiven
        18
    unforgiven  
    OP
       2019-09-30 16:37:10 +08:00
    @lvybupt 用递归实现相同的求同余功能为什么不叫辗转相除法了,难不成我用迭代实现的前序遍历也不是前序遍历了?我的想法是说 xx 算法的递归实现更严谨一些,不至于上来就是一个递归算法了事
    unforgiven
        19
    unforgiven  
    OP
       2019-09-30 16:38:17 +08:00
    @wqzjk393 但是 n 多人把叫不出名字的递归实现的算法统统叫做递归算法,类似于汉诺塔问题
    sunjourney
        20
    sunjourney  
       2019-09-30 16:39:29 +08:00
    if else 也是算法啊
    unforgiven
        21
    unforgiven  
    OP
       2019-09-30 16:41:50 +08:00
    @passerbytiny 你说的没错,递归就是迭代的一种特殊实现,但是把叫不出名字的递归实现的算法统统叫做递归算法这样是不是有点过分了
    unforgiven
        22
    unforgiven  
    OP
       2019-09-30 16:43:04 +08:00
    @lance6716 lisp?
    passerbytiny
        23
    passerbytiny  
       2019-09-30 16:49:55 +08:00
    @unforgiven #18 递归跟迭代是包含关系,不是实现—接口 /定义关系,别搞混了。
    ayase252
        24
    ayase252  
       2019-09-30 16:51:39 +08:00
    递归是在分治法思想指导下的一种实现方法。
    lvybupt
        25
    lvybupt  
       2019-09-30 16:57:13 +08:00
    @unforgiven 两种说法都对。或者说,只是一个习惯性的称呼而已,只要交流的人不产出歧义就行。用大类的算法名来形容具体的算法确实容易引起歧义,但是并不能算错。

    我在给你举个例子,更典型更直观。
    穷举法就是最朴素最基本的算法。如果你放到实现搜索这个功能里面,顺序查找法就是典型的穷举算法。但是如果你直接说穷举法,就可能是倒着找,或者按照其他的某一规则穷举,还能否被称为顺序查找法就有待商榷了。但是你叫它某个查找算法的穷举实现或者用穷举算法查找其实本质上没有任何区别。

    另外,我提醒一下,纠结于它叫一种实现方式还是叫算法,其实是没有意义的。算法本来就是可以相关关联嵌套甚至是彼此实现构成的。
    比如我们在设计一个加密算法的时候,第一步可能需要系统生成随机数。加密算法叫做算法。至于我是叫这个随机数生成过程,我可以调用任意的满足要求的其他算法,是叫它伪随机函数的实现还是叫它伪随机生成算法,其实是没有意义的。
    Nasei
        26
    Nasei  
       2019-09-30 17:02:48 +08:00
    递归是算法的结构,一般遵循分治法的思想,而且你别看不上迭代啊,暴力求解也是算法的一种
    lvybupt
        27
    lvybupt  
       2019-09-30 17:10:39 +08:00
    @unforgiven 我看了一下楼里的各种回复。
    其实命名一种具体的算法里面,名字中应该包含的是解决目标中最关键点的地方才是最合适的。
    解决某个 xx 问题的某某算法,用递归实现了,直接叫递归算法确实不妥。
    但是计算斐波纳契数列的那基本算法,就叫递归算法。
    unforgiven
        28
    unforgiven  
    OP
       2019-09-30 17:12:59 +08:00
    @passerbytiny 本质上都是 goto 啊
    unforgiven
        29
    unforgiven  
    OP
       2019-09-30 17:15:18 +08:00
    @lvybupt 我觉得叫递推更合适一些,毕竟那个基本算法还可以用迭代来写
    unforgiven
        30
    unforgiven  
    OP
       2019-09-30 17:18:08 +08:00
    @unforgiven 叫做回溯也行,但是叫递归真的有歧义
    Fangfang2019
        31
    Fangfang2019  
       2019-09-30 17:31:19 +08:00 via Android
    递归是一种表达方式,不叫算法
    leavic
        32
    leavic  
       2019-09-30 17:35:27 +08:00
    算法应该是可以以固定的步骤解决问题,递归,要几步?我觉得按这个来说不算算法。
    kljsandjb
        33
    kljsandjb  
       2019-09-30 17:40:07 +08:00 via iPhone
    肯定算啊
    ayase252
        34
    ayase252  
       2019-09-30 17:58:10 +08:00
    @leavic 递归也有递归中止条件,有限步肯定能算出来
    bumz
        35
    bumz  
       2019-09-30 19:19:03 +08:00 via iPhone
    递归递推迭代都是算法设计思想
    也可以用来对算法进行分类

    树的遍历是按功能分类

    但他们都不是特指某个具体的算法

    Dijkstra, Tarjan 这些才是具体的算法
    keith1126
        36
    keith1126  
       2019-09-30 23:29:20 +08:00   ❤️ 1
    “对于程序员,递归是如同呼吸一般自然的本能。”

    就好比呼吸一样,虽然确实有一定的运作方式,也涉及到了人体系统的协调工作,但这算一种体育运动吗?
    unforgiven
        37
    unforgiven  
    OP
       2019-10-01 00:05:08 +08:00
    @bumz 我认为算法是对问题的解决方法的描述,递归这种貌似任何算法都可以实现出递归版本
    unforgiven
        38
    unforgiven  
    OP
       2019-10-01 00:06:23 +08:00
    @keith1126 而且算法导论里很少出现递归算法这个词,大多数出现的是递归式
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2520 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 16:00 · PVG 00:00 · LAX 09:00 · JFK 12:00
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.