CODEWITHSUNDEEP
javascriptrecursioncounter
Gage
Gage

Reputation: 71

How to correctly update variables within a recursive function - basic example

I am trying to better my understanding of recursion and in practice i have completed most of the basic recursion problems on https://github.com/JS-Challenges/recursion-prompts/blob/master/src/recursion.js. One thing i can't seem to wrap my head around is incrementing variables within a recursive function. Here is a basic example of a recursive prompt called GCD.

// 14. Find the greatest common divisor (gcd) of two positive numbers. The GCD of two // integers is the greatest integer that divides both x and y with no remainder. // gcd(4,36); // 4

var gcd = function(x, y) { };

here is my code in javascript to tackle the problem

    `var gcd = function(x, y) {
       var counter = 1; 
       var currentGCD = 1; 
       if (x % counter === 0 && y % counter === 0) {
         currentGCD = counter 
         counter++
       } else {
         counter++
       }
       if (counter > x || counter > y) return currentGCD
       return gcd(x,y) 
     };

     console.log(gcd(4,36)); // 4
     console.log(gcd(12,36)); // 12
     console.log(gcd(9,6)) // 3

`

this current code will exceed the maximum call stack limit because counter will never increment past 2. From my understanding, I think it is because for every stack call the variables are being redefined at their first assigned values "counter = 1" and "currentGCD = 1". I know it is possible to create a nested function within GCD and update the counters that way so that the variables are within the GCD scope but out of the recursive scope so they are not constantly being redefined every call. But am i just missing something? Or is that the way to go?

Upvotes: 1

Views: 841

Answers (1)

pintxo
pintxo

Reputation: 2155

If you turn the direction around, starting from the biggest possible divisor (the smaller number) you can do it like this:

function gcd(x, y, nextDivisior) {

  const divisor = nextDivisior || Math.min(x, y);

  if (divisor < 1) {
    return Number.NaN;
  }
  
  if (x % divisor === 0 && y % divisor === 0) {
    return divisor;
  }
  
  return gcd(x, y, divisor - 1);
  
}

console.log(gcd(4,32))
console.log(gcd(9,3))
console.log(gcd(7,11))

Upvotes: 1

Related Questions