LCM using recursive?

python recursion lcm
ComputerGuy22 picture ComputerGuy22 · Sep 23, 2015 · Viewed 7.4k times · Source

Here is my code: 

def lcm(a, b):
    if b == 0:
        return a
    return a * b / lcm(a, b)

print lcm(5,3)

This is what I could manage so far, any idea on how to find the LCM (least common multiple) of two numbers using recursive and one function?

Answer

tsh picture tsh · Nov 2, 2018

We have lcm(a, b) * gcd(a, b) = a * b. So we can write the following equation:

lcm(a, b) = a; if a % b == 0

lcm(a, b) ; if a % b != 0
= a * b / gcd(a, b)
= a * b / gcd(b, a % b)
= a * b / (b * (a % b) / lcm(b, a % b))
= a / (a % b) * lcm(b, a % b)

And translate to Python, we have:

def lcm(a, b):
  t = a % b
  if t == 0: return a
  return a * lcm(b, t) / t

Related questions

What is the maximum recursion depth in Python, and how to increase it?

I have this tail recursive function here: def recursive_function(n, sum): if n < 1: return sum else: return recursive_function(n-1, sum+n) c = 998 print(recursive_function(c, 0)) It works up to n=997, then it just breaks and spits …

Read More
Python: Maximum recursion depth exceeded

I have the following recursion code, at each node I call sql query to get the nodes belong to the parent node. here is the error: Exception RuntimeError: 'maximum recursion depth exceeded' in <bound method DictCursor.__del__ of <…

Read More
Recursive sub folder search and return files in a list python

I am working on a script to recursively go through subfolders in a mainfolder and build a list off a certain file type. I am having an issue with the script. Its currently set as follows for root, subFolder, files …

Read More