0

I am trying to write a code to calculate GCD of two numbers(n and m) recursively. I want my answer to update in gcd_val as the recursion progresses. I tried debugging and can't understand why it chooses the earlier gcd_val as compared to the value obtained in its sub-call(inner recursive call). I want to know why is this happening and what should be the correct way to do it? I get the answer 2 when it should be 4.

def find_gcd(n, m, gcd_val):
factor_list = [2, 3, 5]
if n == 0 or m == 0:
    return 0
for f in factor_list:
    if n % f == 0 and m % f == 0:
        find_gcd(int(n/f), int(m/f), gcd_val)
        gcd_val *= f
return gcd_val

print(find_gcd(20, 8, 1))
null_override
  • 467
  • 3
  • 10
  • 30
Nupur95
  • 1
  • 2
  • 2
    I don't know what language this is but it doesn't appear you do anything with the value returned by the recursive call in the loop. What I mean is that you call `find_gcd(int(n/f), int(m/f), gcd_val)` within the function but its return value is not what you apply the multiplication assignment to. You apply the multiplication assignment (`*=`) to the `gcd_val` argument that was originally passed into the function. You need to multiply-assign the value returned by the recursive call and return that from the function. – trndjc Sep 25 '20 at 23:27

1 Answers1

0

Almost all programming languages defaults to pass arguments by value. That is the second the function starts up the arguments are unique memory locations for just that round and all alterations done with it will never affect a prevous call even if it is the same name.

Programming languages doesn't discriminate between self calling or caling something else so when find_gcd calls find_gcd it treats it the same as if it called find_gcd2 with a similar implementation.

Just like you use print you actually need to use the returned value or else the recursive call in find_gcd is dead code.

Sylwester
  • 47,942
  • 4
  • 47
  • 79