Redian新闻
>
尾递归不会导致堆栈溢出吗?
avatar
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()这样就不会用到堆栈了。我死活想不明白怎么就不需要了
。他说得对吗?大牛们能解释一下吗?
多谢!
avatar
t*u
3
没有。

【在 N***1 的大作中提到】
: 谢谢!
avatar
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);

avatar
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);

avatar
m*n
6
本版的忙碌大佬都觉得回答人的问题是被占便宜,吼吼~
avatar
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);

avatar
j*w
8
这个:
int factorial(int n) {
if (n == 1) return 1;
m = n * factorial(n - 1);
return m;
}
用了临时变量。而临时变量是需要栈空间的。所以栈会增长。
avatar
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;
: }
: 用了临时变量。而临时变量是需要栈空间的。所以栈会增长。

avatar
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;
: }
: 也会用到临时变量。是否编译器很聪明,觉得这个临时变量用不上就消了?

avatar
s*x
11
即使不用临时变量,也需要把返回地址入栈。所以从理论上来说,所有的递归都有堆栈
溢出的问题,用的局部变量越多,溢出得越快。

【在 j*****w 的大作中提到】
: 这个:
: int factorial(int n) {
: if (n == 1) return 1;
: m = n * factorial(n - 1);
: return m;
: }
: 用了临时变量。而临时变量是需要栈空间的。所以栈会增长。

avatar
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);

avatar
g*u
13
好像 大的问题不建议用递归的
而是改成 循环的非递归方式
avatar
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);

avatar
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;
: }
: 用了临时变量。而临时变量是需要栈空间的。所以栈会增长。

avatar
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
avatar
m*n
17
我记得Python规定堆栈最多不能超过1000层?
好像就是针对你说的这个递归叠递归危险
avatar
l*m
18
1000是个default的环境变量,你可以改。比如你担心手下用了递归,你把它改到很小
,看看有没有runtime error

【在 m*****n 的大作中提到】
: 我记得Python规定堆栈最多不能超过1000层?
: 好像就是针对你说的这个递归叠递归危险

avatar
r*t
19
python 尾递归没有优化过,GvR 否了。

【在 m*****n 的大作中提到】
: 我记得Python规定堆栈最多不能超过1000层?
: 好像就是针对你说的这个递归叠递归危险

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。