Rekursion für modulare Arithmetik

Question

Ich versuche, dies zu berechnen:

x^y (mod a) 

Rekursion verwenden, wie es besser für größere Zahlen funktioniert. Hier ist, was ich habe:

public int mod (int x, int y, int a){ 

if(y == 2){ 
return x^2%a; 
} 
if(y%2 == 1){ 
    return a%m*mod(x , y/2, a); 
} 
if(y%2 == 0){ 
return mod(x, y/2, a); 
} 


} 

Der Code funktioniert nicht und ein anderes Thema ist die „fehlende return-Anweisung“ Fehler bei der letzten Klammer. Was kann getan werden, um dies zu beheben?

Answer 1

In Java muss eine Funktion, deren Rückgabetyp nicht void ist, einen Wert zurückgeben. Leider ist der Compiler nicht intelligent genug, um zu verstehen, dass Ihre if-Anweisungen alle Werte des Eingangsparameters abdecken. Der Compiler geht davon aus, dass alle Ihre Bedingungen auf false ausgewertet werden können, sodass diese Funktion in diesem Fall keinen Wert zurückgibt. Es kann also die Korrektheit der Funktion nicht beweisen und meldet einen Fehler.

Answer 2

Ihre letzte if Anweisung if(y%2 == 0) ist redundant, da es nur zwei Möglichkeiten für y%2 sind: es ist entweder 0 oder 1.

Sie überprüft, ob es gleich 1 ist, so dass, wenn diese Bedingung falsch ist, die Sie nicht brauchen zu überprüfen, ob es gleich 0 ist, wird es auf jeden Fall gleich 0 sein, wenn es nicht gleich 1 ist entfernen

die letzten if und es funktioniert gut:

public int mod (int x, int y, int a){ 

if(y == 2){ 
return x^2%a; 
} 
if(y%2 == 1){ 
    return a%m*mod(x , y/2, a); 
} 

return mod(x, y/2, a); 


}