Rekursive Methode zur Berechnung der Potenz q hoch p

L

Lestas89

Bekanntes Mitglied
In dieser Aufgabe soll die Potenz q hoch p berechnet werden mit einer rekursiven Methode. Dann steht noch zur Aufgabe: Schreiben Sie auf einem Blatt Papier die einzelnen Methodenaufrufe für die rekursive Berechnung von 3 hoch 4 auf. Rücken Sie die unterschiedlichen Ebenen ein.

Kann mir jemand den folgenden Code erklären wieso er eine Potenz berechnet und mir kurz sagen was mit dem Einrücken der unterschiedlichen Ebenen gemeint ist?

Java: 
class PotenzRekursiv {

    static double qHochpRek(int q, int p){
        if(p >= 0){
            if( p == 0)
                return 1;
            else
                return q*qHochpRek(q,p-1);
        }
        else{
            if( p == 0)
                return 1;
            else
                return 1./(q*qHochpRek(q,-p-1));
           
        }
       
    }
    public static void main(String[] args) {
        int q = 2;
        int p = -3;
       
        System.out.println(qHochpRek(q,p));
    }

}

Vielen Dank im Voraus!
 
Code: 
class PotenzRekursiv {
    static double qHochpRek(int q, int p) {
        if (p == 0)
            return 1;
        if (p > 0)
            return q * qHochpRek(q, p - 1);
        else
            return 1. / (q * qHochpRek(q, -p - 1));
    }
}
Hier der gleiche Code nur etwas einfacher geschrieben. Versuchs damit. 😉
 
Also Einrücken meint, dass Du einfach immer weiter rechts anfängst.

Code: 
Infos erster Aufruf
  Infos zum ersten Rekursiven Aufruf
    Infos zum zweiten Rekursiven Aufruf
    Infos bezüglich Ende zweiter Rekursiver Aufruf
  Infos bezüglich Ende erster Rekursiver Aufruf
Infos Ende vom ersten Aufruf

So ist dann relativ gut erkennbar, was auf welcher Ebene abgeht und was zusammen gehört.

Und der Code erklärt sich doch eigentlich von alleine. Wie eine Potenz berechnet werden kann, ist die bekannt?
x^y = x*x^(y-1)
und y^0 = 1
==> Rekursion bei positivem y.

Jetzt ist wichtig zu verstehen, was x^(-y) bedeutet.
x^(-y) = 1 / x^y = 1 / (x * x^(y-1))

Was in dem Code nicht stimmig ist, ist die zweifache Prüfung auf 0. Die Prüfung im else Zweig wird nie erreicht, da er da ja nur bei p<0 rein kommt.
 
Erstmal vielen Dank für die Antworten. Ich verstehe aber immer noch nicht diesen Schritt:

q*qHochpRek(q,p-1).

Ich wäre dankbar, wenn man mir Schritt für Schritt erklären würde wieso dies zu einer rekursiven Berechnung der Potenz führt.
 
Das hatte ich Dir bei den Mathematischen Grundlagen versucht zu erläutern:

Du willst ja q^p ausrechnen. qHochpRek ist deine Funktion dafür, also bedeutet
qHochpRek(q,p) = q^p

Und q^p = q * q ^ (p-1)
q ^(p-1) in der Schreibweise der Funktion ist: qHochpRek(q, p-1)
Somit ist q^p = qHochpRek(q, p) = q * qHochpRek(q, p-1)
==> das ist Deine Rekursion. Und damit das endet brauchst Du eine Abbruchbedingung. q^0 = 1. Und das ist halt die Abbruchbedingung mit dem if p == 0.
 
Hallo kneitzel,

nochmal danke für deine Antwort. Kannst du mir vielleicht noch das mit den Ebenen einmal am Beispiel von 3 hoch 4 zeigen? Ich glaube dann wäre ich hier fertig 🙂
 
Code: 
3 hoch 4
  3 * (3 hoch 3)
    3 * (3 * (3 hoch 2))
      3 * (3 * (3 * (3 hoch 1)))
        3 * (3 * (3 * (3 * (3 hoch 0))))
        3 * (3 * (3 * (3 * 1)))
      3 * (3 * (3 * 3))
    3 * (3 * 9)
  3 * 27
81

Das wäre jetzt sozusagen die reine Mathematik, die hinter dieser Rekursiven Berechnung stecken.
Das müsste man jetzt etwas umschreiben, so dass die Schritte des Java Codes sich gut wiederfinden.
Was ein großer Unterschied ist zwischen Mathematik und Code:
- Bei der Mathematik ist das Einrücken eher kontraproduktiv. Das hat man durch das Mitführen der "3 *" von den Vorzeilen.
- Bei dem Code würde man in jeder Einrückung diese Werte nicht mitführen - die kommen dann erst, wenn man wieder auf die Ebene der Funktion zurück kommt.
 
