¿Alguien puede ayudarme a entender cómo funciona este código?

Probemos un ejemplo. Calcular MCD (36,60). Supongo que son las 12.

Los nombres de las variables en la declaración son los nombres de las entradas. Los nombres de las variables en la línea 2 son sus usos.

Entonces mcd (u = 36, v = 60) -> v = 60, u% v = 36

-> mcd (u = 60, v = 36) -> v = 36, u% v = 24

-> mcd (u = 36, v = 24) -> v = 24, u% v = 12

-> mcd (u = 24, v = 12) -> v = 12, u% v = 0

-> mcd (u = 12, v = 0) -> devolver u = 12; y ahora sube la pila de llamadas hasta llegar a la cima.

Entonces, no es un algoritmo con el que estoy familiarizado, pero el principio aquí es tratar de encontrar el número entero más grande que, cuando se divide en cada uno de los 2 números enteros dados, tenga un resto de 0 en ambos casos.

a menudo, la mejor manera de explorar código desconocido es ejecutar un ejemplo. Así que intentemos llamarlo con 6 y 9 esperando la respuesta 3.

entonces, mcd (6, 9): u = 6, v = 9. v no es 0 así que ahora llame:

mcd (9, 6% 9 = 6). v no es 0, así que ahora llame:

mcd (6, 9% 6 = 3). v no es 0, así que ahora llame:

mcd (3, 6% 3 = 0). ahora, v es 0, por lo que 3 se devuelve al llamador original.

No intentaré explicar por qué esto funciona, pero si trabajas con otros ejemplos, verás que funciona.

Sobre la pregunta específica de por qué la llamada recursiva es gcd (v, u% v), bueno, no tiene que ser así. Tenga en cuenta que es válido que la persona que llama inicialmente llame a gcd (6,9) o gcd (9,6) y espere la misma respuesta en ambos casos. En mi ejemplo, la primera llamada simplemente invierte los argumentos para obtener la más grande primero. Esto significa que escribir el algoritmo como:

Int mcd (u, v) {

Devuelve u == 0? v: mcd (v% u, u);

}

Funcionaría igual de bien. Por cierto, prefiero el == aquí al! = En el original porque es más fácil de leer. Esta segunda versión es más rápida cuando u

Tienes que entender un poco de teoría de números.

Digamos que d es el mcd de u y v. Significa u = m * d y v = n * d para algunos m, n tal que mcd (m, n) = 1. Sin pérdida de generalidad podemos suponer u> v.

Entonces tenemos, u = p * v + k para algunos py k.

=> m * d = p * n * d + k

=> d | k, yk es el resto cuando u se divide por v.

QED