[DrScheme] Spiegazione calcolo MCD

[00FUMI]

Non so proprio se questo sia il posto giusto per postare ...ma non ho trovato un forum specifico per questo tipo di linguaggio ma spero comunque di ricevere una risposta.




Allora sto cercando di programmare (per scopi didattici) nel linguaggio drscheme

Sono arrivato a trattare la ricorsione sulle funzioni

riesco a capire il procedimento utilizzato nel caso in cui vi sia ricorsione infatti riesco a capire perfettamente come calcolare il numero fattoriale di un numero n e comunque funzioni simili.

-oggi sono arrivato ad una funzione che mi chiede di calcolare il massimo comun divisore tra due numeri

ho la soluzione ma non riesco a capire come cavolo funzioni realmente

allora la funzione e' questa :

(define (mcd n , m) : prende due naturali in input e restiutisce il mcd

(define (mcd n m)
             (cond
                [(= m 0) n)          ---> se m = 0 allora mcd = n;
                [else (mcd  m (remainder n m))]   --->altrimenti mcd = mcd (m , (resto della divisione m/n)

Qualcuno puo spiegarmi come fa a funzionare?


Grazie

[LeleFT]

Ciao.
La sezione è corretta: Programmazione.
Ti invito a prendere visione del regolamento interno, dove vi sono le norme per l'apertura di una discussione. Consiglio la lettura dei punti in cui si parla del titolo della discussione e del modo in cui postare il codice (utilizzo dei tag CODE, punto 6).

Sistemo io la discussione.

Ad ogni modo, mi pare di capire che quel codice applichi, semplicemente, l'algoritmo di euclide per il calcolo del MCD. Una breve spiegazione, con tanto di esempio (con n e m invertiti rispetto alla tua), è in questa pagina.

PS: quando programmavio io in DrScheme, usavo solo le tonde, non le quadre... mah...


Ciao.

[00FUMI]

Innanzi tutto chiedo scusa per gli errori commessi nel postare!

poi , si e' vero la soluzione si riferisce all'algoritmo euclideo per il calcolo del mcd

e algebricamente per me e' comprensibile ma quando vado ad applicarlo non riesco a capire come funziona la ricorsione (in termini di programmazione)

provo a fare uno esempio forse piu stupido di me :

m= 3 , n =2

allora seguendo la funzione avrei :

(= m 0)? ---> false

allora : (mcd 3 ,2) = (mcd 3 (1))

e poi? ......................... (so che realmente si prosegue con 2/(resto fra 3/2)= 1 , r=0 e quindi 1 e' MCD) ma non capisco che tipo di iterazione continua a fare la funzione per arrivare a m= 0 e quindi avere n=1.

Una volta avuto m = 0 e n=1 allora credo non iteri piu visto che se (= m 0) --> mcd = n


ringrazio per la pazienza

[LeleFT]

Originariamente inviato da 00FUMI
provo a fare uno esempio forse piu stupido di me :

m= 3 , n =2

allora seguendo la funzione avrei :

(= m 0)? ---> false

allora : (mcd 3 ,2) = (mcd 3 (1))

No: la sequenza di chiamate ricorsive è

(mcd 3 2)
(= m 0) ? --> false
ritorna: (mcd 2 1)
         (= m 0) --> false
         ritorna: (mcd 1 0)
                  (= m 0) --> true. restituisco m
         --> restituisco m
--> restituisco m

Questa è una ricorsione di coda. Il risultato lo hai già all'ultimo passaggio, ma devi aspettare che tutte le invocazioni terminino e propaghino il risultato verso la prima...


Ciao.

[00FUMI]

Ora mi e' tutto piu chiaro.


grazie ,ricorsivamente all'infinito