Potenz mithilfe rekursiver Funktion

[moccajoghurt]

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]

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]

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]

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

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]

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);    
	}
}

ist aber nicht rekursiv wie vom TO vorgegeben

 

[0x7F800000]

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);
  }
}

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]

Angeber!

 

[XHelp]

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]

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]

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]

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]

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]

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]

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.

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.