Looking for explanation of Greatest Common Divisor Recursive Function-CodePudding

I'm studying recursive functions, and one I came across is the greatest common divisor. I was working through a very long and complicated piece of code that was going nowhere, and when I looked up the solution, I see it's super short:

function gcd(num1, num2) { 
   if (num2 === 0) { 
  return num1;
}

  return gcd (num2, num1 % num2);
}

I'm struggling to wrap my brain around how this works in the recursive return function call. Num2 becomes the first parameter for some reason, and how does the second parameter work? Is num1 % num2 the new value of num1? How is num2 going to get to 0? I don't see how it's value changes.

CodePudding user response：

It might be tricky to understand without going through examples with pen and paper. num1 % num2 becomes the new value of num1 for each recurring call of the function.

If you try it with gcd(14,4),

4 != 0, 14 % 4 = 2 then next call is gcd(4, 2).

2 != 0, 4 % 2 = 0 then next call is gcd(2, 0).

0 == 0 then greatest common divisor of 14 and 4 is 2. This value is returned all the way up the call stack.

Another example with gcd(5,3):

3 != 0, 5 % 3 = 1 then next call is gcd(3,1).

1 != 0, 3 % 1 = 0 then next call is gcd(1, 0).

0 == 0 then greatest common divisor of 5 and 3 is 1.

CodePudding user response：

An exact equivalent but more clear (to me) code is:

function gcd(num1, num2) { 
  if (num2 === 0) return num1;
  else return gcd (num2, num1 % num2);
}

Now do a few by hand:

console.log(gcd(15, 6));
num2 (6) is not 0 so return gcd(6, 15%6) or gcd(6,3)
num2 (3) is not 0 so return gcd(3, 6%3) or gcd(3,0)
num2 (0) is now 0 so return 3

console.log(gcd(6, 15));
num2 (15) is not 0 so return gcd(15, 6) or gcd(15,6)
num2 (6) is not 0 so return gcd(6, 15%6) or gcd(6,3)
num2 (3) is not 0 so return gcd(3, 6%3) or gcd(3,0)
num2 (0) is now 0 so return 3

Or, you can let the code tell you what's going on:
This is for factorial(n) but you could do the same for gcd():
The important point is that "k" is different for each call:

console.log("FINALLY, factorial(5) = ", factorial(5));

function FACTORIAL(num) { // this is without the BS
  if (num == 1) return 1;
  else return num * factorial(num-1);
}
function factorial(num) { // this shows all
  console.log("getting factorial("   num   ")");
  if (num == 1) {
    console.log("factorial of 1 is just 1");
    return 1;
  } else {
    console.log("need to get factorial("   (num-1)   ")");
    let k = num * factorial(num - 1);
    console.log("got factorial("   num   ") = "   k);
    return k;
  }
}