Java Kleine Potenz-aufgabe sollte auch rekursiv laufen, kriege es nicht hin

ReVo · 31. März 2009

Hallo,

ich kann mit eine einfache while schleife eine potenzrechnung ausführe. Jetzt würde ich das auch gerne rekursiv machen, aber davon habe ich in java garkeine ahnung. Also es gibt x und y, es sollte x hoch y berechnet werden. Mit der schleife habe ich das so hinbekommen:

PHP:

public class Potenz {
	public static void main(String[] args) {
		
		int x = 2;
		int y = 5;
		int i = x;
		
		while(y > 1){
			i = i*x;
			y--;
		}
		System.out.println("Ergebnis:" + i);
	}
}

Klappt wunderbar, mein erstes java programm. Jetzt würde ich das gerne rekursiv machen... eigentlich dachte ich da an das:

PHP:

public class potenzrekursiv {
	
	public static void main(String[] args) {
		rekursiv(0, 2, 5);
	}
	
	static int rekursiv(int i, int x, int y) {
		
		i = x;
		
		if (y == 1) {
			System.out.println("Ergebnis: "+ i);
		}
		else {
			return rekursiv(i = i * x, x, y = y - 1);
		}
		return 0;
	}
}

Also es kommt irgendwie immer 2 raus. Ist ja klar, weil i immer x wird und x ist immer 2 und so auch mein ergebnis. Eig. müsste ich i = x da rausnhmen. Dennoch habe ich das gefühl, dass es auch einfacher geht bzw. dass ich falsch mit dem rekursion arbeite. Bevor ich das noch weiter verwurschtel, tips?

Gruß

sitting chair · 31. März 2009

Bitteschön^^:
class rekursiv{

public static int rekursiv (int x, int y){
if(y==0) return 1;
else {return x*rekursiv(x,(y-1));}
}

public static void main(String[] args) {
int x=2;
int y=10;
System.out.println(rekursiv(x,y));
}
}

edit:

x und y habe ich mal frei gewählt - kann ja auch der Benutzer eingeben oder ähnliches

ReVo · 31. März 2009

Hi danke,

das ist jetzt eine wie ich sehe recht gute lösung, weil das nur mit zwei variablen gemacht wurde. Aber wie würde man das ganze mit drei variablen machen wollen... so wie meine schleife, also mit i, wie könnte man das lösen?

Gruß

sitting chair · 31. März 2009

Wozu soll das i in der Rekursion denn gut sein? Ich meine die Rekursion ist kurz und liefert das gewünschte Ergebnis...warum sollte man das jetzt noch "aufblasen" und eine Variable einführen - was soll diese denn machen?

edit
man könnte deine Schleife ja auch ohne i schreiben, wäre das dann auch ok?

ReVo · 1. April 2009

Ja also ich wollte das ganze halt mit i sehen, damit ich das besser nachvollziehen kann. Also quasi genau das gleiche wie meine while schleifenlösung nur halt rekursiv

Gruß

Limit · 1. April 2009

Code:

def potenz1(basis, exponent):
	if exponent > 1:
		print basis * potenz1(basis, exponent - 1)
	else:
		return basis
		
def potenz2(ergebnis, basis, exponent):
	if exponent > 1:
		potenz2(ergebnis * basis, basis, exponent - 1)
	else:
		print ergebnis * basis

potenz1(2, 5)
potenz2(1, 2, 5) # hier muss als erster parameter immer 1 übergeben werden.

Der Code ist zwar in Python und nicht in Java, aber ich denke das zu übertragen sollte kein Problem sein. Die erste Funktion (potenz1) entspricht in etwa der Version von sitting chair. Die 2. Version eher dem, was du im Sinn gehabt hast. Der Unterschied ist eigentlich nicht so groß. Er besteht hauptsächlich darin wie das Ergebnis zurückgegeben wird, in erstem Fall als Rückgabewert und im zweiten Fall als ganz normaler Parameter. Ein kleiner Unterschied besteht noch darin, dass im ersten Fall die zuerst aufgerufene Instanz der Funktion die Ausgabe tätigt, wohingegen im zweiten Fall die zuletzt aufgerufene Instanz das macht. Wenn man beide gleichzeitig laufen lassen würde sollte die zweite Version früher eine Ausgabe abliefern. Die Gesamtlaufzeit sollte aber wiederum gleich sein.

Firestorm- · 6. April 2009

sitting chair schrieb:
Wozu soll das i in der Rekursion denn gut sein? Ich meine die Rekursion ist kurz und liefert das gewünschte Ergebnis...warum sollte man das jetzt noch "aufblasen" und eine Variable einführen - was soll diese denn machen?

edit
man könnte deine Schleife ja auch ohne i schreiben, wäre das dann auch ok?

Japp man kann das auch ohne "i" schreiben. Eine Rekursion stellt im allgemeinen Sinne einen alternativen Problemlösungsweg dar, welche meistens kürzer somit auch übersichtlicher ist. Manche Probleme der Informatik sind vorteilhafter mit einer Rekursion zu lösen als mit einer Iterativen Variante, typisches Beispiel: Towers of Hanoi.

Je nach Algorithmus sollte jedoch beachtet werden, dass die Zeitkomplexität und Speicherkomplexität unterschiedlich vorteilhaft sein können. In deinem Fall liegen beide Kenngrößen etwa im gleichen Bereich, bei komplexeren Problemen ist aber eine Abwägung dieser beiden Faktoren unabdingbar.

asdfman · 7. April 2009

Etwa heute noch nicht dein SICP gelesen?

Code:

(define power
  (lambda (x y)
    (define loop
      (lambda (y c)
        (if (= 0 y)
            c
            (loop (- y 1) (* c x)))))
  (loop y 1)))

€: Gegen Stack Overflow optimiert (Alle Sprachen benötigen Tail-recursion Optimierung!) :E

Suche

Java Kleine Potenz-aufgabe sollte auch rekursiv laufen, kriege es nicht hin

ReVo

Lieutenant

sitting chair

Lt. Junior Grade

ReVo

Lieutenant

sitting chair

Lt. Junior Grade

ReVo

Lieutenant

Limit

Lieutenant

Firestorm-

Lt. Commander

asdfman

Commander

Ähnliche Themen