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

为什么要用递归而不用循环?

  •  
  •   huzhikuizainali · 2022-08-08 17:50:01 +08:00 · 1583 次点击
    这是一个创建于 598 天前的主题,其中的信息可能已经有所发展或是发生改变。
    看了一下递归算法的介绍。感觉都可以用循环来实现。而且递归因为出栈入栈还要占用大量内存空间。可以自我调用的次数也有限。所以大部分递归算法 解决的问题为为什么不用循环来解决呢?难道在相同运算次数的前提下,递归算法比循环运算速度快?

    另外有一种感觉。就是 C 语言也不想想象中那么“灵活”。比如当你在 C 语言使用递归算法。编译以后程序还是会“自动对内存进行出栈入栈”操作。你只要用了递归算法,内存就会这样被使用。你没得选。当然如果你编写的每一段代码如何使用内存都要自己掌控,那就成了汇编语言了。但是感觉递归算法的内存调用还是被 C 语言编译器“写死了”,不知道我这种看法对不对?
    AoEiuV020CN
        1
    AoEiuV020CN  
       2022-08-08 18:01:16 +08:00
    “过早优化是万恶之源”
    AoEiuV020CN
        2
    AoEiuV020CN  
       2022-08-08 18:05:28 +08:00
    @AoEiuV020CN #1 当业务逻辑是递归时就应该写成递归,而不是循环,
    如果在算法完成不再需要修改之后确认这里需要死扣那一点点性能,再考虑改成不影响算法的循环也不迟,
    yedanten
        3
    yedanten  
       2022-08-08 18:18:23 +08:00 via Android
    “累死”程序员和“累死”机器的区别。有些解法递归好理解好写而已。如果可以的话,尽可能用循环
    wxf666
        4
    wxf666  
       2022-08-08 18:55:37 +08:00
    你不用语言的栈来实现递归,那就用自己的栈来实现循环呗(除非可优化的尾递归)
    billlee
        5
    billlee  
       2022-08-08 19:54:10 +08:00 via Android
    很多算法用递归更容易理解,gcc 开 -O2 就有尾递归优化,不能尾递归的改成手动管理栈,复杂度和直接写递归也是一样的,只有常数因子的差别
    huzhikuizainali
        6
    huzhikuizainali  
    OP
       2022-08-08 22:37:56 +08:00
    @wxf666 我现在看到递归的例子都是“重复”做某件事情。但是递归代码必然会引起内存入栈。难道利用循环“重复”做某件事情也会有内存进栈?
    wxf666
        7
    wxf666  
       2022-08-08 23:01:21 +08:00
    @huzhikuizainali 单纯的循环不会进栈

    或许,你可以试着,用循环去解决一些,原本用递归干的活儿

    比如,写个走迷宫。
    再如,用递归下降去解析个 json

    可能写多几个,你就不爱用循环+自己维护的栈,去模拟语言实现好的递归了
    wxf666
        8
    wxf666  
       2022-08-08 23:04:39 +08:00
    @huzhikuizainali 走迷宫用深度优先遍历啊
    wxf666
        9
    wxf666  
       2022-08-08 23:27:55 +08:00
    @huzhikuizainali 我在想,会不会是你不明白,

    同样是“重复”,为何有的用递归,有的用循环?

    递归还有一系列入栈出栈操作,既占内存,又耗性能,这货存在意义是什么?!
    huzhikuizainali
        10
    huzhikuizainali  
    OP
       2022-08-09 08:26:29 +08:00
    @wxf666 对。就是不明白这一点。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1480 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 36ms · UTC 23:50 · PVG 07:50 · LAX 16:50 · JFK 19:50
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.