>以下のコードは再帰関数を用いてmPnとmCnを計算し出力するプログラムです
>なぜかが分かり
たぶん 再帰の計算の前に、順列と組み合わせの 公式を間違えている気がします。
まず、数学的に正しい事と その実装をどのようにすればいいのかのノウハウの部分がごっちゃになっていると思います。
<公式面>
今の mcn 関数の実装は 単なる 階乗の再帰計算になっています。
3! = 1*2*3 = 6
順列、組み合わせは
https://www.dinop.com/vc/combination.html
に書かれていますが、
nPr = n! / (n-r)!
nCr = nPr / n! なので
n! の 部分を再帰計算するのが単純な回答となります。
n! / (n -r)! が int では オーバーフローするので
階乗計算を展開して
nPr = n * (n - 1) * ... ( n - r + 1)
※ n からはじめて n - r + 1 まで 掛け算
となるのですが、展開してしまうと 再帰の終了判定のために何を渡せば
よいか? 工夫が必要となります。
※ 職業プログラマーは 再帰よりも 単純なループの方が便利。
末尾再帰はループに置き換えるようにアドバイスします。
nCr の 展開は
https://blog.apar.jp/data-analysis/3927/
nCr = ( n から 数を下げながら r 個の掛け算) / (1 から 数を上げながら r 個の掛け算)
で ループの計算に置き換え可能です。
数学的にちゃんと説明ができると、その言語に合わせての実装はそれほど
難しい話ではないと思います。
まさか 順列や 組み合わせは を漸化式に展開して、なおかつ
をれを プログラミングで実装しろという 高度な問題だったと仮定すると
公式
nPr = n! / (n-r)!
より
n を n-1 と すると
(n-1)Pr = (n-1)! / (n-1 - r)! になるので
nPr = (n-1)Pr * n / (n - r)
の漸化式で表現する事が可能
この公式を使って 再帰計算をする事も可能だと思います。
同様に nCr も (n-1)Cr や nC(r-1) を使った漸化式に置き換えて再帰計算する事が可能だと思います。
<実装面>
再帰の終了判定、この場合に 1 を返す。
これ以上繰り返す必要はないので、ここで 値を計算して返す。
という事を どのタイミングで、どのようなパラメータを指定して
関数を設計、関数のパラメータに設定するか? をイメージして
関数を作成してください。
そして、その通りに動作している事を デバッガでステップ実行したり
あらかじめ決められた公式の答えと一致するか? を調査して
問題のある部分を特定してください。
数字として ありえない値を渡した場合に 無限ループにならずに
エラーとして処理を抜けるような工夫も必要です。
1 3
のように2つ目の数字(n
)が大きい場合に Seg fault になりますね。