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()这样就不会用到堆栈了。我死活想不明白怎么就不需要了
。他说得对吗?大牛们能解释一下吗?
多谢!
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 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 基础薄弱哈,请勿见笑。
: 最近在上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 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 基础薄弱哈,请勿见笑。
: 最近在上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 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 他之后又举了例子,说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 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 他之后又举了例子,说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 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 基础薄弱哈,请勿见笑。
: 最近在上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 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 基础薄弱哈,请勿见笑。
: 最近在上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 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 这个:
: 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 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 这个:
: 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 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 基础薄弱哈,请勿见笑。
: 最近在上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 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 基础薄弱哈,请勿见笑。
: 最近在上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 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 基础薄弱哈,请勿见笑。
: 最近在上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*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层?
好像就是针对你说的这个递归叠递归危险
好像就是针对你说的这个递归叠递归危险
相关阅读
关于刷题面试,clojurePostgREST有人生产环境用过没 貌似适合猛糙快CRUDDeep Learning什么框架好动态图怎样买slickedit便宜?有人用react + redux么王垠终于回国了 (转载)百度那个Apollo有人用过吗?学 python3 还是 2.7?Kaggle上有什么和finance/banking相关的比赛比较适合拿来秀的visjs点和线一多就特别慢,有更好的画图库吗block chain科普podcast哪里去找可以快速搭建的论坛?数据世界杯 他们怎么分钱 ?请问,有没有一种算法或者软件可以youtube search by content?文本分析,document_term matrix求解。会用c#/python program MSSql, Excel, 从网上抓数据,合适做啥工作?iterm2 windows alternative华人网讨论做梦梦见未来没有比Visual Studio更好的IDE了吧?