Multiplikation mit rekursivem Aufruf

[Wang]

Hallo,

ich habe diesen Code hier in Java-Code übersetzt, erhalte bei der Ausführung des Programms aber die Fehlermeldung "Exception in thread "main" java.lang.StackOverflowError
at Mult.mult(Mult.java:19)
..."

Weiß jemand, wo der Fehler liegt?

Gruß
Wang

function int mult(int a, int b){
	if(a == 0) {
		return 0;
	}
	else {
		a = a - 1;
		int c = mult(a, b);
		int d = b + c;
		return d;
	}
}

// Datei: Mult.java

public class Mult
{
	private int a;
	private int b;
	private int c;
	private int d;
	
	public int mult (int a, int b)
	{
		if (a == 0)
		{
			return 0;
		}
		else
		{
			this.a = a - 1;
			this.c = mult(a, b);
			this.d = b + c;
			return d;
		}
	}
	
	public void print()
	{
		System.out.println ("Das Produkt lautet: " + d);
	}
	
	public static void main (String[] args)
	{
		Mult test = new Mult();
		test.mult(2,3);
		test.print();
	}
}

 

[preachie]

[JAVA=18] this.a = a - 1;
[/code]

Du ziehst von dem lokalen a 1 ab und weist das Ergebnis der Klassenvariable a zu.
Übergeben tust Du dann aber wiederum die lokale Variable a die weiterhin unverändert ist, so dass die Bedingung a == 0 nie erfüllt ist.
Daher fliegt Dir irgendwann der Stack um die Ohren wenn ein paar Hundert/Tausend/Millionen/Milliarden Mal die mult() Methode aufgerufen wurde 😉

 

[Marco13]

Zwischen dem Parameter 'a' und 'this.a' ist ein Unterschied. Manchmal ist es einfacher, als man vielleicht denkt.
(Meistens aber nicht, also nicht zu optimistisch werden 😀 )

public class Mult
{
    public int mult (int a, int b)
    {
        if (a == 0)
        {
            return 0;
        }
        else
        {
            a = a - 1;
            int c = mult(a, b);
            int d = b + c;
            return d;
        }
    }

    public static void main (String[] args)
    {
        Mult test = new Mult();
        System.out.println ("Das Produkt lautet: " + test.mult(2,3));
    }
}

 

[Haave]

StackOverflowError bedeutet, dass die Berechnung länger dauert, als Speicher dafür im Computer vorhanden ist. Das Code braucht also aus irgendeinem Grund endlos lange.
Hast du überprüft, ob der Ausgangscode (also dein gefundener Code) überhaupt einwandfrei funktioniert? Ich bin nicht so der Pro bei Rekursion, aber mir kommt der rekursive Aufruf in Zusammenhang mit der Zuweisung komisch vor und dass d beim Abarbeiten des Stacks mehrmals zurückgegeben werden müsste. Es sollte aber nochmal jemand anders drüberschauen, der mehr Ahnung davon hat als ich.

EDIT:
Okay, ist also schon passiert ^^;

Sorry für den verzapften Mist… 🙁

 

[Wang]

Danke. 😳
Warum leicht, wenn's auch kompliziert geht...

 

[Andi_CH]

public class mult {

	private static int multiply(int a, int b){
		if(a == 1) {
			return b;
		} else {
			return b + multiply(--a, b);
		}
	}
	public static void main(String[] args) {
		System.out.println(multiply(3, 5));

	}
}

> 15

Funktioniert allerdings nur für positive Zahlen

 

[Andi_CH]

StackOverflowError bedeutet, dass die Berechnung länger dauert, als Speicher dafür im Computer vorhanden ist. Das Code braucht also aus irgendeinem Grund endlos lange.
...
EDIT:
Okay, ist also schon passiert ^^;

Sorry für den verzapften Mist… 🙁

Ich relativiere den "Mist" mal ;-)

"lange" hat nicht zwingend mit "Speicher" zu tun? ;-)

while (true) {
	System.out.println("blabla");	
}

Wird beliebig lange laufen aber keinen Stackoverflow produzieren

Stackoverflow hat damit zu tun, dass der Prozess Stack verbraucht und nicht mehr frei gibt - z.B. bei einer Rekursion, die nie abbricht. Für den Rücksprung wichtige Daten und lokale Variablen, im Beispiel unten das j, werden bei jedem Prozeduraufruf auf den Stack gelegt und erst beim Rücksprung freigegeben.

