s*y
2 楼
基础薄弱哈，请勿见笑。
最近在上udemy上的C++算法课：https://www.udemy.com/algorithms-bootcamp-in-c/
这个老师说尾递归不需要堆栈，并举了求阶乘的两个例子对比：
int factorial(int n) {
if (n == 1) return 1;
return n * factorial(n - 1);
}
int factorialAccumulator(int n, int accumulator) {
if (n == 1) return accumulator;
return factorialAccumulator(n - 1, n * accumulator);
}
他说factorialAccumulator()这样就不会用到堆栈了。我死活想不明白怎么就不需要了
。他说得对吗？大牛们能解释一下吗？
多谢！
最近在上udemy上的C++算法课：https://www.udemy.com/algorithms-bootcamp-in-c/
这个老师说尾递归不需要堆栈，并举了求阶乘的两个例子对比：
int factorial(int n) {
if (n == 1) return 1;
return n * factorial(n - 1);
}
int factorialAccumulator(int n, int accumulator) {
if (n == 1) return accumulator;
return factorialAccumulator(n - 1, n * accumulator);
}
他说factorialAccumulator()这样就不会用到堆栈了。我死活想不明白怎么就不需要了
。他说得对吗？大牛们能解释一下吗？
多谢！
t*u
3 楼
没有。
【在 N***1 的大作中提到】
: 谢谢！
【在 N***1 的大作中提到】
: 谢谢！
s*y
4 楼
他之后又举了例子，说factorial()这样写就可以清楚地看出需要堆栈了：
int factorial(int n) {
if (n == 1) return 1;
m = n * factorial(n - 1);
return m;
}
那我就奇怪了，factorialAccumulator()也可以这样处理啊，他就不提了。
int factorialAccumulator(int n,int accumulator) {
if (n == 1) return accumulator;
m = factorialAccumulator(n - 1, n * accumulator);
return m;
}
【在 s******y 的大作中提到】
: 基础薄弱哈，请勿见笑。
: 最近在上udemy上的C++算法课：https://www.udemy.com/algorithms-bootcamp-in-c/
: 这个老师说尾递归不需要堆栈，并举了求阶乘的两个例子对比：
: int factorial(int n) {
: if (n == 1) return 1;
: return n * factorial(n - 1);
: }
: int factorialAccumulator(int n, int accumulator) {
: if (n == 1) return accumulator;
: return factorialAccumulator(n - 1, n * accumulator);
int factorial(int n) {
if (n == 1) return 1;
m = n * factorial(n - 1);
return m;
}
那我就奇怪了，factorialAccumulator()也可以这样处理啊，他就不提了。
int factorialAccumulator(int n,int accumulator) {
if (n == 1) return accumulator;
m = factorialAccumulator(n - 1, n * accumulator);
return m;
}
【在 s******y 的大作中提到】
: 基础薄弱哈，请勿见笑。
: 最近在上udemy上的C++算法课：https://www.udemy.com/algorithms-bootcamp-in-c/
: 这个老师说尾递归不需要堆栈，并举了求阶乘的两个例子对比：
: int factorial(int n) {
: if (n == 1) return 1;
: return n * factorial(n - 1);
: }
: int factorialAccumulator(int n, int accumulator) {
: if (n == 1) return accumulator;
: return factorialAccumulator(n - 1, n * accumulator);
r*t
5 楼
如果返回值直接被返回的话，编译器能把这一层调用给优化掉。
【在 s******y 的大作中提到】
: 他之后又举了例子，说factorial()这样写就可以清楚地看出需要堆栈了：
: int factorial(int n) {
: if (n == 1) return 1;
: m = n * factorial(n - 1);
: return m;
: }
: 那我就奇怪了，factorialAccumulator()也可以这样处理啊，他就不提了。
: int factorialAccumulator(int n,int accumulator) {
: if (n == 1) return accumulator;
: m = factorialAccumulator(n - 1, n * accumulator);
【在 s******y 的大作中提到】
: 他之后又举了例子，说factorial()这样写就可以清楚地看出需要堆栈了：
: int factorial(int n) {
: if (n == 1) return 1;
: m = n * factorial(n - 1);
: return m;
: }
: 那我就奇怪了，factorialAccumulator()也可以这样处理啊，他就不提了。
: int factorialAccumulator(int n,int accumulator) {
: if (n == 1) return accumulator;
: m = factorialAccumulator(n - 1, n * accumulator);
m*n
6 楼
本版的忙碌大佬都觉得回答人的问题是被占便宜，吼吼～
T*x
7 楼
我觉得是编译器优化的问题，这两种写法的最显著区别是，accumulator的写法不需要
存函数返回值，因为return的就只是函数返回值，没有用函数返回值再进行计算，这样
的写法编译器就容易优化它。
【在 s******y 的大作中提到】
: 基础薄弱哈，请勿见笑。
: 最近在上udemy上的C++算法课：https://www.udemy.com/algorithms-bootcamp-in-c/
: 这个老师说尾递归不需要堆栈，并举了求阶乘的两个例子对比：
: int factorial(int n) {
: if (n == 1) return 1;
: return n * factorial(n - 1);
: }
: int factorialAccumulator(int n, int accumulator) {
: if (n == 1) return accumulator;
: return factorialAccumulator(n - 1, n * accumulator);
存函数返回值，因为return的就只是函数返回值，没有用函数返回值再进行计算，这样
的写法编译器就容易优化它。
【在 s******y 的大作中提到】
: 基础薄弱哈，请勿见笑。
: 最近在上udemy上的C++算法课：https://www.udemy.com/algorithms-bootcamp-in-c/
: 这个老师说尾递归不需要堆栈，并举了求阶乘的两个例子对比：
: int factorial(int n) {
: if (n == 1) return 1;
: return n * factorial(n - 1);
: }
: int factorialAccumulator(int n, int accumulator) {
: if (n == 1) return accumulator;
: return factorialAccumulator(n - 1, n * accumulator);
j*w
8 楼
这个：
int factorial(int n) {
if (n == 1) return 1;
m = n * factorial(n - 1);
return m;
}
用了临时变量。而临时变量是需要栈空间的。所以栈会增长。
int factorial(int n) {
if (n == 1) return 1;
m = n * factorial(n - 1);
return m;
}
用了临时变量。而临时变量是需要栈空间的。所以栈会增长。
s*y
9 楼
可如果写成：
int factorialAccumulator(int n,int accumulator) {
if (n == 1) return accumulator;
m = factorialAccumulator(n - 1, n * accumulator);
return m;
}
也会用到临时变量。是否编译器很聪明，觉得这个临时变量用不上就消了？
【在 j*****w 的大作中提到】
: 这个：
: int factorial(int n) {
: if (n == 1) return 1;
: m = n * factorial(n - 1);
: return m;
: }
: 用了临时变量。而临时变量是需要栈空间的。所以栈会增长。
int factorialAccumulator(int n,int accumulator) {
if (n == 1) return accumulator;
m = factorialAccumulator(n - 1, n * accumulator);
return m;
}
也会用到临时变量。是否编译器很聪明，觉得这个临时变量用不上就消了？
【在 j*****w 的大作中提到】
: 这个：
: int factorial(int n) {
: if (n == 1) return 1;
: m = n * factorial(n - 1);
: return m;
: }
: 用了临时变量。而临时变量是需要栈空间的。所以栈会增长。
j*w
10 楼
Depends on the compiler you are using.
【在 s******y 的大作中提到】
: 可如果写成：
: int factorialAccumulator(int n,int accumulator) {
: if (n == 1) return accumulator;
: m = factorialAccumulator(n - 1, n * accumulator);
: return m;
: }
: 也会用到临时变量。是否编译器很聪明，觉得这个临时变量用不上就消了？
【在 s******y 的大作中提到】
: 可如果写成：
: int factorialAccumulator(int n,int accumulator) {
: if (n == 1) return accumulator;
: m = factorialAccumulator(n - 1, n * accumulator);
: return m;
: }
: 也会用到临时变量。是否编译器很聪明，觉得这个临时变量用不上就消了？
s*x
11 楼
即使不用临时变量，也需要把返回地址入栈。所以从理论上来说，所有的递归都有堆栈
溢出的问题，用的局部变量越多，溢出得越快。
【在 j*****w 的大作中提到】
: 这个：
: int factorial(int n) {
: if (n == 1) return 1;
: m = n * factorial(n - 1);
: return m;
: }
: 用了临时变量。而临时变量是需要栈空间的。所以栈会增长。
溢出的问题，用的局部变量越多，溢出得越快。
【在 j*****w 的大作中提到】
: 这个：
: int factorial(int n) {
: if (n == 1) return 1;
: m = n * factorial(n - 1);
: return m;
: }
: 用了临时变量。而临时变量是需要栈空间的。所以栈会增长。
n*3
12 楼
https://www.google.com/search?rlz=1C1GCEU_enUS838US838&ei=ZLK8XPT1DtHI_
Qadyqu4DA&q=%E5%B0%BE%E9%80%92%E5%BD%92%E4%BC%98%E5%8C%96&oq=%E5%B0%BE%E9%80
%92%E5%BD%92+&gs_l=psy-ab.1.0.0i67l4j0i12l3j0l2.1386.1386..3374...0.0..0.70.
70.1......0....1..gws-wiz.......0i71.7tm4eEc3iGo
【在 s******y 的大作中提到】
: 基础薄弱哈，请勿见笑。
: 最近在上udemy上的C++算法课：https://www.udemy.com/algorithms-bootcamp-in-c/
: 这个老师说尾递归不需要堆栈，并举了求阶乘的两个例子对比：
: int factorial(int n) {
: if (n == 1) return 1;
: return n * factorial(n - 1);
: }
: int factorialAccumulator(int n, int accumulator) {
: if (n == 1) return accumulator;
: return factorialAccumulator(n - 1, n * accumulator);
Qadyqu4DA&q=%E5%B0%BE%E9%80%92%E5%BD%92%E4%BC%98%E5%8C%96&oq=%E5%B0%BE%E9%80
%92%E5%BD%92+&gs_l=psy-ab.1.0.0i67l4j0i12l3j0l2.1386.1386..3374...0.0..0.70.
70.1......0....1..gws-wiz.......0i71.7tm4eEc3iGo
【在 s******y 的大作中提到】
: 基础薄弱哈，请勿见笑。
: 最近在上udemy上的C++算法课：https://www.udemy.com/algorithms-bootcamp-in-c/
: 这个老师说尾递归不需要堆栈，并举了求阶乘的两个例子对比：
: int factorial(int n) {
: if (n == 1) return 1;
: return n * factorial(n - 1);
: }
: int factorialAccumulator(int n, int accumulator) {
: if (n == 1) return accumulator;
: return factorialAccumulator(n - 1, n * accumulator);
g*u
13 楼
好像 大的问题不建议用递归的
而是改成 循环的非递归方式
而是改成 循环的非递归方式
z*y
14 楼
It depends on the optimization option of the compiler. Without optimization,
it may still use stack even without temporary.
【在 s******y 的大作中提到】
: 基础薄弱哈，请勿见笑。
: 最近在上udemy上的C++算法课：https://www.udemy.com/algorithms-bootcamp-in-c/
: 这个老师说尾递归不需要堆栈，并举了求阶乘的两个例子对比：
: int factorial(int n) {
: if (n == 1) return 1;
: return n * factorial(n - 1);
: }
: int factorialAccumulator(int n, int accumulator) {
: if (n == 1) return accumulator;
: return factorialAccumulator(n - 1, n * accumulator);
T*x
15 楼
嗯。这个是对的。
比如现在执行factorial(n=5)，这个n就是临时变量，而且不能马上投入计算，因为要
先算factorial(4)，所以n=5这个值要先存起来。同理算factorial(n=4)时，n=4又要存
起来，这样栈就在增长。
【在 j*****w 的大作中提到】
: 这个：
: int factorial(int n) {
: if (n == 1) return 1;
: m = n * factorial(n - 1);
: return m;
: }
: 用了临时变量。而临时变量是需要栈空间的。所以栈会增长。
比如现在执行factorial(n=5)，这个n就是临时变量，而且不能马上投入计算，因为要
先算factorial(4)，所以n=5这个值要先存起来。同理算factorial(n=4)时，n=4又要存
起来，这样栈就在增长。
【在 j*****w 的大作中提到】
: 这个：
: int factorial(int n) {
: if (n == 1) return 1;
: m = n * factorial(n - 1);
: return m;
: }
: 用了临时变量。而临时变量是需要栈空间的。所以栈会增长。
T*i
16 楼
tail call目前最容易优化的是类似这个
function f(args)
...
return g(args2)
end
比如
function factt(n) return fact_(n, 1) end
function fact_(n, ans) if (n==0) then return ans else return fact_(n-1, n*
ans) end end
function f(args)
...
return g(args2)
end
比如
function factt(n) return fact_(n, 1) end
function fact_(n, ans) if (n==0) then return ans else return fact_(n-1, n*
ans) end end
m*n
17 楼
我记得Python规定堆栈最多不能超过1000层？
好像就是针对你说的这个递归叠递归危险
好像就是针对你说的这个递归叠递归危险
l*m
18 楼
1000是个default的环境变量，你可以改。比如你担心手下用了递归，你把它改到很小
，看看有没有runtime error
【在 m*****n 的大作中提到】
: 我记得Python规定堆栈最多不能超过1000层？
: 好像就是针对你说的这个递归叠递归危险
，看看有没有runtime error
【在 m*****n 的大作中提到】
: 我记得Python规定堆栈最多不能超过1000层？
: 好像就是针对你说的这个递归叠递归危险
r*t
19 楼
python 尾递归没有优化过，GvR 否了。
【在 m*****n 的大作中提到】
: 我记得Python规定堆栈最多不能超过1000层？
: 好像就是针对你说的这个递归叠递归危险
【在 m*****n 的大作中提到】
: 我记得Python规定堆栈最多不能超过1000层？
: 好像就是针对你说的这个递归叠递归危险
相关阅读
tensorflow太扯了meteor能用es6写么？用meteor就不用flux了？Head First Design Pattern写的有问题啊feifei 又有新闻跟你们科班的差太远了能否请推荐个社区系统可以双向同步Slack的?Java 在ML和DL还不错了R竟然没有elseif / elif ?aws大幅度出故障原来是一个程序员输错了命令 (转载)有什么中等规模的项目适合系统学习的？亚特兰大50岁二婚IT失业老中杀妻。公司配的笔记本，如何安全地上黄色网站？ThreadLocal可以这样用吗？Tensorflow's Mandelbrot Set Tutorial谷歌照片翻译那种从图片里识别文字用什么库能做到Angular都出到4.0了？无线键盘鼠标问题Java的经典参考书怎么都很陈旧来，分析下这个垃圾邮件里面的代码python pickle 目的是什么