# Potenz mithilfe rekursiver Funktion



## moccajoghurt (19. Jul 2010)

Ich scheitere bei einer Aufgabe meines Java-Kurses, bei der es darum geht eine rekursive Funktion zu erstellen, die die Potenz einer Zahl berechnet. Hier nochmal die Aufgabenstellung:

Implementieren Sie in Java eine rekursive Funktion
public static double potenz(double zahl, int pot)
die die pot-te Potenz von zahl berechnet. Der Wert von pot kann auch negativ sein!. Schreiben Sie ein kleines Programm, das die Funktion testet.
Beispiele.:
potenz(2.0, 3) == 8
potenz(2.0, -3) == 0.125


Leider habe ich das Prinzip noch nicht verstanden, mit dem rekursive Funktionen Werte ausgeben. Bitte um Hilfe


----------



## XHelp (19. Jul 2010)

die Funktion für positive potenzen könnte wie folgt aussehen:

```
public static double potenz(double zahl, int pot) {
  if (pot==1) {
    return zahl;
  } else {
    return zahl*potenz(zahl,pot-1);
  }
}
```

Für negative Potenzen musst du es noch umschreiben.
x^-n = 1/x^n


----------



## Altintop (29. Sep 2011)

Zwar was älter dieser Thread, aber ich habe ein gutes Beispiel hier:

// Gibt "n hoch m" aus für n und m ganze Zahlen (REKURSIV)
	public static double potRec(int n, int m) 
	{
		if(m < 0)
			return 1 / potRec(n, -m); // Rückgabetyp double !!!

		if(m == 0) // Abbruchsbedingung und Standardwert 
			return 1;

		return n * potRec(n, m-1); // Rekursionsvorschrift anwenden
	}


----------



## bandy (29. Sep 2011)

moccajoghurt hat gesagt.:


> Ich scheitere bei einer Aufgabe meines Java-Kurses, bei der es darum geht eine rekursive Funktion zu erstellen, die die Potenz einer Zahl berechnet. Hier nochmal die Aufgabenstellung:
> 
> Implementieren Sie in Java eine rekursive Funktion
> public static double potenz(double zahl, int pot)
> ...




Hallo,

so kannst du jede Potenz jeder Zahl ausrechnen:


```
public class Potenzberechnen {
	
private double potenzBerechnen(double zahl, int potenz){
	
	double ergebnis= Math.pow(zahl, potenz);
	System.out.print(ergebnis);
	
	return ergebnis;	
}
	public static void main(String[] args) {
	Potenzberechnen P= new Potenzberechnen();
        P.potenzBerechnen(2, 3);    
	}
}
```


----------



## dehlen (29. Sep 2011)

bandy hat gesagt.:


> Hallo,
> 
> so kannst du jede Potenz jeder Zahl ausrechnen:
> 
> ...



ist aber nicht rekursiv wie vom TO vorgegeben


----------



## 0x7F800000 (29. Sep 2011)

XHelp hat gesagt.:


> die Funktion für positive potenzen könnte wie folgt aussehen:
> 
> ```
> public static double potenz(double zahl, int pot) {
> ...


Dieser Berechnungsvorschrift liegt die Beobachtung

```
a^n = a * a^(n-1)
```
zugrunde, das ist linear in n, was für große n schlecht ist.

Etwas besser:

```
import static java.lang.System.*;

public class Power {

	public static double pow(double d, int n){
		if (n < 0){
			return pow(1/d, -n); 
		}else if (n == 0){
			return 1;
		}else{
			double sqrt = pow(d, n/2);
			if (n % 2 == 0){
				return sqrt*sqrt;
			}else{
				return sqrt*sqrt * d;
			}
		}
	}
	