unendlicheRekursion:

Beachte! -- wird erst ausgeführt nachdem der Wert an unendlicheRekursion(i--); übergeben wurde

	private static void unendlicheRekursion(int i) {
		int j = i; // nur zur Demo, damit der Stack auch wächst ;-)
		System.out.println(j);
		if (j<=0)
			System.out.println("Ende der Rekursion"); // wird nie erreicht!
		else
			unendlicheRekursion(j--); // Bewirkt nichts mehr
	} // Platz für j und Rücksprungframe wird freigegeben - diese Zeile wird aber nie erreicht

Aufruf: unendlicheRekursion(3)
Ausgabe:
3
3
3
........ irgendwann dann Stack overflow

Die korrekte Variante:

	private static void endlicheRekursion(int i) {
		int j = i; // nur zur Demo, damit der Stack auch wächst ;-)
		System.out.println(j);
		if (j<=0)
			System.out.println("Ende der Rekursion");
		else
			endlicheRekursion(--j); // Korrekte Variante
	} // Platz für j und Rücksprungframe wird freigegeben

Ausgabe:
3
2
1
0
Ende der Rekursion

Wenn die Methode etwas mehr als nur einen int alloziert und der Aufruf mit MAXINT erfolgt, kann es allerdings auch zu einem Stack overflow kommen...

 

[ARadauer]

oder kurz

public static int mul(int a, int b){
      return b==0?0:a+mul(a,--b);
}

 

[Andi_CH]

Ich perönlich finde die ?: Notation hässlicher - na ja zumindest unleserlicher als die andere.
Aber jeder nach seinem Geschmack.

 

[ARadauer]

Ja stimmt, ist Geschmacksache...
Ich benutz es relativ häufig, da gwöhnt man sich dan natürlich dran.

 

[Landei]

public static int mul(int a, int b){
   return a==0 ? 0 : mul(a >> 1, b+b) + ((a&1) > 0 ? b : 0); 
}

 

[Andi_CH]

Da war doch mal was mit der unleserlichsten Zeile C Code .....

Im aktuellen Projekt ist diese Art des if's tabu - die Wartbarkeit des Codes leide.
Ich habe keine Ahnung in wie weit sich der Javacomplier steuern lässt um optimierteren Code zu erzeugen, aber darum kümmere ich mich nie - wenn es optimert sein muss, setze ich halt C ein

Ist das ein relevanter Laufzeitunterschied ?

public static int mul(int a, int b){
   return a==0 ? 0 : mul(a >> 1, b+b) + ((a&1) > 0 ? b : 0); 
}

public static int mul(int a, int b){
   int retVal = 0;
   if(...)
      ...;
   else
      ...;
   return retVal; 
}

 

[Landei]

Nein, ich denke da kommt die gleiche Performance heraus. Allerdings ist die Frage, ob die Operationen >> und & bei der Aufgabe "zugelassen" sind (das & könnte man noch ersetzen, das >> nicht so richtig). Der Algorithmus ist übrigens die Russische Bauernmultiplikation

 

[Marco13]

Hier nochmal mit der Multiplikationsformel von Kasimir Kostonjenko

public static int mul(int a, int b)
{
   if (a==1) return b;
   if (b==1) return a;
   return mul(1, a*b);
}

 

[Andi_CH]

???:L???:L???:L

return a*b

 

[ARadauer]

Kasimir Kostonjenko? Ist ein Joke oder? Sucht man den in Google findet man nur 5 Treffer, 2 davon von hier ;-)

 

[Andi_CH]

Könnte sein, wenn man davon ausgehen muss dass sehr oft Multiplikationen mit 1 vorkommen, bringen die ersten zwei Zeilen einen Gewinn, aber spätestens die Dritte kann direkt als

return a*b

geschrieben werden

gibt es auch ein [JOKE][/JOKE] Tag ? 🙂

 

[Marco13]

Kasimir Kostonjenko? Ist ein Joke oder? Sucht man den in Google findet man nur 5 Treffer, 2 davon von hier ;-)

Und der dritte (das PDF) macht vielleicht deutlich, warum ich den Namen zum angegebenen Code erwähnt habe.

@Andi_CH: Es sollte ja ... ("irgendwie") ... Rekursion drin vorkommen 😉