t******n
发帖数: 2939 | 1 ☆─────────────────────────────────────☆
xiongyp (dreamrain) 于 (Fri May 24 08:41:56 2013, 美东) 提到:
我们假设不知道什么叫素数，我们对正整数集合进行如下的定义来定义素数。（这是从
链接上取下来的，也是I63的定义）
(1) 1不是素数 (base case)
(2) a是素数当且仅当a不能被任何小于它的素数整除。
我曾经多次指出，这个定义在用素数定义素数，是不正确的。但看到很多的反驳如下。
1不是素数, 我们考察2，发现小于2的素数集合为空集，于是2为素数。以此再往下递归
，得出所有素数的定义。我想昨天深入讨论此内容的人，都不会反对我的总结吧。关于
"小于2的素数集合为空集"推出"2为素数"，因我的不慎，还做出过郑重道歉。
好，我们仿造这种递归定义，来定义偶数。
我们假设不知道什么叫偶数，我们对非负整数集合进行如下的定义来定义偶数。
(1) 0不是偶数 (base case)
(2) a是偶数当且仅当a与任何小于它的偶数之差为2的倍数。
我从base case开始。0不是偶数。我们考察... 阅读全帖 |
|
b********0
发帖数: 62 | 2 我感觉递归可以理解为两层意思
第一层是类似于数学归纳法的思想 就是把大问题分解为类似的小问题 这类思想肯定到
处都用得到 没什么好争的
第二层就是代码里的 函数自己调用自己 这种递归都是可以改写为循环的形式的
一般递归由堆栈实现 会有存储和处理的开销
自己写 一般也要多加一个全局变量
所以大家总会有 递归效率低的印象 其实差不了多少
某些递归实现的问题在于同一个问题的重复计算浪费了资源 可以用记忆化改善
尾递归就是一种特殊的形式 返回值在每一层递归都被直接返回为上一层 这样其实用外
部变量存储的意义就没有了 也就可以直截了当的写成循环的形式
一般递归转化为尾递归的方法 我感觉一般也就是增加传递变量 以达到之前外部状态变
量的效果
个人认为递归简洁直观 如果编译器强大到能做好优化 那就完美了 |
|
r****o
发帖数: 1950 | 3 【 以下文字转载自 InterviewHackers 俱乐部 】
发信人: roufoo (五经勤向窗前读), 信区: InterviewHackers
标 题: 请问一个关于递归算法的问题。
发信站: BBS 未名空间站 (Fri Apr 30 11:19:46 2010, 美东)
很多算法可以用递归实现，非常简洁，比如说二叉树的遍历。
但是通常面试的时候也会让实现一个非递归的版本。
我想问的是，非递归的版本相对于递归而言有什么优势呢？
一个方面可能是递归程序会占用系统栈资源，如果递归层次太多，会耗尽系统栈。
但是通常非递归程序也是会用一个stack，如果递归层次太多，这个非递归程序的stack
的size应该也会很大，这不也会耗系统栈资源吗？
请各位大牛指教。 |
|
y****n
发帖数: 743 | 4 来自主题: JobHunting版 - 关于尾递归 我对尾递归不熟，以前与一位朋友讨论面试题，谈到过。
那道题是：两个正整数x和y，求x/y的余数。禁用循环和乘除法。
我只知道有尾递归这个东西，可以避免递归层数过多时压栈溢出。
我从来没想过把普通递归改写成尾递归，所以对这个贴子比较感兴趣。
我也很好奇：
是不是所有的递归都可以写成非递归？
是不是所有的递归都可以写成尾递归？
是不是尾递归都可以改写成循环形式？
前面出的那道题纯属探讨，没有刁难的意思。 |
|
c**s
发帖数: 159 | 5 个人感觉 递归的优势只是代码简单，效率通常比非递归的要低。
因为递归要用到系统栈，所以递归效率低。
没感觉递归比非递归高效，只有递归用所谓备忘录方法（把已经算过的结果保存起来，
再算到这时可以直接返回）才能提高效率，但应该还是比循环的效率低吧。
尾递归不知道具体定义，感觉上就是在一层中自己只调用一次自己，这样可以方便转为
非递归。 |
|
b****g
发帖数: 192 | 6 没错，很多递归的题都是这么做的：
ArrayList tmp 存的是最终结果的其中一个。
在函数里面，这个tmp还没有完全算完，还在逐步添加以得到最终结果。
所以要先执行tmp.add()，使tmp向结果迈进一步。到这里都很好理解。
然后继续执行递归，递归里面当然还是向最终结果迈进，所以才叫做递归。
现在考虑tmp.remove()这行。
你有没有注意到，tmp.add(); dfs(); tmp.remove() 这几行都在一个for循环里面？
这是因为每次循环都对应tmp的一个值。
具体来说，tmp在执行for循环之前本来就有一个值，干干净净处女之身没被糟蹋过。
第一个执行这个循环，先执行tmp.add()得到一个tmp的值，于是tmp破处了。
于是向最终结果迈进了一步，然后执行递归，继续想最终结果迈进。
这一层一层的递归就先不管他。反正他们都是从dfs()这个递归里开始的。
总之执行完刚刚这个dfs()我们还在第一次循环里面。
假如没有这个tmp.remove()，那就继续执行第二次for循环了。
但是错误就出现了。tmp已经在第一次循环里面通过tmp.add()改变了，已经破处... 阅读全帖 |
|
t****a
发帖数: 1212 | 7 我不会把任意的递归问题转换成尾递归。比如，
1. 如果做动态规划，依赖的参数是多维的，应该怎么办？我看到过的尾递归只解决了
自变量为一维的问题。
2. 程序依赖多个子递归问题，应该怎么办？
3. 多个子函数相互嵌套递归怎么办？
如果有解决这方面问题的尾递归的材料，请分享给我，非常感谢。
我只会用memorize function。效率跟iteration还是差一大截。 |
|
w*******2
发帖数: 8 | 8 尾递归和普通递归的区别就是其栈的空间大小是不随着函数的调用而增长的，所以不会
有stack overflow的问题，通过将所需信息直接通过参数传进调用的子函数，这样的过
程很迭代其实没什么区别，对于一些语言，编译器就直接会把尾递归转化成迭代.
对于简单的递归转化成尾递归，可以通过传递参数的方法来保存之前的状态，但是对于
一些多次调用递归，简单的增加传入参数就不行了，可以使用continuation-passing
style(CPS)来实现，此方法仅适用在函数式编程
就执行效率来说，memorization并不迭代差（不考虑空间复杂度的话） |
|
t****a
发帖数: 1212 | 9 我不会把任意的递归问题转换成尾递归。比如，
1. 如果做动态规划，依赖的参数是多维的，应该怎么办？我看到过的尾递归只解决了
自变量为一维的问题。
2. 程序依赖多个子递归问题，应该怎么办？
3. 多个子函数相互嵌套递归怎么办？
如果有解决这方面问题的尾递归的材料，请分享给我，非常感谢。
我只会用memorize function。效率跟iteration还是差一大截。 |
|
w*******2
发帖数: 8 | 10 尾递归和普通递归的区别就是其栈的空间大小是不随着函数的调用而增长的，所以不会
有stack overflow的问题，通过将所需信息直接通过参数传进调用的子函数，这样的过
程很迭代其实没什么区别，对于一些语言，编译器就直接会把尾递归转化成迭代.
对于简单的递归转化成尾递归，可以通过传递参数的方法来保存之前的状态，但是对于
一些多次调用递归，简单的增加传入参数就不行了，可以使用continuation-passing
style(CPS)来实现，此方法仅适用在函数式编程
就执行效率来说，memorization并不迭代差（不考虑空间复杂度的话） |
|
r********d
发帖数: 7742 | 11 没错，递归的代码一般现实中都不用。但是对于理解很关键啊。
计算机里边的递归算法不要太多。。。再加上树等等递归结构上的算法，全是递归的。
很多实际中的问题，理解了递归的解法也能帮助给出好的迭代算法吧。
反正很多新问题，先给出递归解，在找迭代解挺好使的。实在不行了再用堆栈模拟递归
。。。 |
|
g***j
发帖数: 1275 | 12 请问，递归和非递归分别有什么优势和缺点，如何选择使用递归和非递归的方法？
另外，什么情况下，递归的方法比非递归的方法要高效呢？
什么是tail recursion？ |
|
h****e
发帖数: 928 | 13 有些题目要用非递归的解法，例如：
- 递归解法过于简单
- 非递归解法不会很难写，在15-20分钟合理的解题/写代码时间内
- 递归解法嵌套过深，容易造成stack overflow。有些题目你试一下
就会发现递归解法不可行。 |
|
x*****p
发帖数: 1707 | 14 这正是我要你明白的东西。也就是说，在递归定义中的base case，必须符合这个概念
的原始定义。
如果一个概念没有原始的定义，任何纯粹的递归定义都站不住脚。
我们有了素数的原始定义，才发现1不是素数，结果才衍生出了递归定义。也就是说，
原始的素数定义，能衍生出素数的递归定义，其实应该算推论。但在我们还不知道什么
叫素数的前提下，这个递归定义不成立。
同样，你认为0不是偶数的判断是错误的，这就是来源于你对偶数有个原始定义（2的倍
数）的判断。你在判断0是否是偶数的问题上，是不依赖于我后面的递归定义的。
我说这些，不知你看没看懂？ |
|
f****4
发帖数: 1359 | 15 递归函数的space怎么算？
如果递归函数本地有个变量，递归函数被调用k次，space算k还是算1？
递归函数本身的堆栈空间忽略不计么？
递归函数，书上就速度分析，没有空间分析（也可能我看漏了）
place |
|
n******n
发帖数: 567 | 16 lz在一楼提到了三种方法: tail call, memorization, iteration(典型DP解法？)
我不明白LZ的问题，你是说想执着的‘放弃典型DP的方法’来找一种方法专门把‘任何
递归化成尾递归’？那这种方法即使存在，尾递归在stack上面的操作也不可能比典型
DP解法更优。那么这么做的唯一原因就是写成尾递归编码更方便（memorization如果想
优化所用到的比tail call多用的内存，还是可以替代掉）。但对于f(x) = g(f(x-1),.
..,f(1))，和多函数互相调用的情况，好像能否存在转化成tail call要和g的具体函数
有关？还是对于2和3这种情况根本就转化不了？但不论怎么样，在代码方面也看不出比
典型DP解法简单。。。。 |
|
n******n
发帖数: 567 | 17 lz在一楼提到了三种方法: tail call, memorization, iteration(典型DP解法？)
我不明白LZ的问题，你是说想执着的‘放弃典型DP的方法’来找一种方法专门把‘任何
递归化成尾递归’？那这种方法即使存在，尾递归在stack上面的操作也不可能比典型
DP解法更优。那么这么做的唯一原因就是写成尾递归编码更方便（memorization如果想
优化所用到的比tail call多用的内存，还是可以替代掉）。但对于f(x) = g(f(x-1),.
..,f(1))，和多函数互相调用的情况，好像能否存在转化成tail call要和g的具体函数
有关？还是对于2和3这种情况根本就转化不了？但不论怎么样，在代码方面也看不出比
典型DP解法简单。。。。 |
|
a****l
发帖数: 8211 | 18 递归问题真的可以转化为非递归问题吗？我看到的几个使用非递归算法解决递归问题的
东西，其实最后还是要用一个自己做的栈来储存中间信息的，其实我觉得就是一个障眼
法，把原来程序段的栈变成数据段的栈，本质上还是没有解决递归问题的无限内存的根
本缺陷。 |
|
y****n
发帖数: 743 | 19 来自主题: JobHunting版 - 关于尾递归 我试图理解了一下你改写的C(m,n)
有个几问题：
1. 我所理解的尾递归是指在不改变算法的前提下，在函数的结尾处作递归调用。这样
优化编译后，代码可以在进入递归调用之前释放当前函数的堆栈数据。
改编的代码已经修改了算法，计算了很多多余的数据。
比如：C(10,0)，原来直接返回1，改编代码会计算C(0,0)-C(10,n)全部数据
2. 原来代码在最深层调用时，对堆栈的占用是O(m)
而改编的代码对内存的占用是O(m^2)，这样尾递归的意义就不大了。
3. 感觉上改变后的代码已经不需要递归了，循环貌似更简洁。 |
|
s********u
发帖数: 1109 | 20 还只是胡思乱想，也不太严谨。欢迎指正。（只讨论目前算法面试题一般涵盖的范围）
前言：
我知道大家都会说当满足最优子结构、subproblem overlap的时候可以用dp。但其实这
个条件个人感觉不太实用。
1.比如不overlap的时候也可以用dp，只是效率不提高，还增加了space cost而已。（
所以这个原则应该是“适合用dp”，而不是“可以用dp”
另外且不说最优子结构，overlap有时候也较难判断，比如boggle game这个，路径一定
是有重复的，但是
subproblem却未必，因为前驱的访问节点会影响后驱节点的"胜利条件"。
2.另外，就算是有overlap，从实用的角度来说，dp（bottom-up）未必方便实现。比如
用DFS来判定二叉树中是否有某个节点(cc150的4.7），bool cover( root, p )本身是
单纯的DFS访问，subproblem不存在overlap；但对整个问题而言，cover不停的调用，
对整个问题而言subproblem存在overlap。同样的还有4.1.因为这两个题目都在DFS中使
用了DFS，递归函数中调用了递归... 阅读全帖 |
|
h*******e
发帖数: 1377 | 21 额，比如工业界里面尽量避免写递归么，所有递归都变成循环么，还有什么样的编译器
会自动优化呢， 尾递归是什么呢 这个大概就是我的几个问题，看看大家还能想出更多
么， 记得学校好像有道内核编程要变成非递归，因为kernel内存可用空间小，但是是
学校project, 不知道工业界是怎样。 |
|
A*****i
发帖数: 3587 | 22 需要大量递归的时候直接上scala了，不需要的时候根本不写递归
高中dropout工业界经验不足，接触最大的code base也就20来万行没见过一处递归的。
当然做distributed system本来也用不到多少递归 |
|
x*********h
发帖数: 2223 | 23 什么是递归（recursion）？
《哥德尔、埃舍尔、巴赫——集异璧大成》第五章开门见山解释道：
“递归就是嵌套（nesting），各种各样的嵌套。这个概念很普通。（故事里的故事，
电影中的电影，画中的画，俄式洋娃娃中的俄式洋娃娃（甚至括号说明中的括号说明）
——这些还只是递归魅力中的一小部分）”
随后一小节介绍了三个和递归有关的术语：推入（pushing），弹出（popping）、堆栈
（stacks）。
这三个术语第一次出现于上世纪五十年代一种计算机语言IPL的一部分。
“推入”就是暂停手头工作、标记停止地点、开始另一项工作，新工作比原工作要“低
一个层次”。
“弹出”就是结束低层次的工作、在上一层次暂停的地方恢复原工作。
“堆栈”用来记录暂停地点的环境信息。例如接电话过程中有新电话进来，于是暂停第
一个电话开始接第二个电话，不一会又暂停第二个电话来接第三个电话……堆栈可以记
录你结束当前电话后该回到第几个电话、该电话是谁打来的、暂停时你们谈到哪儿了。
显然，《盗梦空间》中多重嵌套的梦就是“递归”，入梦机器负责“推入”，穿越（
kick）操作用来“弹出”，每层梦中留守的人就是“堆栈 |
|
x*****p
发帖数: 1707 | 24 什么叫等价定义？在你用递归方法定义素数的时候，并不知道什么样的数叫素数。但却
硬性规定了1不是素数。对于这种base case的由来，如果所有的递归定义都仅仅是”硬
性“来规定的，那就会出问题。比如我1楼给的偶数的定义，我们在完全不知道何为偶
数的情况下，表面上的定义是没问题的。却定义出一堆奇数。
当然，这种base case如果是符合这个概念的原始定义的，由递归推导出来的定义就没
有问题。
所以，我讲半天，一会说素数定义等价，一会又说不等价，其实就是在质疑用递归方法
定义中的逻辑错误。你所说的证明两个等价，是在明白什么叫素数，在素数有了原始定
义基础之上发生出来的等价关系。
最后问一句吧。我们在完全不知道一个概念的情况下，用递归来定义这个概念，你是如
何判断这个base case的？ |
|
t*******r
发帖数: 22634 | 25 在码工的 formal system 里面，自然数/偶数/素数 都是可以递归定义
并且递归生成的。
对于楼主的问题的回答是：0 要被定义为偶数。
楼主的例子，为啥要对 0 定义，非严格的说法，递归定义需要定义使得
递归生成无二义的 “初始条件”。 “初始条件” 就好比是 “循环入口断言”。
相对严格的说法，递归定义必须能让 token induce/reduce 成
已经定义的无二义的 primitive token。primitive token
不能引用自己而定义（否则是循环定义）。
那楼主说我把 0 定义名字叫奇数行不行。实际上在 formal system
里，定义为奇数完全可以，只不过你所谓的“奇数”就是大伙儿的偶数，
除了名字不一样，其他性质全一样。甚至你定义为“牛鼻”数还是“傻鼻”
数都没有关系，这个也是 formal system 的特性，取名跟意义无关。
当然，如果你在欧几里德这种不是 formal system 的体系里这么
干，估计悖论是免不了的。 |
|
f****4
发帖数: 1359 | 26 这里就用树的中续遍历来说好了
如果是用stack的话，stack最长要能存储树的最长路径
最坏情况长度为n，最优为lgn
那么用递归的话，如果空间需要考虑stack的话，递归算不算inplace？
如果我们认为递归的stack开销不考虑，那么，我假设在这个树递归函数里面maintain
了一个local变量
那么因为这个函数在单核情况下，同一时间最多被调用n次，最少lgn次。那么这个算法
算是inplace么？（毕竟这里用到的额外内存为lgn ~ n 个）
还有，书上那个stack的分析是Amortized analysis
难道inplace也可以说是Amortized inplace?
sort |
|
d**u
发帖数: 1065 | 27 me too. :-) 还有在registry里找东西也用递归。总之，在树形结构里找东西就用递归
，其它情况能不递归尽量不递归。 |
|
t****a
发帖数: 1212 | 28 个人有点执着的喜欢递归而不是iteration，尾递归像递归却本质上是iteration。谢谢
回复，长知识，这就转包子给你。
,. |
|
t****a
发帖数: 1212 | 29 个人有点执着的喜欢递归而不是iteration，尾递归像递归却本质上是iteration。谢谢
回复，长知识，这就转包子给你。
,. |
|
b*****o
发帖数: 715 | 30 来自主题: JobHunting版 - 关于尾递归 那可能我对尾递归的理解有误。我的理解是，尾递归的state space不会随着问题规模
的增长而增长。
换句话说，不会因为问题规模的变大而出现overflow。
就以硬币问题为例子，普通递归最终会出现stack overflow。而memoization的table最
终也会overflow。但是，真正的尾递归应该不会出现这种问题。难道不是这样吗？ |
|
发帖数: 1 | 31 那既然递归什么时候都不能用，那也就是没有存在的意义咯？
估计是我们这个系统垃圾和我们工程师垃圾，反正我们这里用递归，从architect到虾
兵蟹将我都见过用递归。我们的系统估计用了递归，performance也是垃圾，也就能处
理千万级别的qps，99p的延迟在100ms内
: 问这样的问题，给你entry level不能再多了。
|
|
x*****p
发帖数: 1707 | 32 我看过，凭我学数学的直觉，这些递归定义都是建立在对原始定义认可的基础之上的。
所以说，纯粹的递归定义本身是用概念定义概念，本身就是矛盾的。
举这个链接的一例来说，定义自然数。先申明1是自然数，然后递归说如果N是自然数，
那N+1也是自然数。但这个定义忽略了一条，就是为什么这么肯定1是自然数？这是因为
自然数本身的定义，就证明了1是自然数。离开了自然数的本身定义，这个递归定义没有
任何的意义。 |
|
x*****p
发帖数: 1707 | 33 试图用很多方法，总是让人不明白。我希望我下面的说法，能让大家明白问题所在。
我如果要用递归定义素数，为了不与素数的原始定义冲突，让大家对”素数“这个概念
产生歧义，我在下面的全程不提素数两字。
我们定义正整数集体的一个子集X，满足下面的条件
(1) 1不属于X
(2) x属于X，当且仅当x不能被任何X中小于x的数整除
通过这个递归定义，我们得到了集合，通过比较我们传统定义的素数集合，发现二者是
完全一样的。于是我们称由此递归定义出来的集合中的元素，为素数。
我一直坚持的就是，在完全不知道素数定义的前提下，递归定义中也不应该有”素数“
这个词。
在1楼举的偶数的例子，也如同上面用集合办法定义，得出来的集合，发现和我们认知
的奇数集合是完全一样的，所以得出来的，就不能称为偶数，而称为奇数。只要我的递
归定义中不出现”偶数“这样的字眼，就没问题了。
如果还看不懂，我就无语了，也不用回贴了。 |
|
w***n
发帖数: 1084 | 34 你这个递归定义没有问题. 你这个递归定义和数学归纳法是一样的.
递归和循环是两码事情. 递归是有起点的, 循环是没有起点的 |
|
c*****y
发帖数: 90 | 35 Given an unsigned integer 1345, the program constructs a linked list of
1->3->4->5.
有人先得出一个linked list: 5->4->3->1，然后reverse得到1->3->4->5. 我想直接得到
1->3->4->5，非递归很容易，用递归如何做？我迷惑在跳出递归的那步如何写？if(num
/10==0)
我的部分code如下，有疑问的地方用问号表示了。
Node * ConstructLinkedList(in num, Node *head)
{
if(num==0)
{
head=new Node(num, NULL);
return head;
}
if(num/10=0)
{
head->data=num;
head->next=????
}
else
{
head=new Node();
head->data=num%10;
head=ConstructLinkedL |
|
h****8
发帖数: 599 | 36 递归所需要进栈的信息会更多吧 比如说二叉树前序遍历，非递归用栈时只需要记录节
点的指针，而递归需要记录当前函数的地址，当前PC指针，以及所有函数中local 变量
，开销大得多。再加上进出函数时对memory的寻址，就会慢了
stack |
|
l*****a
发帖数: 14598 | 37 我认为
不是说非递归的版本效率高，因为递归解法过于简单直接，人家考察不出来你的能力
问你非递归解法才能看出你的能力
stack |
|
h****e
发帖数: 928 | 38 我先抛一个。
最早什么时候知道递归：看一本Logo的书，讲了怎么用
海龟画图以后，后面讲递归，举的例子是天安门城楼上
有国徽，国徽里有天安门...
最近什么时候用过：回顾自己过去几年在公司写的code，
从来没有用过。但是最近跟着版上练题，递归的题目已经
做了几十道了。 |
|
d**e
发帖数: 6098 | 39 可以把123各举个例子吗？
应该也不是所有递归都可以转化为尾递归的，比如树的遍历就好像不行 |
|
t****a
发帖数: 1212 | 40 memorize仍然是递归，递归就需要将push pop局部变量，这应该是变慢的重要原因吧。
另外memorize有stackoverflow的风险。JVM上似乎1W层就挂了。
由于会记住所有的调用，memroize还会吃掉大量的内存，可能造成out of memory。迭
代的方法可以自己选择保留什么变量所以没有这个问题。 |
|
d**e
发帖数: 6098 | 41 可以把123各举个例子吗？
应该也不是所有递归都可以转化为尾递归的，比如树的遍历就好像不行 |
|
t****a
发帖数: 1212 | 42 memorize仍然是递归，递归就需要将push pop局部变量，这应该是变慢的重要原因吧。
另外memorize有stackoverflow的风险。JVM上似乎1W层就挂了。
由于会记住所有的调用，memroize还会吃掉大量的内存，可能造成out of memory。迭
代的方法可以自己选择保留什么变量所以没有这个问题。 |
|
l*******b
发帖数: 2586 | 43 嗯，functional里面的lazy evaluation sequence不知道怎么实现的．这个和
memorization有点像吧，像fibonacci数列那样的．不知道是bottom up的实现还是top
down的实现，bottom up貌似不需要stack 调用，top down就是递归了，当然这个例子
两个是等价的可以互相转化，可以写成尾递归的形式．一般的就不知道了．看看那位大
牛讲讲 |
|
k****n
发帖数: 1334 | 44 尾递归是递归发生在function最后，确定可以转换为非递归 |
|
n******n
发帖数: 567 | 45 但凡递归的，都可以转化到非递归，用相同的memory |
|
h*******l
发帖数: 22 | 46 不要误导群众啊， 我碰到好多次说递归太简单， 要求用非递归再实现一下 |
|
l**h
发帖数: 893 | 47 比如Binary Tree的traverse, 用递归是trivial,
不用递归特别是post order,还有有点搞头 |
|
b******7
发帖数: 92 | 48 面试中有可能会问到啊，我就被问过merge-sort的非递归。
类似的有quick-sort,path sum, is balance tree。就这个感觉最难，很容易被里面的
逻辑搞晕
而且递归算法只能描述算法思想，实际工程中感觉不适用，还得用stack转非递归 |
|
s******c
发帖数: 1920 | 49 DP 可以用递归来实现 (算出来一个子问题的解以后存下来 下次直接查表).
也可以不用递归直接用查表填表的方式实现.
我上的算法课上, 老师实际上先用递归来演示DP的精髓. |
|
|
