Learning recursive functions.Segmentation fault reason

The code below is a program that calculates and outputs mPn and mCn using recursive functions

I know that the segmentation fault is n==m-n in line 4, but I don't know why.How can I run the program?

#include<stdio.h>

int mpn(int m, int n){
  if(n==m-n){
    return1;
  }
  return m*mpn(m-1,n);
}

int mcn(int n){
  if(n==1){
    return1;
  }
  return n*mcn(n-1);
} 

int main() {
  int m, n, d;
  printf("input man:");
  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;
}

2022-09-30 18:08

3 Answers

Depending on the processing system, Segmentation fault will be displayed.
Depending on the processing system, you will see Stack Overflow

In short, the end conditions for recursion are incorrect and only infinite recursion.The current code is not implemented as defined in Permutation/Combination.Just fix it.

# If implemented according to the definition formula, it will overflow immediately if a large number is given, so it needs to be devised to make it practical

2022-09-30 18:08

Seg fault

if the second number (n) is large, such as 13

 if(n==m-n){
　　return1;
　}
  A condition of m>2n is implicit to decrement #m and satisfy n==m-n
　# Isn't it?
  return m*mpn(m-1,n);

2022-09-30 18:08

>The code below is a program that calculates and outputs mPn and mCn using a recursive function. >Now I know why

I think the permutation and combination formula are probably wrong before the recursive calculation.

First of all, I think the mathematical correctness and know-how about how to implement it are mixed up.

The current implementation of the mcn function is simply a factorial recursive calculation.
3!=1*2*3=6

permutation, combination
https://www.dinop.com/vc/combination.html

As it is written in ,

nPr=n!/(n-r)!

nCr=nPr/n! So

The simple answer is to recursively calculate the n! part.

n!/(n-r)! overflows with int, so

Expand the multiplier calculation

nPr=n*(n-1)*...(n-r+1)
※ Multiply n to n-r+1

However, if you expand it, what should you give to determine the end of the recursive process?
Okay? You need to think about it.
※ A simple loop is more convenient for professional programmers than a reflexive one.
　 We advise you to replace the trailing recursive with a loop.

nCr deployment is
https://blog.apar.jp/data-analysis/3927/

nCr = (multiplication of r while decreasing the number from n) / (multiplication of r while increasing the number from 1)

can be replaced by loop calculations.

If you can explain it mathematically, the implementation of
in that language is not that good. I don't think it's difficult.

No way, permutations and combinations are developed in an incremental way, and
Assuming it was a sophisticated issue of programming,

Official
nPr=n!/(n-r)!
More

If n is n-1,

(n-1)Pr=(n-1)!/(n-1-r)!, so

nPr=(n-1)Pr*n/(n-r)

Can be expressed in the incremental formula of

I think it is possible to perform recursive calculations using this formula.

Similarly, I think it is possible to replace nCr with an incremental formula using (n-1)Cr and nC(r-1), and perform recursive calculations.

　Recursive termination determination, in which case 1 is returned.
　You don't need to repeat it any more, so calculate and return the value here.
　So, when and what parameters do you specify?
　Do you want to design a function as a function parameter?
Imagining 　Create a function.
　Then, you can perform step-by-step operations in the debugger.
　Does it match a predetermined formula answer? by investigating
　Determine which part of the problem is present.
　If you pass a value that cannot be a number, it will not go into an infinite loop
　It is also necessary to devise ways to get out of the way as an error.

2022-09-30 18:08

If you have any answers or tips

Popular Tags

python x 4647

android x 1593

java x 1494

javascript x 1427

c x 927

c++ x 878

ruby-on-rails x 696

php x 692

python3 x 685

html x 656