s******y
发帖数: 172 | 1 基础薄弱哈，请勿见笑。
最近在上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()这样就不会用到堆栈了。我死活想不明白怎么就不需要了
。他说得对吗？大牛们能解释一下吗？
多谢！ |
s******y
发帖数: 172 | 2 他之后又举了例子，说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);
|
r****t
发帖数: 10904 | 3 如果返回值直接被返回的话，编译器能把这一层调用给优化掉。
【在 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
发帖数: 3575 | 4 本版的忙碌大佬都觉得回答人的问题是被占便宜，吼吼～ |
T*******x
发帖数: 8565 | 5 我觉得是编译器优化的问题，这两种写法的最显著区别是，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
发帖数: 1 | 6 这个：
int factorial(int n) {
if (n == 1) return 1;
m = n * factorial(n - 1);
return m;
}
用了临时变量。而临时变量是需要栈空间的。所以栈会增长。 |
s******y
发帖数: 172 | 7 可如果写成：
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
发帖数: 1 | 8 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****x
发帖数: 22 | 9 即使不用临时变量，也需要把返回地址入栈。所以从理论上来说，所有的递归都有堆栈
溢出的问题，用的局部变量越多，溢出得越快。
【在 j*****w 的大作中提到】
: 这个：
: int factorial(int n) {
: if (n == 1) return 1;
: m = n * factorial(n - 1);
: return m;
: }
: 用了临时变量。而临时变量是需要栈空间的。所以栈会增长。
|
n*****3
发帖数: 1584 | 10 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);
|
|
|
g*******u
发帖数: 3948 | 11 好像 大的问题不建议用递归的
而是改成 循环的非递归方式 |
z*y
发帖数: 1311 | 12
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
发帖数: 8565 | 13 嗯。这个是对的。
比如现在执行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
发帖数: 2416 | 14 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 |
m*****n
发帖数: 3575 | 15 我记得Python规定堆栈最多不能超过1000层？
好像就是针对你说的这个递归叠递归危险 |
l*******m
发帖数: 1096 | 16 1000是个default的环境变量，你可以改。比如你担心手下用了递归，你把它改到很小
，看看有没有runtime error
【在 m*****n 的大作中提到】
: 我记得Python规定堆栈最多不能超过1000层？
: 好像就是针对你说的这个递归叠递归危险
|
r****t
发帖数: 10904 | 17 python 尾递归没有优化过，GvR 否了。
【在 m*****n 的大作中提到】
: 我记得Python规定堆栈最多不能超过1000层？
: 好像就是针对你说的这个递归叠递归危险
|
