请教个问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教个问题

请教个问题# JobHunting - 待字闺中

y*32013-10-29 07:10

1 楼

如果题目中要求只能用constant memory，或者要求空间复杂度是O(1)，是不是就不能
用recursion了？

y*32013-10-29 07:10

2 楼

没有人知道吗？。。。跪求！

b*o2013-10-29 07:10

3 楼

和语言实现有关，像Lisp这样的FP语言，尾递归可以是constant memory。

【在 y*****3 的大作中提到】

: 如果题目中要求只能用constant memory，或者要求空间复杂度是O(1)，是不是就不能
: 用recursion了？

y*32013-10-29 07:10

4 楼

谢谢！那如果我用java写，要求Constant memory的话肯定不可以用递归了？

【在 b*****o 的大作中提到】

: 和语言实现有关，像Lisp这样的FP语言，尾递归可以是constant memory。

j*62013-10-29 07:10

5 楼

尾递归实现和语言没关系吧？（理解不对的话求大牛指正）不过一般情况下递归都不
是尾递归
所以就用循环之类的写吧~

A*g2013-10-29 07:10

6 楼

有关系，尾递归是指每个function call的最后一步是call这个function自己，所以前
面stack的内容和后面计算没关系，就可以不存前面stack里的内容了，LISP的解析器或
编译器会做这样的优化
(define (sum start end)
(if (= start end) start
(+ start (sum (+ start 1) end))))
同样的写法，Java或C++一般还是会存整个stack，然后一层层返回
int sum(int start, int end) {
if (start==end)
return start;
else
return start+sum(start+1, end);
}
Java/C++ 如果用loop的话，就不用stack了
int sum(int start, int end) {
int sum = 0;
for (int i=start; i<=end; i++)
sum+=i;
return sum
}

【在 j*********6 的大作中提到】

: 尾递归实现和语言没关系吧？（理解不对的话求大牛指正）不过一般情况下递归都不
: 是尾递归
: 所以就用循环之类的写吧~

b*o2013-10-29 07:10

7 楼

恩，Java的递归是基于stack的，所以不可能是constant memory。

【在 y*****3 的大作中提到】

: 谢谢！那如果我用java写，要求Constant memory的话肯定不可以用递归了？