Рекурсивное решение для биномиального коэффициента в C

Question

Почему мое решение биномиального коэффициента падает? Я действительно пытался научиться рекурсии, но я все еще думаю, что я не совсем понимаю об этом. Интересно, может ли кто-нибудь помочь мне узнать о рекурсии и как думать рекурсивно?

Даже когда я пишу хороший базовый чехол, моя программа вылетает. Любая ссылка для изучения рекурсии с четкой демонстрацией была бы очень полезной для меня.

Вот мой код для биномиального коэффициента, и я не могу найти ошибку/ошибку, ища вашу помощь.

Код:

#include<stdio.h> 

long long m,n,o,p,result; 

long long binomial(long long n,long long m) 
{ 
    if(n==m) 
     return 1; 
    else { 
     if(m==0) 
      return 1; 
     else { 
      o=binomial(n-1,m); 
      p=binomial(n-1,m-1); 
      return o+p; 
     } 
    } 
} 

int main() 
{ 
    printf("Please Enter The Value Of n:\n"); 
    scanf("%lld",&n); 

    printf("Now Enter The value of m:\n");  
    scanf("%lld",&m); 

    result = binomial(n,m); 
    printf("Resultant Binomial coefficient: %lld\n",result); 
    return 0; 
} 

Answer 1

Биномиальная коэффициент определен только для пар п и к при п> = к. Обычным является использование n и k в выражениях биномиального коэффициента, но они соответствуют n и m в вашем коде.

Чтобы избежать проблем, вам необходимо включить проверку ошибок ввода. Ваш код падает, когда n меньше m, потому что каждый раз, когда оператор o=binomial(n-1,m); выполняется, значение n в вызываемой функции снижается, но n уже меньше m, которая отлична от нуля (если m были равны нулю функция будет иметь просто 1), поэтому n == m никогда не может произойти.

Кстати, вы можете улучшить свой код несколькими способами. Использование глобальных переменных, как правило, плохая идея, и было бы лучше, чтобы переместить декларацию:

long long m, n, result; 

в main(), где нужны эти переменные. Кроме того, подпись функции для main() должна быть int main(void). И вы можете подтянуть логику в функции binomial() значительно, устраняя необходимость в o и p:

long long binomial(long long n,long long m) 
{ 
    if (m != 0 && n != m) { 
     return binomial(n-1, m) + binomial(n-1, m-1); 
    } else { 
     return 1; 
    } 
}