y*****3
发帖数: 451 | 1 如果题目中要求只能用constant memory，或者要求空间复杂度是O(1)，是不是就不能
用recursion了？ |
y*****3
发帖数: 451 | |
b*****o
发帖数: 715 | 3 和语言实现有关，像Lisp这样的FP语言，尾递归可以是constant memory。
【在 y*****3 的大作中提到】
: 如果题目中要求只能用constant memory，或者要求空间复杂度是O(1)，是不是就不能
: 用recursion了？
|
y*****3
发帖数: 451 | 4 谢谢！那如果我用java写，要求Constant memory的话肯定不可以用递归了？
【在 b*****o 的大作中提到】
: 和语言实现有关，像Lisp这样的FP语言，尾递归可以是constant memory。
|
j*********6
发帖数: 407 | 5 尾递归实现和语言没关系吧？（理解不对的话求大牛指正） 不过一般情况下递归都不
是尾递归
所以就用循环之类的写吧~ |
A******g
发帖数: 612 | 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*****o
发帖数: 715 | 7 恩，Java的递归是基于stack的，所以不可能是constant memory。
【在 y*****3 的大作中提到】
: 谢谢！那如果我用java写，要求Constant memory的话肯定不可以用递归了？
|
g*********e
发帖数: 14401 | 8 跟compiler有关
【在 j*********6 的大作中提到】
: 尾递归实现和语言没关系吧？（理解不对的话求大牛指正） 不过一般情况下递归都不
: 是尾递归
: 所以就用循环之类的写吧~
|
