3. Rekursion - Verständnisproblem

Rekursion - Verständnisproblem

  • K

    Hallo Programmier Freunde,

    ich bin gerade beim Thema Rekursion und bin echt am verzweifeln. Ich verstehe einfach nicht wie die Potenzierung abläuft. Besser gesagt verstehe ich alles außer einen kleinen Teil, der eigentlich am wichtigsten ist.

    Hier erstmal ein Beispiel:

    #include <iostream>

using namespace std;

int Answer(unsigned short number, unsigned short power);

int main()
{
int number, power;
int answer;
cout << "Geben Sie eine Zahl ein: ";
cin >> number;
cout << "Zu welcher Potenz? ";
cin >> power;
answer = Answer(number,power);
cout << number << " hoch " << power << " ist gleich " <<
answer << endl;

return 0;

}

int Answer(unsigned short number, unsigned short power)
{
if(power == 1)
return number;
else
return (number * Answer(number,power-1));
}

    So jetzt ist die Frage wie am ende in Zeile 28 das number aus (number * Answer(number,power-1) multipliziert wird. Gehen wir davon aus die erste Zahl ist 4 und soll ebenfalls mit 4 potenziert werden. Wie bekommt aber das Answer(number,power-1) den Wert 4? Wie es wieder zurückgeworfen wird bis die Potenz auf 1 geht verstehe ich soweit. Aber mein Gedanke ist, dass wenn es returned wird und das Programm die Potenz 1 bringen will, wann überhaupt die 4 multipliziert wird.

    Mir fällt es schwer mein Problem zu beschreiben, ich hoffe ihr habt es verstanden.

    0
  • D

    Das kommt aus Zeile 26 wenn die Rekursion genug tief ist. Mach es einfach mal von Hand für eine kleine Zahl:

    Answer (2,3)
-> // power != 1 also rekursion
2*Answer(2,2)
-> // power != 1 also rekursion
2*2*Answer(2,1)
-> // power == 1, also wird return 2 gemacht
2*2*2
    0
  • K

    drakon schrieb:

    Das kommt aus Zeile 26 wenn die Rekursion genug tief ist. Mach es einfach mal von Hand für eine kleine Zahl:

    Answer (2,3)
-> // power != 1 also rekursion
2*Answer(2,2)
-> // power != 1 also rekursion
2*2*Answer(2,1)
-> // power == 1, also wird return 2 gemacht
2*2*2

    Danke erstmal für die Mühe.
    Ich versuchs mal selber zu erklären, soweit ich das verstanden habe.

    So sagen wir mal 2 number und 3 power
    dann wird 2,3 logischerweise zu else
    2 * answer(2,3-1)
    2 power ist wieder nicht 1 also wirds wieder zu else
    dann bleibt die erste 2 * vom letzten und es heißt nun
    2 * 2 * answer(2, 2-1)
    dann wird if true und dies wird dann zu den (2 * 2 😉 multiplziert sodass es am ende 2 * 2 * 2 heißt. aber wenns so ist, wie kommt das programm dazu, beim letzten schritt die zahl mal zu nehmen oder die zahlen miteinander zu verknüpfen?

    total verwirrt gerade 😕

    0

  • Die einzelnen Rechenschritte (Multiplikationen) werden jeweils beim 'return' schon ausgerechnet, nicht erst ganz am Schluß, d.h.

    Answer (2,3)
-> // power != 1 also rekursion
2*Answer(2,2)
-> // power != 1 also rekursion
2*(2*Answer(2,1))
-> // power == 1, also wird return 2 gemacht
2*(2*2)
->
2*4
->
8

    Je Rekursionsebene wird also ein Teilergebnis berechnet (das in den Klammern).
    Vllt. ist das so jetzt besser für dich verständlich?

    0
  • ?

    Der Algorithmus lautet nach dem Prinzip von Divide and Conquer übrigens so:

    int sq(int x)
{ return x * x; }

int pow(int a, int b)
{
 if (b == 0)
 { return 1; }
 else if (b % 2 == 0)
 {
  return sq(pow(a, b/2));
 }
 return a * pow(a, b-1);
}

    Ungetestet.

    0
  • K

    ich glaube es verstanden zu haben.
    es wird also die zahl ausgerechnet und in einen speicher "gelagert"
    dies geht dann immer weiter und es wird nacheinander mit dem gespeicherten zusammengeführt bis halt if erfüllt wird.
    so würde es dann ungefähr dann aussehen:
    (number * (number * (number* (Answer(number,power-1)))));
    bis power halt auf 1 ist?

    0
  • D

    Th69 schrieb:

    Die einzelnen Rechenschritte (Multiplikationen) werden jeweils beim 'return' schon ausgerechnet, nicht erst ganz am Schluß, d.h.

    Das stimmt. Ich dachte, dass ich es halt eher als Teleskopsumme aufschreibe, damit er besser sieht, was da in etwa passiert.

    @KompiPauer:
    Genau so sieht das aus. Wobei der Speicher üblicherweise der Stack für die lokalen Variablen einer Funktion ist. Wenn du mit einem Debugger das mal durchgehst und die unterste Funktion gehst siehst du schön, wie das ganze zurückgesteppt wird und das Ergebnis am Ende entsteht.

    0
  • K

    Sehr gut, jetzt kann ich besser schlafen 😃

    0
Anmelden zum Antworten