

以下のコードは再帰関数を用いてmPnとmCnを計算し出力するプログラムです

Segmentation faultの箇所はコード4行目のn==m-nであることは分かっていますがなぜかが分かりません。どうすればプログラムを動かせますか？

[code]

    #include <stdio.h>
    
    int mpn(int m, int n){
      if(n==m-n){
        return 1;
      }
      return m*mpn(m-1, n);
    }
    
    int mcn(int n){
      if(n==1){
        return 1;
      }
      return n*mcn(n-1);
    } 
    
    int main(){
      int m, n, d;
      printf("input m and n:");
      scanf("%d %d", &m, &n);
      d=mpn(m, n);
      printf("%dP%d = %d\n", m, n, d);
      d=d/mcn(n);
      printf("%dC%d = %d\n", m, n, d);
      return 0;
    }
    
[/code]


CC BY-SA 4.0
2019-11-08T05:05:27.300
60351
2019-11-09T07:14:48.793
2019-11-08T05:18:28.517
3060
35091
question
c
再帰関数を学んでいます。Segmentation fault の理由


処理系によっては `Segmentation fault` 表示になるでしょうし  
処理系によっては `Stack Overflow` 表示になるでしょう

要するに再帰の終了条件が誤っていて無限再帰しているだけです。今のコードは Permutation / Combination
の定義通りに実装されていませんよね。そこを直すだけ。

# 定義式通りに実装すると大きい数値を与えると即オーバーフローするので実用的にするには工夫が必要


CC BY-SA 4.0
2019-11-08T05:33:41.847
60353
2019-11-08T05:33:41.847
8589
60351
answer


> 1 3 のように2つ目の数字(n)が大きい場合に Seg fault
[code]

      if(n==m-n){
    　　return 1;
    　}
      #mをデクリメントしていって、n==m-n を満たすには、m>2n の条件が暗黙
    　#じゃないですか？
      return m*mpn(m-1, n);
    
[/code]


CC BY-SA 4.0
2019-11-08T22:58:23.503
60363
2019-11-08T22:58:23.503
10174
60351
answer


＞以下のコードは再帰関数を用いて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 を返す。  
これ以上繰り返す必要はないので、ここで 値を計算して返す。  
という事を どのタイミングで、どのようなパラメータを指定して  
関数を設計、関数のパラメータに設定するか？ をイメージして  
関数を作成してください。  
そして、その通りに動作している事を デバッガでステップ実行したり  
あらかじめ決められた公式の答えと一致するか？ を調査して  
問題のある部分を特定してください。  
数字として ありえない値を渡した場合に 無限ループにならずに  
エラーとして処理を抜けるような工夫も必要です。


CC BY-SA 4.0
2019-11-09T07:14:48.793
60367
2019-11-09T07:14:48.793
18851
60351
answer