讨论/技术交流/求助|请问咋才能不用玄学写递归?/
求助|请问咋才能不用玄学写递归?

如何避免用玄学写递归?

我总是用玄学来写递归【能不能过全凭运气】,想请教大佬们都是怎么写递归的?

  • 每次理解大佬们的递归我都是一看就会,可是一层一层往下推的时候,运气不好前面返回到哪里、从哪里开始调用等等就搞混了,还得从新来过;
  • 然后好不容易理解了,等下次再写的时候,又成了写玄学了。。。
  • 比如说树的各种遍历递归和非递归我都能理解,可等到写其他扩展类题目【比如判断对称二叉树等题目】,我又只能靠玄学了。。。
请大佬们分享下经验。。。
【我只知道: 一直,一直,一直做题,然后可能就会了。。。】
————————————————————————————————————————————————————

衷心感谢大佬们的慷慨指点,我要继续在这条从入门到秃头的不归刷题路上走下去了【后面评论不回复了,哈哈,抱歉】

下面是小白【我】的一点经验【请大佬不要喷我,但可以帮后面看的扣友指正错误,哈哈】,仅供暂时还在“纱帐外”的扣友参考,比较啰嗦,时间紧直接跳过看评论就好:

感谢大佬们不吝赐教,看了各位大佬的指点,做了些题【顺便摸下了几根头发】,突然发现,其实我和递归之间只是隔了一层纱,挑开了就懂了。

  • 1.千万不要觉得递归很难【因为我这种小白都能懂。。。】,递归本身简单易懂,或许这也是递归那么吃资源却还没有被淘汰的一个主要原因吧;
  • 2.之所以有一些递归的题不容易理解,我个人觉得是因为在这些题里递归已经不单纯了。。。
    比如说,简单递归都是自顶向下走,但有一些却是自底向上;
    简单递归都是只传入一个参数,但有的却不止一个,比如双指针什么的;
    简单递归都是被主函数调用一次,但有的却是在循环里,比如图的各种操作等等;
    简单递归都是到了终止条件才返回,但有的却加了剪枝。。。
    等等等等。
    再变态点或许就把前面说到的都用上,还用不止一次【哈哈,瞎猜的】;
    搞得递归有点不好懂了。。。
    1. 千万不要刚接触递归就去考虑中间那些跳来跳去的递归过程【个人观点】,只要细心一点,从简单递归开始,多练习,自己多思考,我觉得总会像弄懂for循环一样弄懂递归的。。。
另外,我写递归的题的时候【当然是简单递归】,会考虑三个方面【下面评论里大佬们写的非常到位,我根据自己的情况吸收总结的自己的方法】:
(1)第一次传入的参数是什么,传几个参数合适【比如求n!,传一个,第一次传入n;树的题一般第一次传入root,有时候需要双指针遍历比较树就传两个】;
(2)终止条件是什么,需不需要剪枝,有几种终止情况等等【比如n!,终止条件是n=1的时候,那么if(n==1) return 1; 一般树和图需要考虑剪枝】;
(3)写这个递归函数是要干什么,怎么才能合理的分步去干【比如求n!,是要返回一个结果,那么就return n*recursion(n-1); 再比如树的遍历,是要按规定顺序输出树节点的值,若先序就先输出再往下递归,中序就先递归左子树,然后立马输出,再遍历右子树】
(4)我个人认为,千万不要刚接触递归就去考虑中间那些跳来跳去的递归过程。。。【只是个人观点】

再次衷心感谢大佬们的慷慨指点,我必须为每一根头发负责,时间紧迫,后面评论不回复了,抱歉抱歉

6
共 32 个回复

递归就是函数自己调用自己,不同的地方在于:传递的参数的规模不同。

  • 需要分清楚「原问题」和「子问题」,把「原问题」转换成为「子问题」需要做哪些工作;
  • 然后还要了解化解的子问题在什么情况下不可以再拆分(也就是可以直接得出答案),避免递归调用不能返回。

我学习递归是通过「归并排序」和「快速排序」入门的,然后知道了「链表」的问题可以递归求解,「树」的问题也可以递归求解,「深度优先遍历」、「分治算法」也可以递归实现、可以用「栈」的解决的问题有一些也可以通过「递归」求解(支持递归底层的数据结构就是栈)。

因此,递归不是一个可以和算法隔离开来的概念。所以我的建议是:在学习算法和做题练习的过程中,渐渐去理解如何应用递归方法,如何调试递归方法,如何想到这个问题可以递归求解

递归、深度优先遍历、分治算法、后进先出、栈,它们有着很紧密的联系。


学会「递归」不是拍脑袋、或者看他人的几个分享,我们就会写的。和学习算法一样,有一个「了解 -> 熟悉 -> 不断练习 -> 巩固 -> 再不断练习」的过程。

所以我的建议是:在学习和应用中学习递归

15

举个例子,求 1 加到 n

代码

