Recursive call getting stuck

Question

 #include <bits/stdc++.h>
 using namespace std;
 int gcd(long long int a, long long int b){
      if(a||b==0){
           return 0;
      }
      else if(b==a){
           return a;
      }
      else if(a>b){
           return gcd(a-b,b);
      }
      else{
           return gcd(a,b-a);
      }
 }
 int lcm(long long int a,long long int b){
      return a*b/(gcd(a,b));
 }
 int main(){
      long long int answer=1;
      for (int i = 2; i<=20; i++) {
      answer=lcm(i,answer);
      cout<<answer;
      }
      cout<<answer;
      return 0;
 }

i wrote this code for problem 5 in project euler. however the output screen is showing nothing and is getting hanged. i put a few debugging cout statements and i understood that in the main function the it is entering the loop but it is not continuing the excution after the call for lcm.

the program is to find the lcm of numbers from 1 to 20. i used the formula llcm= a*b/gcd(a,b). where in gcd also i used the recursive euclidian algorithm. i am not able to trace out the reason for this bug . could anyone help pls.

also if there any suggestions regarding my coding style (indentation, type casting, variable names, algorithm or anything) please point it out. i am beginner so i do not know much regarding c++ and programming styles.

First I would use capitals to start sentences. Your indentation skills can also use a refresh. As for style, anything that you need to revisit later better be clear enough for your own sake, and possibly others. — StarShine, Jan 26 '18 at 23:05
Recommended reading: [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) and [Why is “using namespace std” considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice). Now that you've read those, think on what can happen if you include the tens of thousands of identifiers in the standard library and place them all into the global namespace with your code. — user4581301, Jan 26 '18 at 23:13
These are more coding process than style: 1: Don't ignore compiler warnings. Compiler errors mean your code cannot be turned into a program, but compiler warnings mean you can get a program, but it may not do what you want it to do. I turn on `-pedantic`, `-Wall`, and `-Wextra` to get more warnings. 2. Familiarize yourself with the use of whatever debugging tools come with your development environment. Tools like GDB and Valgrind (look them up) will make short work of most of the logic errors you're likely to make while learning. The time-savings using debuggers brings are enormous. — user4581301, Jan 26 '18 at 23:30

score 4 · Accepted Answer · answered Jan 26 '18 at 23:07

Your program is becoming stuck because of this line:

if (a || b == 0) {

The == operator has higher precedence than ||, so the condition is in fact the same as:

if (a || (b == 0)) {

Which in C(++) is the same as:

if ((a != 0) || (b == 0)) {

That is, if a is non-zero OR b is zero. a will be non-zero straight away, hence your program will always try to divide by zero, which causes problems. I am not sure where you found this version of the algorithm, a cursory search results in a much simpler variant:

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

As for the second part of your question, there are many little (stylistic) issues in your code that I would change. Inconsistent spacing, unnecessary use of long long int (an int would do just fine here) … But for these, I recommend the codereview StackExchange.

Recursive call getting stuck

1 Answers1