Open in App
Not now

# C Program to find LCM of two numbers using Recursion

• Difficulty Level : Hard
• Last Updated : 15 Dec, 2020

Given two integers N and M, the task is to find their LCM using recursion.

Examples:

Input: N = 2, M = 4
Output: 4
Explanation: LCM of 2, 4 is 4.

Input: N = 3, M = 5
Output: 15
Explanation: LCM of 3, 5 is 15.

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach: The idea is to use the basic elementary method of finding LCM of two numbers. Follow the steps below to solve the problem:

• Define a recursive function LCM() with 3 integer parameters N, M, and K to find LCM of N and M.
• The following base conditions need to be considered:
• If N or M is equal to 1, return N * M.
• If N is equal to M, return N.
• If K < min(N, M):
• If K divides both N and M, return K * LCM(N/K, M/K, 2).
• Otherwise, increment K by 1 and return LCM(N, M, K+1).
• Otherwise, return the product of N and M.
• Finally, print the result of the recursive function as the required LCM.
• Below is the implementation of the above approach:

## C

 `// C program for the above approach ` ` `  `#include ` ` `  `// Function to return the ` `// minimum of two numbers ` `int` `Min(``int` `Num1, ``int` `Num2) ` `{ ` `    ``return` `Num1 >= Num2 ` `               ``? Num2 ` `               ``: Num1; ` `} ` ` `  `// Utility function to calculate LCM ` `// of two numbers using recursion ` `int` `LCMUtil(``int` `Num1, ``int` `Num2, ``int` `K) ` `{ ` `    ``// If either of the two numbers ` `    ``// is 1, return their product ` `    ``if` `(Num1 == 1 || Num2 == 1) ` `        ``return` `Num1 * Num2; ` ` `  `    ``// If both the numbers are equal ` `    ``if` `(Num1 == Num2) ` `        ``return` `Num1; ` ` `  `    ``// If K is smaller than the ` `    ``// minimum of the two numbers ` `    ``if` `(K <= Min(Num1, Num2)) { ` ` `  `        ``// Checks if both numbers are ` `        ``// divisible by K or not ` `        ``if` `(Num1 % K == 0 && Num2 % K == 0) { ` ` `  `            ``// Recursively call LCM() function ` `            ``return` `K * LCMUtil( ` `                           ``Num1 / K, Num2 / K, 2); ` `        ``} ` ` `  `        ``// Otherwise ` `        ``else` `            ``return` `LCMUtil(Num1, Num2, K + 1); ` `    ``} ` ` `  `    ``// If K exceeds minimum ` `    ``else` `        ``return` `Num1 * Num2; ` `} ` ` `  `// Function to calculate LCM ` `// of two numbers ` `void` `LCM(``int` `N, ``int` `M) ` `{ ` `    ``// Stores LCM of two number ` `    ``int` `lcm = LCMUtil(N, M, 2); ` ` `  `    ``// Print LCM ` `    ``printf``(``"%d"``, lcm); ` `} ` ` `  `// Driver Code ` `int` `main() ` `{ ` `    ``// Given N & M ` `    ``int` `N = 2, M = 4; ` ` `  `    ``// Function Call ` `    ``LCM(N, M); ` ` `  `    ``return` `0; ` `}`

Output:

```4
```

Time Complexity: O(max(N, M))
Auxiliary Space: O(1)

My Personal Notes arrow_drop_up
Related Articles
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://origin.geeksforgeeks.org/c-program-to-find-lcm-of-two-numbers-using-recursion/", "fetch_time": 1675946130000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2023-06/segments/1674764499966.43/warc/CC-MAIN-20230209112510-20230209142510-00232.warc.gz", "warc_record_offset": 459021469, "warc_record_length": 30205, "token_count": 1033, "char_count": 2941, "score": 3.640625, "int_score": 4, "crawl": "CC-MAIN-2023-06", "snapshot_type": "latest", "language": "en", "language_score": 0.7242922186851501, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00058-of-00064.parquet"}