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

初学编程对递归思想很难理解,求前辈指导一下

  •  
  •   w2bgopher · 2020-01-29 16:46:58 +08:00 · 11169 次点击
    这是一个创建于 1520 天前的主题,其中的信息可能已经有所发展或是发生改变。

    刷题的时候经常遇到需要递归的思想,但是我看答案的递归无法想象出它的结果是什么形成的,感觉十分的抽象,尤其是对于一些树,图的遍历已经其他需要递归完成的操作。

    84 条回复    2020-02-12 04:28:03 +08:00
    las917vki
        1
    las917vki  
       2020-01-29 16:56:01 +08:00   ❤️ 1
    套娃
    5G
        2
    5G  
       2020-01-29 16:59:29 +08:00
    确实就是套娃,不知道该怎么说
    jeffh
        3
    jeffh  
       2020-01-29 17:00:20 +08:00
    书里的递归树你应该能看得懂吧。另外个人总结的一些方法,可以想象成平行宇宙,递归进去的每个方法都是相互独立的。有兴趣的可以看下我写的这篇文章。https://juejin.im/post/5dc55e0651882559181a1274
    augustheart
        4
    augustheart  
       2020-01-29 17:00:50 +08:00
    首先简单来说就是在函数中调用一次函数自身。如果你配合堆栈的概念会更容易理解。在堆栈上看,递归是需要开辟新的栈空间的(先不考虑尾递归优化这个特例)),所有的上下文都是全新的,不准确的说,你把递归调用的函数可以看成一个全新的函数,这样你就可以抛开递归这个概念来思考调用过程中到底发生了什么了。
    纯自己的理解。
    augustheart
        5
    augustheart  
       2020-01-29 17:03:32 +08:00   ❤️ 1
    当然,考虑到你自称初学者,我就啰嗦一句,理解递归首先要求你对函数调用有足够的理解,你对函数调用有清楚的理解,递归就不难理解
    xxx749
        6
    xxx749  
       2020-01-29 17:03:39 +08:00 via Android
    teslabcd
        7
    teslabcd  
       2020-01-29 17:04:40 +08:00 via Android
    @xxx749 哈哈哈哈哈哈哈哈哈哈
    ipwx
        8
    ipwx  
       2020-01-29 17:07:56 +08:00   ❤️ 2
    如果是没有副作用的函数,可以用数学的递推公式来理解。其实这也是理解动态规划最好的方式,什么看代码反而理解不了动态规划。
    ipwx
        9
    ipwx  
       2020-01-29 17:08:36 +08:00
    比如斐波那契递推公式:

    f(n) = f(n-1) + f(n-2)
    f(2) = f(1) = 1
    chitanda
        10
    chitanda  
       2020-01-29 17:14:40 +08:00 via iPhone
    以前看一本书,书名忘记了,有个说法,leap of faith。其实我刚开始学递归也是很难理解,我的办法就是干,看一遍不懂看两遍,没事就找出来看看想想
    Inside
        11
    Inside  
       2020-01-29 17:15:39 +08:00   ❤️ 5
    翻一下高中课本,看看数学归纳法,递归的数学基础就是这个,代码实现是证明的形式。
    eason1874
        12
    eason1874  
       2020-01-29 17:20:40 +08:00   ❤️ 1
    循环重复做一件事,直到符合退出条件。

    如果这个循环是通过函数调用自身实现的,就叫递归。
    Building
        13
    Building  
       2020-01-29 17:27:20 +08:00 via iPhone   ❤️ 1
    不要想着那些循环概念,其实归递也是调用函数,凡是遇到归递,你就想着调用函数就行了,然后看参数,看流程。
    qwerthhusn
        14
    qwerthhusn  
       2020-01-29 17:40:25 +08:00
    斐波拉契
    汉诺塔
    netlous
        15
    netlous  
       2020-01-29 17:44:57 +08:00   ❤️ 33
    这个链接能帮助你了解递归:
    https://www.v2ex.com/t/640834
    dangyuluo
        16
    dangyuluo  
       2020-01-29 17:56:06 +08:00
    你需要一个热心的大哥哥,手把手教你用 C 写一个递归函数,然后用 gdb 调试,看一下函数是怎么进入自己的,栈是怎么一步步被吃干净的
    xiri
        17
    xiri  
       2020-01-29 17:59:49 +08:00 via Android
    自己把递归的过程画出来
    arjen
        18
    arjen  
       2020-01-29 18:02:00 +08:00
    @netlous 好活
    ericgui
        19
    ericgui  
       2020-01-29 18:06:59 +08:00   ❤️ 1
    写递归,就是套娃
    但为了防止无线循环,你记住,任何递归,第一步必然是写退出条件。
    t6attack
        20
    t6attack  
       2020-01-29 18:14:40 +08:00
    写一个 遍历文件夹及子文件夹 就理解了。
    monstervivi
        21
    monstervivi  
       2020-01-29 18:25:13 +08:00
    看一下盗梦空间然后总结一下就知道了。
    vance123
        22
    vance123  
       2020-01-29 18:28:22 +08:00 via Android
    Justin13
        23
    Justin13  
       2020-01-29 18:31:18 +08:00 via Android
    把递归看做循环,退出条件类比迭代条件
    wssy
        24
    wssy  
       2020-01-29 18:39:22 +08:00 via Android
    个人认为递归是分治思想的体现。
    系统性学习下算法理解会深入些,我以前刚接触编程时也是一脸茫然,多解决些题目,看些书,就慢慢理解一点了
    hakono
        25
    hakono  
       2020-01-29 18:49:48 +08:00 via Android
    或者我觉得可以考虑把递归的学习适当延后
    递归虽然写好了很优雅,但是一切的递归都是能等效翻译为循环的。也就是说,实在吃力可以先用循环顶着呗。等你编程经验上来了自然在应用中会逐渐。产生递归的思想

    (顺便,在团队中不太想看到别人的代码里出现太多递归
    1a0ma0
        26
    1a0ma0  
       2020-01-29 19:18:55 +08:00
    写点汇编试试?其实就是寄存器保存信息,然后跳转位置。可以看看《计算机组成要素》这本书,跟着这本书把上项目都都实现了。
    kokodayo
        27
    kokodayo  
       2020-01-29 19:24:59 +08:00
    从前有座山,山里有座庙……
    Cbdy
        28
    Cbdy  
       2020-01-29 19:36:47 +08:00 via Android
    可以用栈来理解
    lscho
        29
    lscho  
       2020-01-29 19:39:16 +08:00
    递归就是,我提醒自己明天提醒自己,直到某天结束。。。这就是递归,“提醒”就是函数,“明天提醒”就是在函数执行中再次调用当前函数,“某天结束”就是退出条件。
    wensonsmith
        30
    wensonsmith  
       2020-01-29 19:42:47 +08:00   ❤️ 2
    每次我都会想这个栗子:

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

    别忘了你是程序员,这个可难不倒你,递归就开始排上用场了。于是你就问前面一排的人他是第几排,你想只要在他的数字上加一,就知道自己在哪一排了。但是,前面的人也看不清啊,所以他也问他前面的人。就这样一排一排往前问,直到问到第一排的人,说我在第一排,然后再这样一排一排再把数字传回来。直到你前面的人告诉你他在哪一排,于是你就知道答案了。

    来自: https://www.showdoc.cc/476806889376927?page_id=2791994496480277
    janxin
        31
    janxin  
       2020-01-29 19:43:04 +08:00
    其实就是数学递归的表现
    laravel
        32
    laravel  
       2020-01-29 19:43:23 +08:00
    结合栈来理解啊
    ayase252
        33
    ayase252  
       2020-01-29 19:44:44 +08:00 via iPhone
    把一个大问题分解成若干个相同的小问题。
    orzorzorzorz
        34
    orzorzorzorz  
       2020-01-29 19:52:08 +08:00
    假设只有一层的调用自身,你就想着到递归的点,程序会停下来,先重新执行自身,然后等执行完了,返回当前的值,然后继续上个层次的程序就得了。多层的递归就是到条件满足了,然后一层层跳回到第一层。
    1runningbird
        35
    1runningbird  
       2020-01-29 20:00:43 +08:00 via iPhone
    从前有座山山里有个庙,庙里有个老和尚给小和尚讲故事,讲的故事是:从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲的故事是....
    Shiyq
        36
    Shiyq  
       2020-01-29 20:04:58 +08:00
    就是我用我自己啊
    sadhen
        37
    sadhen  
       2020-01-29 20:11:28 +08:00
    前段时间给我的侄女买了一个木制的汉诺塔玩具,递归应该从娃娃开始学起
    aguesuka
        38
    aguesuka  
       2020-01-29 20:19:35 +08:00 via Android
    《实分析》归纳法,有明确定义
    symeonchen
        39
    symeonchen  
       2020-01-29 20:58:50 +08:00
    想象觉得困难可以通过画图来帮助理解,或者写公式也可以,都有帮助。
    另外,没看错的话,头像是「黒崎レイナ」吧,v 站对头像的选择其实有一些简单的约束,可阅读 https://www.v2ex.com/t/62637
    pangleon
        40
    pangleon  
       2020-01-29 21:19:35 +08:00
    去做 LEETCODE 反转链表的递归做法
    ryanpenber
        41
    ryanpenber  
       2020-01-29 21:35:04 +08:00
    你去事业单位办事,你对业务员说,你要取出你保存的合同内容。业务员说稍等,我要请示值班经理;值班经理听了以后也不知道怎么办,说我去请示单位领导;单位领导觉得没处理过这个案例,请示区域经理;区域经理说:这点小事都办不好?合同是 XXXXX。单位领导拿到以后,把合同拿给值班经理,值班经理拿到了合同给了业务员;业务员把合同交给了你。

    程序返回的结果由下一层程序提供,这是我理解的递归
    52coder
        42
    52coder  
       2020-01-29 21:55:22 +08:00
    递归你可以理解为有限次函数调用,调用到最后一次后,再层层向上返回。
    jdz
        43
    jdz  
       2020-01-29 22:09:46 +08:00 via Android
    可以看下《计算机系统概括》,其中有一章专门讲递归
    versee
        44
    versee  
       2020-01-29 22:13:49 +08:00 via Android   ❤️ 3
    1.不要人肉追踪函数的调用,你深入几层以后根本拔不出来
    2.写好递归停止的条件以后,把每次的函数调用当成一个立即得到答案的黑盒
    ebony0319
        45
    ebony0319  
       2020-01-29 22:16:00 +08:00 via Android
    就是数学里面的抽象函数,类似于:f(x)=f(x-1)+1,这种一般会给一个条件:已知 f(1)=1
    omph
        46
    omph  
       2020-01-29 22:16:21 +08:00
    通过树结构来理解
    AX5N
        47
    AX5N  
       2020-01-29 22:41:50 +08:00   ❤️ 1
    感觉楼上基本都是在讲废话,楼主要听得懂你们说的那些还问么。
    fluorinedog
        48
    fluorinedog  
       2020-01-29 23:40:22 +08:00 via iPad   ❤️ 3
    楼主研究一下数学归纳法吧,和递归的思想是一模一样的。
    首先,对于 trivial 的情况,直接算得解,如同数学归纳法的初始条件。
    然后,假设我们已经有一个函数可以拿到 k-1 的情况,要计算 k,可以直接用 k-1 的结果,如同数学归纳法的迭代部分。
    这两者共同的核心是,我们得相信 k-1 的情况已经 magically 解决了,不要在这个地方引入思想负担。重点得关注 k-1 到 k 的变换过程。
    jakezh
        49
    jakezh  
       2020-01-29 23:51:40 +08:00
    adang313
        50
    adang313  
       2020-01-30 00:22:59 +08:00 via Android
    我也在学习中
    SlipStupig
        51
    SlipStupig  
       2020-01-30 00:54:36 +08:00
    自己给自己打电话
    levelworm
        52
    levelworm  
       2020-01-30 01:07:52 +08:00
    我也不太擅长递归。我觉得基本思想很好理解,就是把任务分解成相同性质的小任务。但是我觉得有两个难点,一个是理解每次递归之后必然会返回到上一层,第二个是如何分解。我觉得这个和智商有关,我这种智商不够的就只能先硬来,做的多了就好些。
    DamienS
        53
    DamienS  
       2020-01-30 01:10:25 +08:00
    你这样想。

    1. 我(当前的 function )只管当前要做的事情。
    2. 其他的逻辑由其他递归的 function 来做。我(当前的 function )不知道他们怎么做出来的,但是我就 assume 他们运行完拿到了正确的结果。


    比如 recursively 打印二叉树中序 node。


    sudo code 是

    recurPrint:
    if(currentNode==null){
    return;
    }

    recurPrint(Left Node)

    print(current Node)

    recurPrint(Right Node).


    这个就是我 assume recurPrint(Left Node) 和 recurPrint(Right Node) 都运行正确。我就把当前的 node 打出来了 print(current Node)。


    做完这个逻辑后需要确认 recurPrint(Left Node) 和 recurPrint(Right Node) 真的能运行成功。那就想下有什么特殊的需要处理的 case。就是当前 node 是 null 时,这时不打印直接返回,整个逻辑就 ok 了
    alphatoad
        54
    alphatoad  
       2020-01-30 04:03:30 +08:00 via iPhone   ❤️ 5
    要理解递归,你必须理解递归
    Shook
        55
    Shook  
       2020-01-30 04:13:51 +08:00
    可能应该多写写树的题目,比如如何寻找节点。
    happyz90
        56
    happyz90  
       2020-01-30 06:41:03 +08:00 via Android
    感觉汉诺塔来演示递归还是挺形象的
    52coder
        57
    52coder  
       2020-01-30 08:31:26 +08:00
    @alphatoad 卧槽,一大早看到你这个解释有点禅意了,比我的评论精辟了。
    ioriwong
        58
    ioriwong  
       2020-01-30 08:47:40 +08:00 via iPhone
    大家忽略了“初中生”,数学归纳法,递推数列 都没学
    SharkU
        59
    SharkU  
       2020-01-30 09:56:32 +08:00
    只要问题可以进行向下分解,并最终可以直接进行求解。
    [递归]( https://segmentfault.com/a/1190000007420201)
    zhw2590582
        60
    zhw2590582  
       2020-01-30 11:19:08 +08:00
    刚开始会不容易理解,等接触多了,练习多了就慢慢熟练了,我以前和你一起看见递归就头疼
    yjxjn
        61
    yjxjn  
       2020-01-30 11:22:54 +08:00
    我给你讲个故事:
    从前有座山,山上有座庙,庙里有个老和尚和小和尚,老和尚对小和尚说:从前有座山,山上有座庙,庙里有个老和尚和小和尚,老和尚对小和尚说:从前有座山,山上有座庙,庙里有个老和尚和小和尚,老和尚对小和尚说:从前有座山,山上有座庙,庙里有个老和尚和小和尚,老和尚对小和尚说:从前有座山,山上有座庙,庙里有个老和尚和小和尚,老和尚对小和尚说:从前有座山,山上有座庙,庙里有个老和尚和小和尚,老和尚对小和尚说:从前有座山,山上有座庙,庙里有个老和尚和小和尚,老和尚对小和尚说:从前有座山,山上有座庙,庙里有个老和尚和小和尚,老和尚对小和尚说:

    理解了吗???哈哈
    chengxiao
        62
    chengxiao  
       2020-01-30 11:27:14 +08:00
    照着书上的写,多写几次级明白了
    写着写着就明白了
    by73
        63
    by73  
       2020-01-30 11:30:21 +08:00
    学下 functional programming 就好,用数学的方式去理解它。当然还有其他方式是去 leetcode 之类的地方,用递归实现下链表、树之类的操作算法。
    bullfrog
        64
    bullfrog  
       2020-01-30 12:06:02 +08:00
    1.在一个副本里进入到另一个副本,退出副本的时候还是之前哪个副本
    2.盗梦空间
    herozzm
        65
    herozzm  
       2020-01-30 13:11:28 +08:00
    A 是确诊患者,然后 Ta 做高铁回家,一个车厢的其他人是 B,然后 B 们又去其他地方接触其他人,利用递归可以最终得到所有接触过的人员
    bugmakerxs
        66
    bugmakerxs  
       2020-01-30 13:44:35 +08:00 via Android
    方法栈理解清楚了,递归就懂了,递归其实就是一次普通的方法调用而已
    netty
        67
    netty  
       2020-01-30 13:46:55 +08:00 via Android
    极客时间的《数据结构与算法讲得不错》:
    1.编写递归代码的关键是,只要遇到递归,我们就把它抽象成一个递推公式,不用想一层层的调用关系,不要试图用人脑去分解递归的每个步骤。
    2.写递归代码的关键就是找到如何将大问题分解为小问题的规律,并且基于此写出递推公式,然后再推敲终止条件,最后将递推公式和终止条件翻译成代码。

    文档:10_递归:如何用三行代码找到“最终推荐人”? 链接: http://note.youdao.com/noteshare?id=d026fcabe93136f02c95efc449c6624f
    netty
        68
    netty  
       2020-01-30 13:49:45 +08:00 via Android
    然后多实践,徒手写,从最简单的阶乘和斐波那契数列开始
    kaifeii
        69
    kaifeii  
       2020-01-30 16:35:56 +08:00
    所有递归都可以用栈替代,递归只是把一部分过程数据记录在函数栈里了。
    建议你先学会堆栈结构,然后了解一点编译原理,然后你就知道把可以把递归的每一层局部变量包括入参压到栈里。
    从几个市面上标准的简单递归代码开始做栈化练习,多做几次你就都懂了。
    为了防止 stackoverflow,实际应用上也要用栈代替递归,迟早要学的。
    rainbowchou
        70
    rainbowchou  
       2020-01-30 16:48:11 +08:00
    楼上说的很有道理啊 就是数据结构 栈 ,函数调用就是把数据压入栈 弹出栈操作,递归就是全压入,然后倒序弹出,先学学数据结构吧
    HhZzXx
        71
    HhZzXx  
       2020-01-30 16:51:41 +08:00
    首先,一个函数(比如 A 函数)是有提供了一定特性的,即对外提供某种服务,比如 `String toString(node)` 方法对外提供 ”获得以 node 为根节点的子树的字符串描述“ 这个服务。
    那么,我们在递归函数 A 里调用函数 A 时,无需考虑那么多,直接就是:”调用这个 A 函数,获得其提供的服务“,然后我们基于其提供的服务,构建我们这个函数对外提供的服务。
    例子:
    String toString(node) {
    if(node==null) {
    return "";
    }
    a = toString(node.left);
    b = toString(node.right);
    return a + node.head + b;
    }
    我们调用 toString(node.left) 和 toString(node.right)获取 left 子树和 right 子树的字符串描述,基于此,构建出我们对外提供的服务 ”a + head + b“。当然,递归是有终止条件的,所以得判断 node 为 null 时就返回空串
    marlondu
        72
    marlondu  
       2020-01-30 20:26:46 +08:00
    简单点,不要看他们扯那么复杂,递归,就是在函数里自己调自己。
    xutao881
        73
    xutao881  
       2020-01-30 20:49:47 +08:00
    let num = 0;

    f a(){
    if(num>10){

    }
    }
    xutao881
        74
    xutao881  
       2020-01-30 20:50:35 +08:00
    妈耶,没打完就回复了。。。意思就是条件不满足的时候调用自己,满足之后 return
    wnpllrzodiac
        75
    wnpllrzodiac  
       2020-01-30 20:55:34 +08:00 via Android
    汉诺塔,当初想了好几个小时
    Electronika
        76
    Electronika  
       2020-01-31 00:44:07 +08:00 via iPhone
    @netlous hhhhh
    ajaxfunction
        77
    ajaxfunction  
       2020-01-31 10:29:25 +08:00
    如果是会用,多写几次就可以了,
    如果想理解,必须明白堆栈的概念和函数生命周期和变量作用域,特别是堆栈
    timwu
        78
    timwu  
       2020-01-31 15:39:33 +08:00
    看我这篇博客文章: https://wuzhiwei.net/ds_app_stack/ 栈 递归 汉诺塔
    GAsss
        79
    GAsss  
       2020-01-31 15:45:42 +08:00 via Android
    可以看看 The Little Schemer
    Kaakira
        80
    Kaakira  
       2020-01-31 17:23:15 +08:00
    AndyZhuAZ
        82
    AndyZhuAZ  
       2020-02-01 09:43:25 +08:00
    画个图,或者联想一下数学里的高阶导数((f'(x)')')'
    RickyC
        83
    RickyC  
       2020-02-01 10:12:45 +08:00
    我觉得轻易不要使用递归.
    jxie0755
        84
    jxie0755  
       2020-02-12 04:28:03 +08:00
    很多人说了很多各种高端术语, 什么域啊, 堆栈啊, 什么生命周期啊, 都是些已经懂了什么叫递归再反过来看问题的人说出来的话, 对你一个不理解什么是递归的人没有什么帮助.

    我作为一个几年前的新手用最通俗的话告诉你. 去找一个最简单的递归函数, 比如斐波那契, 求第 10 个数, 一定要彻底了解它是怎么运行的. 自己用手画出来.

    然后你就懂了, 因为它在执行的时候, 还没结束, 还没返回结果, 就遇到了它自己, 于是又进入了这个函数一次, 不断进入直到不需要进入为止, 因为你最终遇上了最简单的情况, 直接得到了结果. 最后再把结果一步步推回去.

    最重要的一句话就是: 递归函数就是从头一路看到脚, 在从脚一路返回到头.
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1910 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 72ms · UTC 16:24 · PVG 00:24 · LAX 09:24 · JFK 12:24
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.