[問題] leetcode POW(n,x) stack overflow

[anoymouse (沒有暱稱)]

平台: 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://www.ptt.cc/bbs/C_and_CPP/M.1601434122.A.85E.html
※ 編輯: anoymouse (61.230.161.136 臺灣), 09/30/2020 10:51:23
推 xiefengan: Google 快速冪
正在看 還在消化中  也許可以避免stack overflow。
→ s90104123: INT_MAX看看？
推 yangerma: 你這邊提到了兩種overflow，我還不確定你是不是把兩種搞
→ yangerma: 混了。
→ yangerma: "stack overflow"就像你說的可能是遞迴過深的關係，至於
→ yangerma: 多深叫過深跟runtime的系統設定、還有你的遞迴函數會吃
→ yangerma: 多少記憶體有關。至於遞迴為什麼不能過深，跟遞迴在執行
→ yangerma: 時是如何做到的有關，不知道的話值得去了解一下。
→ yangerma: 另外你提到的跟INT_MAX有關的是整數的overflow，因為C語
→ yangerma: 言裡int只能表達某個大小範圍內的整數，如果在拿int運算
→ yangerma: 的過程中超過那個範圍，導致運算的結果不如預期。
→ yangerma: 以上兩種overflow完全是兩回事，而這份程式碼看起來很可
→ yangerma: 能是發生了第一種(stack overflow)。你可以數數看這個程
→ yangerma: 式應該會遞迴幾層，以後就會知道這樣的深度是會導致stac
→ yangerma: k overflow的。
→ yangerma: 至於解決方法，最簡單的就是不要用遞迴ww
我這邊純粹在指stack overflow，會提到INT_MAX只是因為leetcode把第二個參數設成
INT_MAX，當然如果最終回傳直>INT_MAX可能也有問題，但目前主要是想先處理
stack overflow。
推 alan23273850: 能用迴圈就不要用遞迴
→ WPC001: 你這個為什麼一定要用遞迴?
是沒有一定要用遞迴 我一開始也是想用迴圈，但是我想看看別人是怎麼做的
發現該題的討論區通通都是用遞迴，就想說試試看遞迴。
※ 編輯: anoymouse (36.227.161.96 臺灣), 10/02/2020 12:05:12
推 kingofsdtw: 別用recursive看看? recursive考試用而已
→ kingofsdtw: 現實上一堆會變成地雷