先写最笨的代码

  1. 先写一个 add_1() ,这个函数表示 从 1 加到 1 的和
int add_1() {
    return 1;
}
  1. 再写一个 add_2() ,这个函数表示从 1 加到 2 的和
int add_2() {
    return 1 + 2;
}
  1. 再写一个 add_3() ,这个函数表示从 1 加到 3 的和
int add_3() {
    return 1 + 2 + 3;
}

这么写下去不是办法啊,想办法改改代码

  1. 观察一下,add_2() 其实是可以调用 add_1()
  2. add_3() 是可以调用 add_2()
int add_1() {
    return 1;
}

int add_2() {
    return add_1() + 2;
}

int add_3() {
    return add_2() + 3;
}

我们改造一下函数,将具体的数字作为参数传进去,为了避免步子迈得太大,限定对应的函数只能传入对应的数值

int add_1(int x) { // 传入 x = 1
    if (x == 1) return 1;
}

int add_2(int x) { // 传入 x = 2
    return add_1(x - 1) + x;
}

int add_3(int x) { // 传入 x = 3
    return add_2(x - 1) + x;
}

观察发现,除了 add_1() 之外,其他函数是一样的,因此可以将代码进一步精简

int add(int x) {
    if (x == 1) return 1;
    return add(x - 1) + x;
}

最后就变成了递归的样子

现在再思考一下 add() 函数所代表的功能应该怎么描述

  1. 求从 1 到 n 的和
  2. 既然如此,我们就可以写上 n ,并调用求 n - 1 的函数
  3. 幸运的是,我们可以不用写 n 次重复的代码,从这个角度上来说,跟 for 循环是一样的

函数的出口

  1. 如果没有出口,就像 for 循环没有退出条件一样,会无线循环下去
  2. 所以每个递归都会有个出口,这个例子中,就是 if (x == 1) return 1;

思考回路

  1. 可以先找简单的例子,写出来的代码,在脑中练习
  2. 从上往下想,即:我现在是 add(5) ,我要调用 add(4) ...
  3. 从下往上想,即:我现在知道 add(1) 是多少,能不能求 add(2)
  4. 多想相当于练习了,多练就会了
16

你是子问题没考虑清楚。。。写递归是不需要考虑跳来跳去的,把你写的递归函数当做是一个库函数来调用,实现某些功能的库函数,然后实现的过程中恰好使用了这个函数。从功能层面上理解递归

12

我也不清楚,自己看评论吧,大概总结了一下:
1.不要太过于关注递归过程,
2.分清楚原问题怎么拆分为子问题
3.注意终止条件
4.多练习,做题多思考

3

额,我说的不太清楚
递归也是有套路的

func recur(level int, param int) {
    //终止条件
    if(level > max_level) {
        return
    }
    //单层逻辑
    process()
    //层数+1 变量跟随层数变动
    recurn(level + 1, new param)
}

这么一个模板可以解决大部分递归了

2

感谢大佬指点,

玄学

--一个只属于小白的烦恼:
  • 就是我知道一个递归一定有终止条件,一定会调用自身,一定能分成可以解决的子问题,也可能会有判断条件来进行剪枝等等,
  • 但是遇到一道题的时候,直接就懵了,觉得终止条件有一堆,也不知道分成什么样的子问题更合适,调用自身也不知道从哪里调用合适,从哪里剪枝,该怎么剪枝才能不影响一层层的调用结果。。。
  • 越想越懵。。。
  • 最后只能硬着头皮组合一下思路,结果有时候还蒙对了。。。
  • 但多数情况下不是结果不对,就是超时间限制。。。
  • 于是就玄学了。。。
    大佬说的对,我是应该调试,但是像树的递归,只能靠人脑调试,不太方便在编译器里调试,至于力扣的官方调试器,小白表示还没用。。。
2

上面大家都说的很好了。

  1. 把最基本的情况写对。
  2. 相信你写的递归函数是正确的,找到问题和子问题之间的关系。这一步有点像数学归纳法了。主要是通过传递参数,和对递归调用返回的结果做一些操作这样。
  3. 如果最基本的情况是对的,递推关系是对的,那么结果就应该是对的。

不要太关心具体递归调用的细节,每次调用函数应该往哪走之类的……而是应该把整个函数当做一种函数抽象,一定要相信你写的东西是正确的。如果一个递归里面只调用了一次自己,你可能还能知道往哪走。有的时候一次递归调用会调用不止一次自己,这个时候几乎不可能靠人脑搞明白函数走到哪了,该返回到哪了。

还是一直做题,一直做题,讲和写还是不太一样的。可以尝试先找一点特别特别简单的题,把能用循环做的题都换成递归的方式写一遍。

2

感谢大佬指点

1

多练,一定要考虑清楚退出条件

1

我就是为了方便调试,所以在本地写好了二叉树的类,直接把力扣的样例作为字符串贴到本地作为输入就能构造好完整的树,然后进行运行/调试。这种工作都是一次写好,长期使用,绝对不亏

1