Das versteh ich aber irgendwie nicht. Ich hatte mir das in etwa so vorgestellt:

Code: 
static double qHochpRek(3, 4)
     static double qHochpRek(3, 3)
        static double qHochpRek(3, 2)
            static double qHochpRek(3, 1)

Meintest du das nicht so ? Bin jetzt total durcheinander
 
Ich habe keine Ahnung, wie Ihr das im Unterricht bisher gemacht habt. Das sind also Informationen, die Dir vorliegen sollten. Streng genommen sind nur die Aufrufe gefragt, daher sind das Deine Daten nur eben ohne das static double - das ist ja Signatur der Methode und hat mit dem Aufruf nichts zu tun.

Und die Aufrufe alleine sind in meinen Augen Unsinnig. Daran kann man die Berechnung ja in keiner Weise nachvollziehen. Daher bin ich davon ausgegangen, dass da andere Informationen gefragt sind.

Halt so in der Art, wie ich es schon ohne die Aufrufe aufgeschrieben habe.

Aber wie gesagt - das wäre meine Erwartungshaltung und für Dich ist die Erwartungshaltung des Lehrers wichtig. Und die kannst nur Du wissen weil Du im Unterricht warst.
 
Obwohl eine Frage habe ich noch: Das mit der Abbruchbedingung verstehe ich noch nicht so ganz. Wenn es bei p == 0 aufhören soll, müsste doch in der main methode eigentlich eine 1 ausgegeben werden wegen return 1. Wieso ist dies nicht der Fall?
 
Nein, denn die 1 bekommt ja der Aufruf zurück, der p = 0 übergeben hat. Daher hätte ich das ja auch anders aufgeschrieben, damit es deutlich wird.

Code: 
qHochpRek(3,4)
  3 * qHochpRek(3,3)
    3 * qHochpRek(3,2)
      3 * qHochpRek(3,1)
        3 * qHochpRek(3,0)
        3 * 1
      3 * 3 
    3 * 9
  3 * 27
81

Evtl. macht es Sinn, hier auch noch mehr Infos zu Aktionen anzugeben. Das wäre dann:

Code: 
print qHochpRek(3,4)
  return 3 * qHochpRek(3,3)
    return 3 * qHochpRek(3,2)
      return 3 * qHochpRek(3,1)
        return 3 * qHochpRek(3,0)
        return 3 * 1
      return 3 * 3 
    return 3 * 9
  return 3 * 27
print 81

Somit wurde das qHochpRek(...) immer ersetzt durch das, was denn da genau passierte. Jede Einrückung wechselt dann sozusagen in die Funktion - und die weiss nicht, was aussen ist und ist der auch egal.

So wird doch dann auch recht schnell deutlich, wieso nicht die 1 ausgegeben wurde, denn die landete dann ja nur eine Ebene höher und wurde da dann mit q (3) multipliziert.
 
Ich danke dir vielmals für deine Mühe, aber diesen Satz habe ich noch nicht so ganz verstanden:
Zitat:"Nein, denn die 1 bekommt ja der Aufruf zurück, der p = 0 übergeben hat"

Kannst du mir das vllt anders erklären? Da steig ich nicht hinter.
 
Du hast doch in den code-teilen die Aufrufe mit den umgebenen Aktionen. Geprüft wird bei jedem Aufruf, ob p == 0 ist. Dies ist jedoch nur bei dem Aufruf der Fall, der am weitesten eingerückt ist. Dieser Aufruf liefert 1 zurück, weshalb dann eine Zeile tiefer statt dem 3 * qHochpRek(3,0) die 3 *1 steht (der qHochpRek aufruf hat halt 1 zurück gegeben). Also wird jetzt 3 * 1 gerechnet und dann die 3 zurück gegeben. Die geht dann auch wieder eine Ebene hoch, so dass da dann das 3 * 3 rauskommt u.s.w.
 
Irgendwie hab ich das Gefühl, dass ich das immer noch nicht begriffen habe. Wieso wird 3 * 1 gerechnet wenn dort nur return 1 steht? Dort steht doch nicht q * return 1.
 
Die oberste Ebene gibt 1 zurück, aber die Ebene davor hatte doch diesen Code:
return q*qHochpRek(q,p-1)
Also bei q = 3 war das - so wie von mir angegeben:
3 * qHochpRek(3,0)
qHochpRek(3,0) gibt 1 zurück, so dass dann bei der Ebene
3 * 1 bleibt. Dies wird dann ausgerechnet und daher wird dann wieder eine Ebene höher 3 *3 was zurück gegeben wird u.s.w.
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

mantisse var * 10 hoch potenz var
Antworten: 2
rekursive Funktion zur Berechnung der Spiegelzahl
Antworten: 7
Rekursive Potenz ohne Math.Pow()
Antworten: 9
Potenz Berechnung
Antworten: 16
Rekursive Berechnung der Höhe eines binären Baumes
Antworten: 4

Zurück
Oben