Methoden Rekursive Potenz ohne Math.Pow()

[javatar]

Hallo,

bin ganz neu hier. Ich habe ein kleines Problem. Ich möchte eine rekursive Methode schreiben, die mir eine Potenz X^n berechnet.

Soweit tut es was es soll, aber die Laufzeit ist immer so lang wie n groß ist. Kann man das nicht irgendwie optimieren, ich habe das hier gelesen Wiki, werde aber nicht ganz schlau draus, kann mir jemand helfen? Ahja, das ist mein Code:

 public double power(double x, long n){
	 
    	
    	if(n == 0){
    		ergebnis = 1;
    	}
    	if(n == 1){
    		ergebnis = x;
    	}
    	if(n > 1){
    		anzahlRechnungen++;	
    		ergebnis = x * power(x,n-1);

    	}
    		
    	return ergebnis;
    }

Gruß Javatar

 

[Marcinek]

Ja, wenn man es interaktiv berechnet und dann hat man noch die Möglichkeit es zu beschleunigen.

Rekursionen verursachen einen speicher overhead.

 

[Andi_CH]

interaktiv

... iterativ ... 🙂

public static int pow(int basis, int exponent) {
	int resultat = 1;
	for(int i=0; i<exponent; i++) {
		resultat *= basis;
	}
	return resultat;
}

 

[Marcinek]

... iterativ ... 🙂

Autovervollständigung => iPhone ^^

 

[javatar]

Und für die Rekursion gibt es keine Option?

 

[faetzminator]

Der gepostete iterative Code ist genau das gleiche wie dein rekursiver Code. Wo ist denn dein Problem? Du willst eine rekursive Methode - du hast eine rekursive Methode.

 

[SlaterB]

Rekursion oder iterativ per Schleife ist nur eine reine Technik, unabhängig vom Inhalt,

auf die Potenz bezogen kannst du in beiden Fällen die Anzahl der Durchläufe optimieren:
7^100
= 7*7*7*7 ......... 100x

oder

a = 7*7 = 7^2
b = a*a = 7^4
c = b*b = 7^8
d = .. 7^16
e = .. 7^32
f = .. 7^64

das sind schon nur 6 statt 100 Schritte und 'über die Hälfte' geschafft,
natürlich erreicht man nur mit Verdopplung selten exakt das Ergebnis, bisschen Arbeit ist da noch,
ich hoffe du willst das selber machen und nicht einfach die fertige Lösung haben 😉
alles per Rekursion oder Iteration zu lösen, ich rede nicht von vielen einzelnen Variablen
(gut, steht im Wiki praktisch auch so)

 

[javatar]

Der gepostete iterative Code ist genau das gleiche wie dein rekursiver Code. Wo ist denn dein Problem? Du willst eine rekursive Methode - du hast eine rekursive Methode.

SlaterB hat es beantwortet. Ich suche nach einer Optimierung.

 

[Marcinek]

Der gepostete iterative Code ist genau das gleiche wie dein rekursiver Code. Wo ist denn dein Problem? Du willst eine rekursive Methode - du hast eine rekursive Methode.

Bis auf den unterschied, dass du hier für jede Iteration einen Instruction Pointer auf einem Stack legst. Während die iterative Methode damit westnlich Speicherfreundlicher ist.

Das Ergebniss ist das gleiche.

 

[faetzminator]

Bis auf den unterschied, dass du hier für jede Iteration einen Instruction Pointer auf einem Stack legst. Während die iterative Methode damit westnlich Speicherfreundlicher ist.

Das Ergebniss ist das gleiche.

Ähm ja danke, ich weiss das... die Frage ist, ob es für einen Anfänger relevant ist. Man sollte lediglich wissen, dass es bei rekursiven Aufrufen mal wumms machen kann 😉