作者anoymouse (没有昵称)
看板C_and_CPP
标题[问题] leetcode POW(n,x) stack overflow
时间Wed Sep 30 10:48:40 2020
平台: Leetcode in C
Implement pow(x, n), which calculates x raised to the power n (i.e. xn).
在case myPow(0.00001,2147483647) 出现stack overflow的情况，
其实第二个参数不到INT_MAX就会overflow了。 请问是不是递回太深的缘故，要怎麽保证不会overflow?
谢谢
double myPow(double x, int n){
double output;
if(n>0)
{
if(n == 1 )
return x;
else
{
output = x*myPow(x,n-1);
}
}
else if(n == 0 )
return 1;
else
{
if(n == -1)
return 1/x;
else
output = (1/x)*myPow(x,n+1);
}
return output;
}
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 61.230.161.136 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1601434122.A.85E.html
※ 编辑: anoymouse (61.230.161.136 台湾), 09/30/2020 10:51:23
1F：推 xiefengan: Google 快速幂 09/30 12:19
正在看 还在消化中 也许可以避免stack overflow。
2F：→ s90104123: INT_MAX看看？ 09/30 16:36
3F：推 yangerma: 你这边提到了两种overflow，我还不确定你是不是把两种搞 09/30 19:25
4F：→ yangerma: 混了。 09/30 19:26
5F：→ yangerma: "stack overflow"就像你说的可能是递回过深的关系，至於 09/30 19:26
6F：→ yangerma: 多深叫过深跟runtime的系统设定、还有你的递回函数会吃 09/30 19:26
7F：→ yangerma: 多少记忆体有关。至於递回为什麽不能过深，跟递回在执行 09/30 19:26
8F：→ yangerma: 时是如何做到的有关，不知道的话值得去了解一下。 09/30 19:26
9F：→ yangerma: 另外你提到的跟INT_MAX有关的是整数的overflow，因为C语 09/30 19:26
10F：→ yangerma: 言里int只能表达某个大小范围内的整数，如果在拿int运算 09/30 19:26
11F：→ yangerma: 的过程中超过那个范围，导致运算的结果不如预期。 09/30 19:26
12F：→ yangerma: 以上两种overflow完全是两回事，而这份程式码看起来很可 09/30 19:26
13F：→ yangerma: 能是发生了第一种(stack overflow)。你可以数数看这个程 09/30 19:26
14F：→ yangerma: 式应该会递回几层，以後就会知道这样的深度是会导致stac 09/30 19:26
15F：→ yangerma: k overflow的。 09/30 19:26
16F：→ yangerma: 至於解决方法，最简单的就是不要用递回ww 09/30 19:26
我这边纯粹在指stack overflow，会提到INT_MAX只是因为leetcode把第二个参数设成
INT_MAX，当然如果最终回传直>INT_MAX可能也有问题，但目前主要是想先处理
stack overflow。
17F：推 alan23273850: 能用回圈就不要用递回 09/30 19:51
18F：→ WPC001: 你这个为什麽一定要用递回? 09/30 22:58
是没有一定要用递回 我一开始也是想用回圈，但是我想看看别人是怎麽做的
发现该题的讨论区通通都是用递回，就想说试试看递回。
※ 编辑: anoymouse (36.227.161.96 台湾), 10/02/2020 12:05:12
19F：推 kingofsdtw: 别用recursive看看? recursive考试用而已 10/06 18:31
20F：→ kingofsdtw: 现实上一堆会变成地雷 10/06 18:31