刷题的时候经常遇到需要递归的思想,但是我看答案的递归无法想象出它的结果是什么形成的,感觉十分的抽象,尤其是对于一些树,图的遍历已经其他需要递归完成的操作。
1
las917vki 2020-01-29 16:56:01 +08:00 1
套娃
|
2
5G 2020-01-29 16:59:29 +08:00
确实就是套娃,不知道该怎么说
|
3
jeffh 2020-01-29 17:00:20 +08:00
书里的递归树你应该能看得懂吧。另外个人总结的一些方法,可以想象成平行宇宙,递归进去的每个方法都是相互独立的。有兴趣的可以看下我写的这篇文章。https://juejin.im/post/5dc55e0651882559181a1274
|
4
augustheart 2020-01-29 17:00:50 +08:00
首先简单来说就是在函数中调用一次函数自身。如果你配合堆栈的概念会更容易理解。在堆栈上看,递归是需要开辟新的栈空间的(先不考虑尾递归优化这个特例)),所有的上下文都是全新的,不准确的说,你把递归调用的函数可以看成一个全新的函数,这样你就可以抛开递归这个概念来思考调用过程中到底发生了什么了。
纯自己的理解。 |
5
augustheart 2020-01-29 17:03:32 +08:00 1
当然,考虑到你自称初学者,我就啰嗦一句,理解递归首先要求你对函数调用有足够的理解,你对函数调用有清楚的理解,递归就不难理解
|
6
xxx749 2020-01-29 17:03:39 +08:00 via Android
|
8
ipwx 2020-01-29 17:07:56 +08:00 2
如果是没有副作用的函数,可以用数学的递推公式来理解。其实这也是理解动态规划最好的方式,什么看代码反而理解不了动态规划。
|
9
ipwx 2020-01-29 17:08:36 +08:00
比如斐波那契递推公式:
f(n) = f(n-1) + f(n-2) f(2) = f(1) = 1 |
10
chitanda 2020-01-29 17:14:40 +08:00 via iPhone
以前看一本书,书名忘记了,有个说法,leap of faith。其实我刚开始学递归也是很难理解,我的办法就是干,看一遍不懂看两遍,没事就找出来看看想想
|
11
Inside 2020-01-29 17:15:39 +08:00 5
翻一下高中课本,看看数学归纳法,递归的数学基础就是这个,代码实现是证明的形式。
|
12
eason1874 2020-01-29 17:20:40 +08:00 1
循环重复做一件事,直到符合退出条件。
如果这个循环是通过函数调用自身实现的,就叫递归。 |
13
Building 2020-01-29 17:27:20 +08:00 via iPhone 1
不要想着那些循环概念,其实归递也是调用函数,凡是遇到归递,你就想着调用函数就行了,然后看参数,看流程。
|
14
qwerthhusn 2020-01-29 17:40:25 +08:00
斐波拉契
汉诺塔 |
15
netlous 2020-01-29 17:44:57 +08:00 33
这个链接能帮助你了解递归:
https://www.v2ex.com/t/640834 |
16
dangyuluo 2020-01-29 17:56:06 +08:00
你需要一个热心的大哥哥,手把手教你用 C 写一个递归函数,然后用 gdb 调试,看一下函数是怎么进入自己的,栈是怎么一步步被吃干净的
|
17
xiri 2020-01-29 17:59:49 +08:00 via Android
自己把递归的过程画出来
|
19
ericgui 2020-01-29 18:06:59 +08:00 1
写递归,就是套娃
但为了防止无线循环,你记住,任何递归,第一步必然是写退出条件。 |
20
t6attack 2020-01-29 18:14:40 +08:00
写一个 遍历文件夹及子文件夹 就理解了。
|
21
monstervivi 2020-01-29 18:25:13 +08:00
看一下盗梦空间然后总结一下就知道了。
|
22
vance123 2020-01-29 18:28:22 +08:00 via Android
|
23
Justin13 2020-01-29 18:31:18 +08:00 via Android
把递归看做循环,退出条件类比迭代条件
|
24
wssy 2020-01-29 18:39:22 +08:00 via Android
个人认为递归是分治思想的体现。
系统性学习下算法理解会深入些,我以前刚接触编程时也是一脸茫然,多解决些题目,看些书,就慢慢理解一点了 |
25
hakono 2020-01-29 18:49:48 +08:00 via Android
或者我觉得可以考虑把递归的学习适当延后
递归虽然写好了很优雅,但是一切的递归都是能等效翻译为循环的。也就是说,实在吃力可以先用循环顶着呗。等你编程经验上来了自然在应用中会逐渐。产生递归的思想 (顺便,在团队中不太想看到别人的代码里出现太多递归 |
26
1a0ma0 2020-01-29 19:18:55 +08:00
写点汇编试试?其实就是寄存器保存信息,然后跳转位置。可以看看《计算机组成要素》这本书,跟着这本书把上项目都都实现了。
|
27
kokodayo 2020-01-29 19:24:59 +08:00
从前有座山,山里有座庙……
|
28
Cbdy 2020-01-29 19:36:47 +08:00 via Android
可以用栈来理解
|
29
lscho 2020-01-29 19:39:16 +08:00
递归就是,我提醒自己明天提醒自己,直到某天结束。。。这就是递归,“提醒”就是函数,“明天提醒”就是在函数执行中再次调用当前函数,“某天结束”就是退出条件。
|
30
wensonsmith 2020-01-29 19:42:47 +08:00 2
每次我都会想这个栗子:
周末你带着女朋友去电影院看电影,女朋友问你,咱们现在坐在第几排啊?电影院里面太黑了,看不清,没法数,现在你怎么办? 别忘了你是程序员,这个可难不倒你,递归就开始排上用场了。于是你就问前面一排的人他是第几排,你想只要在他的数字上加一,就知道自己在哪一排了。但是,前面的人也看不清啊,所以他也问他前面的人。就这样一排一排往前问,直到问到第一排的人,说我在第一排,然后再这样一排一排再把数字传回来。直到你前面的人告诉你他在哪一排,于是你就知道答案了。 来自: https://www.showdoc.cc/476806889376927?page_id=2791994496480277 |
31
janxin 2020-01-29 19:43:04 +08:00
其实就是数学递归的表现
|
32
laravel 2020-01-29 19:43:23 +08:00
结合栈来理解啊
|
33
ayase252 2020-01-29 19:44:44 +08:00 via iPhone
把一个大问题分解成若干个相同的小问题。
|
34
orzorzorzorz 2020-01-29 19:52:08 +08:00
假设只有一层的调用自身,你就想着到递归的点,程序会停下来,先重新执行自身,然后等执行完了,返回当前的值,然后继续上个层次的程序就得了。多层的递归就是到条件满足了,然后一层层跳回到第一层。
|
35
1runningbird 2020-01-29 20:00:43 +08:00 via iPhone
从前有座山山里有个庙,庙里有个老和尚给小和尚讲故事,讲的故事是:从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲的故事是....
|
36
Shiyq 2020-01-29 20:04:58 +08:00
就是我用我自己啊
|
37
sadhen 2020-01-29 20:11:28 +08:00
前段时间给我的侄女买了一个木制的汉诺塔玩具,递归应该从娃娃开始学起
|
38
aguesuka 2020-01-29 20:19:35 +08:00 via Android
《实分析》归纳法,有明确定义
|
39
symeonchen 2020-01-29 20:58:50 +08:00
想象觉得困难可以通过画图来帮助理解,或者写公式也可以,都有帮助。
另外,没看错的话,头像是「黒崎レイナ」吧,v 站对头像的选择其实有一些简单的约束,可阅读 https://www.v2ex.com/t/62637 |
40
pangleon 2020-01-29 21:19:35 +08:00
去做 LEETCODE 反转链表的递归做法
|
41
ryanpenber 2020-01-29 21:35:04 +08:00
你去事业单位办事,你对业务员说,你要取出你保存的合同内容。业务员说稍等,我要请示值班经理;值班经理听了以后也不知道怎么办,说我去请示单位领导;单位领导觉得没处理过这个案例,请示区域经理;区域经理说:这点小事都办不好?合同是 XXXXX。单位领导拿到以后,把合同拿给值班经理,值班经理拿到了合同给了业务员;业务员把合同交给了你。
程序返回的结果由下一层程序提供,这是我理解的递归 |
42
52coder 2020-01-29 21:55:22 +08:00
递归你可以理解为有限次函数调用,调用到最后一次后,再层层向上返回。
|
43
jdz 2020-01-29 22:09:46 +08:00 via Android
可以看下《计算机系统概括》,其中有一章专门讲递归
|
44
versee 2020-01-29 22:13:49 +08:00 via Android 3
1.不要人肉追踪函数的调用,你深入几层以后根本拔不出来
2.写好递归停止的条件以后,把每次的函数调用当成一个立即得到答案的黑盒 |
45
ebony0319 2020-01-29 22:16:00 +08:00 via Android
就是数学里面的抽象函数,类似于:f(x)=f(x-1)+1,这种一般会给一个条件:已知 f(1)=1
|
46
omph 2020-01-29 22:16:21 +08:00
通过树结构来理解
|
47
AX5N 2020-01-29 22:41:50 +08:00 1
感觉楼上基本都是在讲废话,楼主要听得懂你们说的那些还问么。
|
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 的变换过程。 |
49
jakezh 2020-01-29 23:51:40 +08:00
|
50
adang313 2020-01-30 00:22:59 +08:00 via Android
我也在学习中
|
51
SlipStupig 2020-01-30 00:54:36 +08:00
自己给自己打电话
|
52
levelworm 2020-01-30 01:07:52 +08:00
我也不太擅长递归。我觉得基本思想很好理解,就是把任务分解成相同性质的小任务。但是我觉得有两个难点,一个是理解每次递归之后必然会返回到上一层,第二个是如何分解。我觉得这个和智商有关,我这种智商不够的就只能先硬来,做的多了就好些。
|
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 了 |
54
alphatoad 2020-01-30 04:03:30 +08:00 via iPhone 5
要理解递归,你必须理解递归
|
55
Shook 2020-01-30 04:13:51 +08:00
可能应该多写写树的题目,比如如何寻找节点。
|
56
happyz90 2020-01-30 06:41:03 +08:00 via Android
感觉汉诺塔来演示递归还是挺形象的
|
58
ioriwong 2020-01-30 08:47:40 +08:00 via iPhone
大家忽略了“初中生”,数学归纳法,递推数列 都没学
|
59
SharkU 2020-01-30 09:56:32 +08:00
只要问题可以进行向下分解,并最终可以直接进行求解。
[递归]( https://segmentfault.com/a/1190000007420201) |
60
zhw2590582 2020-01-30 11:19:08 +08:00
刚开始会不容易理解,等接触多了,练习多了就慢慢熟练了,我以前和你一起看见递归就头疼
|
61
yjxjn 2020-01-30 11:22:54 +08:00
我给你讲个故事:
从前有座山,山上有座庙,庙里有个老和尚和小和尚,老和尚对小和尚说:从前有座山,山上有座庙,庙里有个老和尚和小和尚,老和尚对小和尚说:从前有座山,山上有座庙,庙里有个老和尚和小和尚,老和尚对小和尚说:从前有座山,山上有座庙,庙里有个老和尚和小和尚,老和尚对小和尚说:从前有座山,山上有座庙,庙里有个老和尚和小和尚,老和尚对小和尚说:从前有座山,山上有座庙,庙里有个老和尚和小和尚,老和尚对小和尚说:从前有座山,山上有座庙,庙里有个老和尚和小和尚,老和尚对小和尚说:从前有座山,山上有座庙,庙里有个老和尚和小和尚,老和尚对小和尚说: 理解了吗???哈哈 |
62
chengxiao 2020-01-30 11:27:14 +08:00
照着书上的写,多写几次级明白了
写着写着就明白了 |
63
by73 2020-01-30 11:30:21 +08:00
学下 functional programming 就好,用数学的方式去理解它。当然还有其他方式是去 leetcode 之类的地方,用递归实现下链表、树之类的操作算法。
|
64
bullfrog 2020-01-30 12:06:02 +08:00
1.在一个副本里进入到另一个副本,退出副本的时候还是之前哪个副本
2.盗梦空间 |
65
herozzm 2020-01-30 13:11:28 +08:00
A 是确诊患者,然后 Ta 做高铁回家,一个车厢的其他人是 B,然后 B 们又去其他地方接触其他人,利用递归可以最终得到所有接触过的人员
|
66
bugmakerxs 2020-01-30 13:44:35 +08:00 via Android
方法栈理解清楚了,递归就懂了,递归其实就是一次普通的方法调用而已
|
67
netty 2020-01-30 13:46:55 +08:00 via Android
极客时间的《数据结构与算法讲得不错》:
1.编写递归代码的关键是,只要遇到递归,我们就把它抽象成一个递推公式,不用想一层层的调用关系,不要试图用人脑去分解递归的每个步骤。 2.写递归代码的关键就是找到如何将大问题分解为小问题的规律,并且基于此写出递推公式,然后再推敲终止条件,最后将递推公式和终止条件翻译成代码。 文档:10_递归:如何用三行代码找到“最终推荐人”? 链接: http://note.youdao.com/noteshare?id=d026fcabe93136f02c95efc449c6624f |
68
netty 2020-01-30 13:49:45 +08:00 via Android
然后多实践,徒手写,从最简单的阶乘和斐波那契数列开始
|
69
kaifeii 2020-01-30 16:35:56 +08:00
所有递归都可以用栈替代,递归只是把一部分过程数据记录在函数栈里了。
建议你先学会堆栈结构,然后了解一点编译原理,然后你就知道把可以把递归的每一层局部变量包括入参压到栈里。 从几个市面上标准的简单递归代码开始做栈化练习,多做几次你就都懂了。 为了防止 stackoverflow,实际应用上也要用栈代替递归,迟早要学的。 |
70
rainbowchou 2020-01-30 16:48:11 +08:00
楼上说的很有道理啊 就是数据结构 栈 ,函数调用就是把数据压入栈 弹出栈操作,递归就是全压入,然后倒序弹出,先学学数据结构吧
|
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 时就返回空串 |
72
marlondu 2020-01-30 20:26:46 +08:00
简单点,不要看他们扯那么复杂,递归,就是在函数里自己调自己。
|
73
xutao881 2020-01-30 20:49:47 +08:00
let num = 0;
f a(){ if(num>10){ } } |
74
xutao881 2020-01-30 20:50:35 +08:00
妈耶,没打完就回复了。。。意思就是条件不满足的时候调用自己,满足之后 return
|
75
wnpllrzodiac 2020-01-30 20:55:34 +08:00 via Android
汉诺塔,当初想了好几个小时
|
76
Electronika 2020-01-31 00:44:07 +08:00 via iPhone
@netlous hhhhh
|
77
ajaxfunction 2020-01-31 10:29:25 +08:00
如果是会用,多写几次就可以了,
如果想理解,必须明白堆栈的概念和函数生命周期和变量作用域,特别是堆栈 |
78
timwu 2020-01-31 15:39:33 +08:00
看我这篇博客文章: https://wuzhiwei.net/ds_app_stack/ 栈 递归 汉诺塔
|
79
GAsss 2020-01-31 15:45:42 +08:00 via Android
可以看看 The Little Schemer
|
80
Kaakira 2020-01-31 17:23:15 +08:00
|
81
deepred 2020-02-01 08:59:58 +08:00
|
82
AndyZhuAZ 2020-02-01 09:43:25 +08:00
画个图,或者联想一下数学里的高阶导数((f'(x)')')'
|
83
RickyC 2020-02-01 10:12:45 +08:00
我觉得轻易不要使用递归.
|
84
jxie0755 2020-02-12 04:28:03 +08:00
很多人说了很多各种高端术语, 什么域啊, 堆栈啊, 什么生命周期啊, 都是些已经懂了什么叫递归再反过来看问题的人说出来的话, 对你一个不理解什么是递归的人没有什么帮助.
我作为一个几年前的新手用最通俗的话告诉你. 去找一个最简单的递归函数, 比如斐波那契, 求第 10 个数, 一定要彻底了解它是怎么运行的. 自己用手画出来. 然后你就懂了, 因为它在执行的时候, 还没结束, 还没返回结果, 就遇到了它自己, 于是又进入了这个函数一次, 不断进入直到不需要进入为止, 因为你最终遇上了最简单的情况, 直接得到了结果. 最后再把结果一步步推回去. 最重要的一句话就是: 递归函数就是从头一路看到脚, 在从脚一路返回到头. |