	public static void main(String[] args){
		out.println(pow(2, 3));
		out.println(pow(2, -3));
	}
}
```
bzw.

```
a^n = (a^(n/2))^2 für n gerade
a^n = a*(a^floor(n/2))^2 für n gerade
```
Hier wird die Potenz jedes mal halbiert, deshalb läuft's in O(lg(n)), was für fürchterlich große n (wie in Kryptographie benötigt) wichtig ist.


----------



## HoaX (29. Sep 2011)

Angeber!


----------



## XHelp (29. Sep 2011)

0x7F800000 hat gesagt.:


> das ist linear in n, was für große n schlecht ist


Eine effiziente Lösung und eine Lösung, die man gut nachvollziehen kann sind meistens nicht die selben Lösungen


----------



## xehpuk (29. Sep 2011)

0x7F800000 hat gesagt.:


> Hier wird die Potenz jedes mal halbiert, deshalb läuft's in O(lg(n)), was für fürchterlich große n (wie in Kryptographie benötigt) wichtig ist.


Deine Ausführung hat leider einen Haken: In der Kryptografie würde man nicht mit double rechnen. :bae:


----------



## bandy (29. Sep 2011)

dehlen hat gesagt.:


> ist aber nicht rekursiv wie vom TO vorgegeben



Wieso? Rekursiver Aufruf liegt doch dann vor, wenn eine Methode durch eine andere aufgerufen wird, oder? Wenn ich in meiner Methode die Methode 


```
pow()
```

der Klasse 


```
Math
```

aufrufe, dann ist es doch rekursiv?:bahnhof:


----------



## Dekker (29. Sep 2011)

Nein...

Rekursion bedeutet, dass sich eine Funktion selbst wieder aufruft um ein Problem zu lösen. Dabei wird meißt versucht ein großes Problem zu lösen in dem man es in kleinere Probleme aufteilt, bis sie so klein sind, dass man sie einfach berechnen kann. Mithilfe der Teillösungen kommt man dann zu Gesamtlösung. Dieser Ansatz wird z.B. auch Divide and Conquer genannt. Ein berühmter Algorithmus der nach diesem Prinzip vorgeht ist der Quicksort.

Das hier wäre Rekursion:


```
public int foo(int n){
  if(n<=0) // Das hier ist der sogenannte Rekursionsanker
      return 0;
  else
      return n+foo(n-1); // Rekursiver aufruf. foo(n) ruft also foo(n-1) auf -> Problem wurde verkleinert
}
```

Dabei sei angemerkt, das die Funktion foo nichts sinvolles macht, es soll einfach nur zeigen wie eine Rekursion im Prinzip funktioniert / aussehen kann.


----------



## Altintop (30. Sep 2011)

Ups, bin hier nicht registriert, aber wie gut, dass man auch als Gast posten kann.

Potenzieren - REKURSIV:


```
public static double potRec(int n, int m) 
	{
		if(m < 0)
			return 1 / potRec(n, -m); // Rückgabetyp double !!!
		
		if(m == 0) // Abbruchsbedingung, Startwert
			return 1;
		
		return n * potRec(n, m-1); // Rekursionsvorschrift anwenden
	}
```
______

Potenzieren - ITERATIV:


```
public static double potIt(int n, int m) 
	{
		double tmp = 1; // Zwischenspeicher
		
		if (m == 0) // Anfangsbedingung für Potenzen 
			return tmp;
		
		if (m < 0)
			for (int i = 1; i <= -m; i++)
				tmp /= n;
		
		if (m > 0)
			for (int i = 1; i <= m; i++)
				tmp *= n;
		
		return tmp;
	}
```
___

Sonstige Funktionen, wo man die Unterschiede zwischen Iteration und Rekursion darstellen kann:


```
// Gibt die Fakultät von n zurück, (REKURSIV)
	public static int facRec(int n)
	{
		if (n < 0) // Fehlerausgabe
			return -99;
		
		if (n == 0) // Anfangsbedingung für Fakultät
			return 1;
		else
			return n * facRec(n-1); // Rekursionsvorschrift anwenden
	}
```


```
//Gibt die Fakultät von n zurück (ITERATIV)
	public static int facIt(int n)
	{
		if (n < 0) // Fehlerausgabe
			return -99;
		
		int tmp = 1; // Zwischenspeicher
		
		if (n == 0) // Anfangsbedingung für Fakultät
			return tmp;
		
		for (int i = 1; i <= n; i++)
			tmp *= i;
		
		return tmp;
	}
```
___

Binäre Suche:


```
public static int binSearchRec(int[] a, int l, int r, int key)
       {
		int m = (l+r)/2;
		
		if (l > r )
			return -100;
		
		if (a[m] == key)
			return m;
		
                if (a[m] < key)
			return binSearchRec(a,m+1,r,key);
		else
			return binSearchRec(a,l,m-1,key);
		
	}
```


```
// Gibt die n-te Fibonacci-Zahl zurück, REKURSIV
	public static int fibRec(int n)
	{
		if (n == 0)  // Anfangswert F(0) = 0
			return 0;
		if (n == 1)  // Anfangswert F(1) = 1
			return 1;
		
		return fibRec(n-1) + fibRec(n-2); // Rekursionsvorschrift anwenden
	}
```


```
// Gibt die n-te Fib-Zahl zurück, ITERATIV
        public static int fibIt(int n)
	{
		int[] fib = new int[n+1];
		fib[0] = 0;
		fib[1] = 1;
		
		for (int i = 2; i <= n; i++){
			fib[i] = fib[i-1] + fib[i-2]; 
		}
		return fib[n];
	}
```

Denke das sind genug Beispiele


----------



## hdi (30. Sep 2011)

> Dabei sei angemerkt, das die Funktion foo nichts sinvolles macht, es soll einfach nur zeigen wie eine Rekursion im Prinzip funktioniert / aussehen kann


Naja, es ist die Summenfunktion, erzähl mal nem Mathematiker dass die nichts sinnvolles macht


----------



## 0x7F800000 (30. Sep 2011)

XHelp hat gesagt.:


> Eine effiziente Lösung und eine Lösung, die man gut nachvollziehen kann sind meistens nicht die selben Lösungen


Gilt für 99.999% der Fälle, jo. [c]a^n = (a^(n/2))^2[/c] kann aber jeder ab der Achten Klasse nachvollziehen, deswegen ist es in diesem Fall irrelevant: keiner fragt den ja nach einer Laufzeitanalyse. 



xehpuk hat gesagt.:


> Deine Ausführung hat leider einen Haken: In der Kryptografie würde man nicht mit double rechnen. :bae:


Genauso wie man für double keine rekursive Potenzfunktionen programmieren würde, weil das mit der FPU hundert mal schneller geht.


----------

