C Рекурсивная функция - GCD

Question

Я начал изучать C и программирование в целом относительно недавно, и нам сказали сделать программу, которая находит GCD и LCM из двух чисел, используя рекурсию.

Теперь после некоторого измельчения мне удалось собрать это вместе.

#include<stdio.h> 

int gcd(int a,int b); 

int main() 
{ 
    int a,b,l,temp; 
    printf("Enter two numbers :\n"); 
    scanf("%d%d",&a,&b); 
    if(a<b) 
    { 
     temp=a; 
     a=b; 
     b=temp; 
    } 
    l=gcd(a,b); 
    printf("GCD = %i\nLCM = %i",l,a*b/l); 

    return 0; 
} 

int gcd(int a,int b) 
{ 
    static int c; 
    c=a%b; 
    a=b; 
    b=c; 
    if(c!=0) 
    { 
     gcd(a,b); 
    } 
    else 
     return a; 
} 

Теперь по какой-то причине неизвестно, функция не работает без «else». В частности, вот так:

int gcd(int a,int b) 
{ 
    static int c; 
    c=a%b; 
    a=b; 
    b=c; 
    if(c!=0) 
    { 
     gcd(a,b); 
    } 
     return a; 
} 

Несмотря на то, что я не отношусь к заданию, мне кажется, что я должен понять, в чем проблема. Будучи новичком, я был бы признателен за любую помощь.

Приносим извинения, если вопрос слишком глупый или код слишком грязный.

Answer 1

Проблема является рекурсивный вызов:

int gcd(int a,int b) 
{ 
    static int c; 
    c=a%b; 
    a=b; 
    b=c; 
    if(c!=0) 
    { 
     gcd(a,b); // The problem is here 
    } 
    else 
     return a; 
} 

Вы сделали два различных подхода:

1. В вышеописанном случае вы не оператор возврата, если c!=0. Ваша функция имеет для возврата int. Обычно компиляторы дают вам предупреждение, потому что вы вернете своеобразное случайное число see here. Итак, скажем, удача в том, что ваша функция с другим работает.
2. Без справки else вы будете всегда возвращение a. Вы вычисляете gcd, но вы никогда не будете использовать результат, поэтому ваш результат первого вызова всегда будет меньшим числом между a и b вашего основного. Вы должны использовать результат своего рекурсивного вызова, чтобы заставить функцию работать.

Правильный подход, чтобы вернуть результат рекурсивного вызова, как Санджай-Софо уже сказал:

return gcd(a,b); 

Кроме того, это плохой стиль кодирования использовать скобки на если и не брекеты на ELSE ;) Оба случая прекрасны, но сохраняют их одинаковыми.

Answer 2

Вы задали вопрос о проблемах в своем коде. Здесь

static int c; 

Почему это статично, Кроме того, для вычисления gcd с использованием рекурсии вам не нужна третья переменная. И

gcd(a,b); 

В какой переменной вы возвращение НОД. Это не имеет никакого смысла. Это не функция void, она возвращает int.

Теперь правильный метод,

if (b != 0) 
    return gcd(b, a%b); 
    else 
    return a; 

Вот так.