# Multiplikation mit rekursivem Aufruf



## Wang (2. Nov 2010)

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 (2. Nov 2010)

[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 (2. Nov 2010)

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 (2. Nov 2010)

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 (2. Nov 2010)

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


----------



## Andi_CH (3. Nov 2010)

```
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 (3. Nov 2010)

Haave hat gesagt.:


> 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 ^^;
> ...



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 (3. Nov 2010)

oder kurz


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


----------



## Andi_CH (3. Nov 2010)

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


----------



## ARadauer (3. Nov 2010)

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


----------



## Landei (3. Nov 2010)

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


----------



## Andi_CH (3. Nov 2010)

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 (3. Nov 2010)

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 (3. Nov 2010)

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 (3. Nov 2010)

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


```
return a*b
```


----------



## ARadauer (3. Nov 2010)

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


----------



## Andi_CH (3. Nov 2010)

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 (3. Nov 2010)

ARadauer hat gesagt.:


> 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


----------

