[C] Calcolare minimo comune multiplo con ricorsione

[floppyes]

Ciao a tutti!

Non riesco a capire come calcolare il minimo comune multiplo utilizzando la ricorsione.

Ho provato a scriver un pezzetto di codice però non ho utilizzato la ricorsione ma una semplice funzione in C. Quello che non riesco a fare è trasformare questo codice in una funzione ricorsiva.

   if (n1>n2)
      max=n1;
   else
      max=n2;

   for (i=n1*n2; i>=max; i--)
      if (i%n1==0 && i%n2==0)
         mcm=i;

Io so che il minimo comune multiplo tra due numeri a e b è dato dal prodotto dei due diviso il massimo comune divisore, però non riesco a calcolarlo utilizzando la ricorsione.

Sapete darmi qualche idea per il codice corretto?

Grazie mille
Ciaoo

[Obidream]

Ciao, io così su 2 piedi farei in questo modo:

int mcm(int a, int b)
{
static int m = 1;
if (m % a == 0 && m % b == 0)
     return m;
m++;
mcm(a,b);
return m;
}

La variabile m è dichiarata come statica per non alterare il suo valore ad ogni chiamata della funzione mcm.

[floppyes]

Ciao!

Grazie mille per la risposta. In pratica la riga:

if (m % a == 0 && m % b == 0)
      return m;

equivale al caso base, mentre:

   m++;
   mcm(a,b);
   return m;

equivale al codice da eseguire nel caso in cui non sia soddisfatto il caso base.

Grazie mille
Ciao

[apatriarca]

L'uso di static è altamente sconsigliato. Se mai dovrai/vorrai usare tale funzione in un codice parallelo, incontrerai non pochi problemi. Conviene quindi eliminare tale variabile fin dall'inizio. Ma il problema principale di questo codice è il metodo con cui viene implementata la ricorsione in linguaggi come C. Se \(a\) e \(b\) sono sufficientemente grandi il codice potrebbe crashare perché hai riempito lo stack. Sarebbe meglio usare la ricorsione per calcolare il GCD. Qualcosa come il seguente:

int lcm(int a, int b) {
    return lcm_rec(a, b, a*b);
}

int lcm_rec(int a, int b, int p) {
    if (b == 0) { return p/a; }
    else { return lcm_rec(b, a%b, p); }
}

L'utilizzo di una seconda funzione è abbastanza comune quando si usa la ricorsione.

[floppyes]

Ciao!

Perfetto grazie mille per la spiegazione

Ciaoo!