von rekursiv zu iterativ

[BlueDolphin]

Hey,

ich bin grade dabei mich mit Rekursion zu beschäftigen. Folgende rekursive Methode quadriert eine Matrix:

//Matrix potenzieren
	static Matrix exp(Matrix a, int n) {
		
		if (n == 1) {
			
			return a;
		}
		if (n % 2 == 0) {
			
			return exp(a.mult(a), n/2);
		}
		return a.mult(exp(a.mult(a), (n-1)/2));
	}

die Methode mult hilft dabei:

Matrix mult(Matrix b) {
	    
	    int m = this.anzahlZeilen();     // Anzahl Zeilen
	    int n = this.anzahlSpalten();    // Anzahl Spalten
	    int mb = b.anzahlZeilen();       // Anzahl Zeilen in b
	    int nb = b.anzahlSpalten();      // Anzahl Spalten in b
	
	    if (n != mb) {
	 
	      return null; // Dimensionen nicht passend
	    }
	
	    // (m x nb) - Ergebnismatrix c erzeugen
	    // und Multiplikation durchführen
	    Matrix c = new Matrix(m, nb);
	    
	    for (int i = 0; i < m; i++) {
	      for (int j = 0; j < nb; j++) {
	        int summe = 0;
	        
	        for (int k = 0; k < n; k++) {
	          summe = summe + this.elemente[i][k]*b.elemente[k][j];
		}
	        c.elemente[i][j] = summe;
	      }
	    }
	    return c;
	}

Nun meine Frage: Kann man die Methode exp() denn auch in eine iterative Variante umwandeln? Man muss doch exp() trotzdem immer aufrufen, oder? Da das Ganze ja auf der Überlegung A^n = (A^2)^n/2 basiert. Falls nötig kann ich auch meien ganzen Quellcode posten.

Danke schonmal, LG Susi

 

[bygones]

natürlich kann man die methode auch iterativ umschreiben, einen aufruf von exp wäre aber falsch, da du ja dann wieder ins rekursive kommst.

 

[BlueDolphin]

einen aufruf von exp wäre aber falsch, da du ja dann wieder ins rekursive kommst

ja eben, mir fällt aber keine Lösung ein, die nicht rekursiv ist also ohne exp() aukommt ???:L hat vielleicht jemand einen denkanstoß für mich :roll:

 

[Andre_]

Denkanstoss: for oder while schleife

 

[bygones]

for oder while schleife die n runterzählt...

es gibt 3 möglichkeiten
n = 1 - das ist das ende der Iteration
n % 2 == 0 bzw. n % 2 !=0 - da dann die jeweilge berechnungen

 

[BlueDolphin]

erstmal danke für die Antworten...aber ich muss nochmal nerven :roll:

um a^n iterativ zu berechnen muss ich die Matrix ja "nur" in der Schleife immer *a rechnen, d.h.

a^2 = a.mult(a)
a^3 = (a.mult(a)).mult(a)
a^4 = ((a.mult(a)).mult(a)).mult(a)

das Problem ist ja nun, dass a nach dem ersten a.mult(a) zu a^2 wird und somit beim nächsten aufruft von mult() a^2*a^2 gerechnet wird, d.h. a wird immer überschrieben

ich habe das nun so gelöst, dass ich eine Hilfsmatrix b anlege, die die selben Startwerte enthält wie Matrix a
so funktioniert das Ganze zwar, aber zweckmässig ist das wohl nicht:

Matrix exp2(Matrix a, int n) {
		
		int x = 2;
		int y = 2;
		
		Matrix b = new Matrix (x,y);
		b.elemente[0][0] = 3;
		b.elemente[0][1] = 8;
		b.elemente[1][0] = 9;
		b.elemente[1][1] = 0;
		
		for (int i = n; i > 1; i--) {
		
			if (i == 1) {
			
				a = a;
			}
			
			if (i % 2 == 0) {
				
				a = a.mult(b);
			}
			
			if (i % 2 != 0) {
				
				a = a.mult(b);
			}
		}
		return a;
}

Wie kann ich das Lösen, ohne die Hilfsmatrix verwenden zu müssen?

Danke für die Hilfe

 

[master099]

nur mit mult() und der einen Matrix funktioniert das nicht

a^2 = a.mult(a)
a^3 = (a.mult(a)).mult(a)
a^4 = ((a.mult(a)).mult(a)).mult(a)

passt ja soweit müsstest du nur in der for-schleife sagen, dass jedesmal ein .mult(a) angehängt wird, aber wie das geht weiß ich auch net :bahnhof: