Least Common multiple python

[minko]

Hello, so i have to convert non recursion code to recursion for least common multiple, i have a non recursion code here:

def lcm(x, y):

   if x > y:
       greater = x
   else:
       greater = y

   while True:
       if((greater % x == 0) and (greater % y == 0)):
           lcm = greater
           break
       greater += 1

   return lcm

num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))

So in this i need to use 2 if's but im not sure how i can put it in recursion.

[deanhystad]

The recursion replaces the while loop. What is the loop doing?

   while True:
       if((greater % x == 0) and (greater % y == 0)):
           lcm = greater
           break
       greater += 1

The loop does greater += 1, so your recursive function will have to do that. How are you going to increment the value of greater each time you recursively call the function?

       if((greater % x == 0) and (greater % y == 0)):
           lcm = greater
           break

The loop ends if greater is evenly divisible by x and y. When the loop ends it assigns lcm the value of greater.

The function returns lcm, that is also going to be the value retuned by your recursive function.

The hardest part by far is how are you going set the value for greater.

def lcm(x, y):
 
   if x > y:
       greater = x
   else:
       greater = y
 
   while True:
       greater += 1

greater is initialized to x or y depending on what is greater, but subsequent uses of greater increment the current value by 1. How do you do that?

[DPaul]

Are we in agreement what the least common multiple should be?
For 3 and 12, that is 24.
The code in post #1 says 12.

Maybe it's a language thing?

Paul

[deanhystad]

The answer should be 12. 12 x 1 = 12, 3 x 4 = 12. There is no smaller number divisible by 12 and 3.

[DPaul]

The answer should be 12. 12 x 1 = 12, 3 x 4 = 12. There is no smaller number divisible by 12 and 3.

OK, got it wrong, 12 is considered a multiple of itself.
Paul

[jefsummers]

One notes limitations of recursion - I used the method above with a recursive routine and tried some numbers. 48 and 49 gave a recursion error - too many levels. 17 and 49 worked fine. The limit is somewhere in between.

So, the assignment is to teach you recursion techniques, but in this application a loop is more effective - less limitations. Best recursion example I have seen or used is the Towers of Hanoi puzzle. But that one is harder, good for extra credit!