Rekursion Modulo

[Lazyyy]

Hallo zusammen,
während meiner Anfänge der Rekursion auf folgendes Problem gestoßen:

public class Modulo {

   public static int calculate(int dividend, int divisor) {
       int result = 0;
       if(divisor <= 0 || dividend < 0)return -1;
       
       if(divisor < dividend){
           result = calculate(dividend-divisor, divisor) + 1;
       }
       
       return dividend - result*divisor;
   }
}

ich will den Modulo berechnen.
Meiner Meinung nach zäht der code in result die anzahl der Teilungen. Diese soll er mit dem divisor multiplizieren und anschließend vom Dividenden abziehen.

Der Test mit 10 und 2 welcher 0 erwartet ergibt zum beispiel 28.
Test 8 und 3 erwartet 2 und ergibt 17.
Kann mir beim besten willen nicht erklären wo diese Zahlen her kommen. Falls ich meinen eigenen Code komplet fehl interpretiere wäre eine Korrektur nett :

Viele Grüße

 

[httpdigest]

Das Problem ist, dass der Aufruf von calculate(dividend-divisor, divisor) innerhalb von result = calculate(dividend-divisor, divisor) + 1 ja nicht die Gesamtzahl der Teilungen für diesen rekursiven Abstieg zurückliefert, sondern ja auch alle Summen der einzelnen Rekursionsaufstiege mit return dividend - result*divisor;.

Eine bessere Lösung wäre, nicht die Anzahl der Teilungen zu zählen, sondern solange dividend-divisor rekursiv zu berechnen, bis dividend < divisor, in welchem Fall dividend dann das Ergebnis ist.

 

[Lazyyy]

Ah ok wie bekomme ich es hin dann diesesn einen Wert aus der Rekursion zu holen. Wenn ich den Dividenden heraushole ist es immer der Anfangswert.

if(dividend > divisor){
           result = calculate(dividend-divisor, divisor);
       }
       
       return result;      // noch falsch weil nicht der Dividend

 

[Blender3D]

Ah ok wie bekomme ich es hin dann diesesn einen Wert aus der Rekursion zu holen. Wenn ich den Dividenden heraushole ist es immer der Anfangswert.

Wenn dann so.
Modulo nur für positive Werte:

public static int modulo(int dividend, int divisor) {
        if (dividend == divisor)
            return 0;
        if (divisor > dividend)
            return dividend;
        return modulo(dividend - divisor, divisor);

    }

 

[httpdigest]

Die Abfrage auf divident == divisor benötigt man nicht. Durch die Subtraktion in der einen nachfolgenden Rekursion wird das Ergebnis sowieso dann 0.

 

[MoxxiManagarm]

Wenn dann so.
Modulo nur für positive Werte:

Den Fall divisor=0 solltest du streng genommen dann auch mit betrachten.

       if(divisor <= 0 || dividend < 0)return -1;

Es mag vielleicht Geschmackssache sein, aber für diesen Fall finde ich es sinnvoller z.B. eine IllegalArgumentException zu werfen anstatt -1 zurückzugeben.

 

[Blender3D]

Den Fall divisor=0 solltest du streng genommen dann auch mit betrachten.

Es sollten negative Werte auch beachtet werden, um ein brauchbares Modulo zu bekommen. Hier steht die Rekursion im Vordergrund.

 

[Blender3D]

Die Abfrage auf divident == divisor benötigt man nicht. Durch die Subtraktion in der einen nachfolgenden Rekursion wird das Ergebnis sowieso dann 0.

Stimmt.