[理工] [資結]binomial coefficient遞迴的小疑問

[shownlin (哈哈阿喔)]

一個小問題
因為大部分的答案好像都這樣寫

int binomialCoeff(int n, int k)
{
  // Base Cases
  if (k==0 || k==n)
    return 1;
  return  binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);
}

想請問是不是資料結構中的答案都不用考慮結果為0的initial conditions？

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.217.23.14
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1492569675.A.C24.html
→ outofyou: 結果為0是什麼意思？
恩…就是當n<k或n==0的時候應該是return 0?
※ 編輯: shownlin (49.217.23.14), 04/19/2017 10:55:48
推 outofyou: 課本上的extended binomial定義結果必不為0,k必不為負
→ shownlin: 原來如此，非常感謝
→ outofyou: 我錯了
→ outofyou: n==0或n<k還是應該return0
→ outofyou: 範例答案輸入若符合n>=k且k>=0，確實不需多考慮起始條件
→ outofyou: 範例答案會缺漏起始條件是在n<k時，無窮迴圈。
→ outofyou: 建議起始條件為if(k==0)return 1;else if(n<k)return 0;
→ outofyou: 可注意的是雖然n<k,C(-1,0)=1而不是=0 by definition
→ outofyou: 有錯，請看回文