0

I am working on finding the greatest common divider of two numbers. I have algorithm as following:

  function gcd(a,b){
    var temp = a;
    if(b > a){
      a = b;
      b = temp;
    }
    var remainder = a % b;
    console.log("remainder: "+ remainder);
    while(remainder){
      a = b;
      b = remainder;
      gcd(a,b);
    }
    return b;
  }

Inside the while loop,directing calling the gcd(a,b) causes the program to crash:

while(remainder){
  a = b;
  b = remainder;
  gcd(a,b);
}

but returning gcd(a,b) instead of calling it works: 

while(remainder){
  a = b;
  b = remainder;
  return gcd(a,b);
}

I don't understand the differences. Why doesn't the first case stops when it reaches base case as remainder -> 0 ?

ZhouBing Yang
  • 105
  • 5
  • 1
    Have you tried to step through that code with a [debugger](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems)? – litelite Nov 08 '17 at 19:29
  • 2
    You never change the remainder in your loop. – litelite Nov 08 '17 at 19:29
  • @litelite: I think OP is unaware that each `remainder` variable is a different instance. Also how recursion works in general. – Mooing Duck Nov 08 '17 at 19:30
  • 1
    because `remainder` never changes – anteAdamovic Nov 08 '17 at 19:31
  • @MooingDuck Seems like the most probable explanation. Which is why i proposed the debugger. – litelite Nov 08 '17 at 19:31
  • @litelite the remainder certainly changed with every iteration since I reassigned a = b and b = remainder? My problem is why returning gcd() work but calling gcd() instead does not? – ZhouBing Yang Nov 08 '17 at 19:53
  • Try to step through the code with a debugger, you will be surprised. Recursion does not work like you think it does. – litelite Nov 08 '17 at 19:58
  • Calling gcd(a,b) without using its result seems pointless. What does this call do? – n. 1.8e9-where's-my-share m. Nov 08 '17 at 20:34
  • calling gcd(a,b) because I want to reduce the function into base case which is when remainder == 0 that is when function return a value correct? @n.m. – ZhouBing Yang Nov 08 '17 at 21:53
  • I think I figure out the problem now. The way I execute program with directly calling gcd() in the while loop never gets me out of the while loop instead it keeps creating more instants of gcd(). – ZhouBing Yang Nov 08 '17 at 22:38
  • A function returns a value. It doesn't do anything else (nothing that can be observed from the outside at any rate). Calling a function without using its return value is a no-op and doesn't accomplish anything, including "reduce the function into base case" (whatever that means). – n. 1.8e9-where's-my-share m. Nov 08 '17 at 22:52

0 Answers0