w***g
发帖数: 5958 | 1 尾递归编译器能自动转化为循环。对于像Haskell这种还对性能有所追求的语言，递归
的不同写法效率能差很多。 |
|
w***g
发帖数: 5958 | 2 各有各的好处。循环更像是实现细节，递归则更像问题的描述。要说容易理解，我觉得
很多时候递归更容易理解。但是循环更便于程序员掌控程序的复杂度。函数式编程写的
好的看起来像是在很高的层次上定义问题，问题定义清楚了程序也就出来了。程序可以
写得非常精炼。要是想体验体验，可以去看眼Haskell的标准库的代码。比C++标准库要
干净得多得多。
函数式变成的恶心之处要到monad才能表现出来。经历各种诘屈聱牙的定义之后，发现
其实只是实现了一个过程性的子语言。目前貌似没有从表象到本质都是纯函数式编程的
语言。要说纯，C++的模板语言其实是比很多号称函数式语言的语言更加纯净的一种函
数式语言。 |
|
G**Y
发帖数: 33224 | 3 我怀疑初学的话，即使写了递归也未必知道呀
如果不递归，只是pattern matching。很多语言都很容易。 |
|
|
o***o
发帖数: 11767 | 5 【 以下文字转载自 PDA 讨论区 】
发信人: pker (我要那天再挡不住我眼), 信区: PDA
标 题: 人就是个递归
发信站: BBS 未名空间站 (Tue Nov 28 02:27:21 2017, 美东)
11月初觉悟了，
把各种手机该退的退，该卖的卖，
最后就留下一个iphone 7+和8+。
经过BF和CM二轮攻势，
俺他娘的又多了iphone x，s7 edge, pixel c, essential phone
俺就像个傻逼一样的不停的买和卖。
其实说到底，就是没钱，
有钱就不停的买和卖超跑，游艇或者飞机了。
又穷又傻逼 |
|
发帖数: 1 | 6 用递归形式写迭代就是
f (last) = if (predict(last)) then return last else return f ( calc(last) ) |
|
b*******8
发帖数: 37364 | 7 属实。迭代是一叉树的形式，当然也可以用递归遍历树的方法。 |
|
g*******y
发帖数: 1930 | 8 可以判断i/=10之后，如果i是0了，就不继续递归了。
不管i是不是0，i%10是肯定会成为一个节点的。
如果输入是0，那么就输出一个单节点就结束了
如果输入不是0，最后i变成0以后也就结束了。
pair construct(int i){
Node *cur = new Node;
cur->data = i%10;
cur->next = 0;
i/=10;
if(i){
pair r = construct(i);
r->second->next = cur;
return make_pair(r->first,cur);
}else{
return make_pair(cur,cur);
}
} |
|
c*****y
发帖数: 90 | 9 谢谢大家。再问个递归的方法，如何reverse doubly linked list? |
|
C**********n
发帖数: 100 | 10 一直很迷糊，如果一个算法有递归的话，如何算复杂度呢？ |
|
S**Y
发帖数: 136 | 11 有重复元素的排列,递归算法应该怎么做呢?
比如( 1 2 3 3)
则输出: 1233 1323 1332 2133 2313 2331 ,etc. |
|
r****o
发帖数: 1950 | 12 我说的非递归的stack是程序自己的栈(数据结构里面的那个stack)，用来保存中间信息
。但是它也会消耗系统栈吧。 |
|
|
t**n
发帖数: 272 | 14 在实际的工程项目中用递归千万要小心, 很多时候程序栈耗尽了就直接出错
自己写代码申请空间更有控制,另外占用空间也更小
stack |
|
m*****g
发帖数: 226 | 15 讨论一下啊
一般的函数调用，不管是否递归导致的，为何要保存local变量。local变量应该还在原
来的函数栈里面阿。 |
|
g**e
发帖数: 6127 | 16 我认为是算的，因为用了系统的stack
有些题目要求O(1) space，能不能用递归？ |
|
c****p
发帖数: 6474 | 17 如果递归次数是O(1)级别的，那用也没问题吧。
非常数级别的，不好说。。 |
|
c********1
发帖数: 161 | 18 当然不是，比如quick sort就是可以用递归实现的in place sorting....... In place
的意义不在于不用空间或者用的空间很小，而是说随着N的增长，运行所需的extra的空
间是constant的。 |
|
y*******g
发帖数: 6599 | 19 att
CLRS上用grey 表示第一次发现node, black表示finish
在递归的时候很明确，但用stack的话怎么区分 grey/black? |
|
y*******g
发帖数: 6599 | 20 怎么push?是进第一个还是第二个stack? 感觉要不停的开stack，，也就是递归了 |
|
|
|
|
e***l
发帖数: 710 | 24 直接用一个额外的数组（或者node对象的一个分量）记录颜色，颜色标记的顺序应该和
递归的方法相同：
所有node标白色;
root标灰色并入栈;
while(栈非空){
取得栈顶元素,//必为灰色
找到它第一个白色的邻接node,将其标灰并入栈, //注1
如果没有找到白色邻接node，将栈顶元素标黑并出栈。//所有邻接node已发现
}
注1：可以对每个node记录“已经访问到了第几个邻接node”,避免每次从头搜索 |
|
f********e
发帖数: 166 | 25 板上大牛能不能给贴个代码啊，反转链表用递归咋写啊？谢谢啊谢谢 |
|
|
z**********8
发帖数: 229 | 27 2.2 Implement an algorithm to find the nth to last element of a singly
linked list.
这题我的直觉就是两个指针然后保证两者的距离为n，跟它给出的标准解法一样。但是
他有这么一段话：
“Note: This problem screams recursion, but we’ll do it a different way
because it’s trickier. In a question like this, expect follow up questions
about the advantages of recursion vs iteration.”
实在想不出recursion的解法，可以求达人解释一下么？（如果用两个指针的话应该空
间复杂度是O（1）时间是O（n），n是链表长度。用递归可以做的更好么？advantage在
哪里呢？） |
|
p*****2
发帖数: 21240 | 28 递归的话可以返回next的位置。
最后一个元素返回1,你知道你next的位置，就知道自己的位置了。 |
|
z**********8
发帖数: 229 | 29 谢谢，总觉得用递归不是很straightforward。。。还不如用两个指针。。 |
|
z**********8
发帖数: 229 | 30 谢谢，总觉得用递归不是很straightforward。。。还不如用两个指针。。 |
|
|
p**e
发帖数: 533 | 32 operator 在两个数字前面（不是中间），给一个string（空格分隔的操作符和数字）
，利用递归计算result。
比如：
+ 3 2 表示3+2=5
+ + 3 -2 * 1 6 表示(3+ -2)+(1*6) = 7
大家来写写code。 |
|
|
|
s*******a
发帖数: 8827 | 35 好像最早学到递归是那个把盘子在三个柱子上移来移去的问题，本科c语言课上学的好
像。 |
|
i**********e
发帖数: 1145 | 36 longway2008 贴过的代码，估计是我看过非递归解法最短的行数了。。。但不好消化
bool isMatch(const char *str, const char *pat, bool hasStar=false)
{
if (!*pat) return !*str || hasStar;
const char *s, *p;
for (s = str, p = pat; *s; ++s, ++p) {
if (*p == '*')
return isMatch(s, p+1, true);
else if ( *p != '?' && *s != *p)
return !hasStar ? false : isMatch(str+1, pat, hasStar);
}
while (*p == '*') ++p;
return (!*p);
} |
|
|
h****n
发帖数: 1093 | 38 我的递归版本
bool isMatch(const char *s, const char *p) {
if(*s=='\0')
{
if(*p=='\0') return true;
while(*p)
{
if(*p!='*') return false;
p++;
}
return true;
}
if(*p=='*') return isMatch(s+1,p) || isMatch(s,p+1);
else return (*p=='?'||*p==*s)?isMatch(s+1,p+1):false;
} |
|
h****n
发帖数: 1093 | 39 Leetcode，貌似递归没法通过你的large test cases |
|
i**********e
发帖数: 1145 | 40 要通过large case 只能用非递归的。不过那个面试写太复杂了，很多edge case 要考
虑。
DP 的解法复杂度是 O(m*n) 一般都是 memory exceed，我不知道二爷的为什么 time
limit exceed。也有可能java 跑得慢的缘故吧。二爷的代码如果转换成C++应该是
memory exceed 的。 |
|
|
|
u***8
发帖数: 1581 | 43 103页。那个电话号码对应字母的题目。为什么for loop里面，要在最后判断是不是等
于0 或者是1？
getCharKey(int , int )不就是可以把一个数字对应的3个之一的字母给返回了么？那
么是0或者是1,就返回空的不就够了。为什么要判断下0 1,这个不懂。
updates: code在这里
static final int PHONE_NUMBER_LENGTH = 7;
void printTelephoneWords(int[] phoneNum) {
char[] result = new char [PHONE_NUMBER_LENGTH];
doPrintTelephoneWords( phoneNum, 0, result);
}
void doPrintTelephoneWords(int[] phoneNum, int curDigit, char[] result) {
if ( curDigit == PHONE_NUMBER_LENGTH) {
System.out.println(new S... 阅读全帖 |
|
c********t
发帖数: 5706 | 44 请问用了递归以后，怎么计算空间复杂度？
比如说permution和二叉树preorder遍历吧，怎么计算空间复杂度是多少呢 |
|
w****x
发帖数: 2483 | 45
算法导论上有，比如说斐波那契数列递归的时间复杂度？ |
|
c********t
发帖数: 5706 | 46 请问递归多少层会stackoverflow这道题怎么回答？ |
|
l*****a
发帖数: 14598 | 47 具体点吧
就是说跟每次调用中分配/使用的内存有关系？
如果什么也不干，能递归10000层，使用的很多，几层就完了？ |
|
j*****y
发帖数: 1071 | 48 这个时间递归式子是
T(m, n) = T(m - 1, n) + T(m, n - 1)
可以用 substitution 证明 T(m, n) >= 2^(m + n) |
|
p*****2
发帖数: 21240 | 49 来自主题: JobHunting版 - 关于尾递归 大家能不能给点例子不能转变成尾递归的？我想写写看。谢谢。 |
|
p*****2
发帖数: 21240 | 50 来自主题: JobHunting版 - 关于尾递归
尾递归
def getHeight(root:TreeNode):Int={
recursion(0,List(root))
}
def recursion(layer:Int, list:List[TreeNode]):Int= list match{
case Nil=> layer
case _ => recursion(layer+1, process(list))
}
def process(list:List[TreeNode]):List[TreeNode]={
var newlist:List[TreeNode]=Nil
for(node<-list){
if(!node.left.isEmpty) newlist=node.left.get::newlist
if(!node.right.isEmpty) newlist=node.right.get::newlist
... 阅读全帖 |
|
