Programa C para encontrar MCM de dos números usando Recursion

Dados dos números enteros N y M , la tarea es encontrar su MCM usando recursividad .

Ejemplos:

Entrada: N = 2, M = 4
Salida: 4
Explicación: MCM de 2, 4 es 4.

Entrada: N = 3, M = 5
Salida: 15
Explicación: MCM de 3, 5 es 15.

Enfoque: La idea es usar el método elemental básico para encontrar el MCM de dos números . Siga los pasos a continuación para resolver el problema:

• Defina una función recursiva LCM() con 3 parámetros enteros N, M y K para encontrar LCM de N y M .
• Deben tenerse en cuenta las siguientes condiciones básicas:
  • Si N o M es igual a 1 , devuelve N * M.
  • Si N es igual a M , devuelve N .
• Si K < min(N, M):
  • Si K divide tanto a N como a M , devuelve K * LCM(N/K, M/K, 2) .
  • De lo contrario, incremente K en 1 y devuelva LCM(N, M, K+1).
• De lo contrario, devuelve el producto de N y M.
• Finalmente, imprima el resultado de la función recursiva como el LCM requerido .

A continuación se muestra la implementación del enfoque anterior:

C

// C program for the above approach    #include <stdio.h>    // 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; }

Producción:

4

Complejidad de tiempo: O(max(N, M))
Espacio auxiliar: O(1)