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层？
: 好像就是针对你说的这个递归叠递归危险
相关阅读
请问哪位用过那种跪着座的Kneeing chair (转载)Re: beg: 难题：也是关于内存的问题Is there a way to track streaming audio/video?XSL question两把门锁的问题how to look the values in a vector in VC.NETJava banned operator overloadingJAVA generic programming 是怎么实现的？内存泄漏怎么查？为什么需要定义 = 和 copy ctorstatic function and static variable？global variable usage question in C++在php中,怎样转换date format?pointer to override function?奇怪的C Programming on Linux问题can't understand this function definitioncvs configurationGoogle™ Code JamComments about OOM killer, for fun only :)a c++ question