Rekursive Funktion zum Potenzieren einer Zahl

jimmy086

Ich hab hier ein C Programm zum potenzieren. Die Funktion pow() wird rekursiv aufgerufen. Ich versteh aber nicht ganz wie das Programm eigentlich funktioniert!? Vorallem: return pow(m,n-1)*m ?? --> die ganze Funktion mit m multiplizieren?? was ist mit dem n?
Kann mir das jemand erklären?

#include <stdio.h>

int pow(int m,int n){
    if(n == 0)
         return 1;

    else
         return pow(m, n-1)*m;
}

int main(){
     printf("Ergebnis: %d\n",pow(3,2));  // Basis = 3, Exponent = 2
     getchar();
     return 1;
}

rüdiger

pow(m,0) => 1
pow(m,n) => pow(m, n-1)*m

für pow(3,2) sieht das dann so aus

pow(3,2) => pow(3,1)*3 => (pow(3,0)*3) *3 => (((1) *3) *3)

jimmy086

ja, das verstehe ich schon, ist vom Prinzip her wie eine Schleife die n mal durchläuft und jedes mal (m*m) rechnet!

aber ich versteh nicht wieso man einfach die ganze Funktion * m nehmen kann:
return pow(m, n-1)*m;
dann müsste doch auch das (n-1) mit m multipliziert werden??

Du multiplizierst nicht die Funktion selbst mit m, sondern du rufst zuerst die Funktion auf und deren Rückgabewert multiplizierst du mit m. Und dann gibst du das wieder zurück. Rekursion ist sehr schön.

Icematix

Rekursion ist sehr schön.

Mit einer for-Schleife wäre es sicher nicht schlechter und definitiv sicherer.

Mal sehen was die Funktion zu 2^12344567789 sagt.
Bzw der Stack.

Icematix schrieb:

Mal sehen was die Funktion zu 2^12344567789 sagt.
Bzw der Stack.

Ändert nichts daran, dass die Rekursion an sich schön ist.
Btw: welchen Datentyp willst du deiner for-Schleife übergeben, damit es keinen Überlauf gibt und dein allzu sicherer Code falsche Ergebnisse liefert? Auf einem 32 Bit System kriegst du das mit einem unsigned long nämlich nicht mehr hin.

jimmy086

rec schrieb:

Du multiplizierst nicht die Funktion selbst mit m, sondern du rufst zuerst die Funktion auf und deren Rückgabewert multiplizierst du mit m. Und dann gibst du das wieder zurück. Rekursion ist sehr schön.

ja schon klar, aber der Rückgabewert ist ja hier die Funktion selbst!

Das m wird einfach so of mit m multipliziert, bis das n = 0

aber was ich nicht verstehe: return pow(m,n-1)*m <= woher weiß der computer dass er das m mit dem (m) multiplizieren soll und nicht m mit (n-1)?
wird hier immer das 1.Element in der Klammer (m,n-1) verwendet??

knivil

Er multiplieziert das Ergebnis von pow(m,n-1) mit m. So wie es dasteht: werte pow(m,n-1) aus und multipliziere mit m. (m,n-1) gehoert zum Funktionsaufruf. In Mathe kannste doch auch z.B. y = x(x-1) als y = x*f(x) schreiben, wobei hier f(x) = x-1 ist.

jimmy086 schrieb:

ja schon klar, aber der Rückgabewert ist ja hier die Funktion selbst!

Ne, das ist dir anscheinend überhaupt nicht klar. Denn der Rückgabewert ist nicht die Funktion selbst, sondern ein int. Das ist ja auch deklariert.

Icematix

rec schrieb:

Icematix schrieb:

Mal sehen was die Funktion zu 2^12344567789 sagt.
Bzw der Stack.

Ändert nichts daran, dass die Rekursion an sich schön ist.
Btw: welchen Datentyp willst du deiner for-Schleife übergeben, damit es keinen Überlauf gibt und dein allzu sicherer Code falsche Ergebnisse liefert? Auf einem 32 Bit System kriegst du das mit einem unsigned long nämlich nicht mehr hin.

Och, 1MB Stack sollte man schon voll bekommen.
Was bleibt denn alles nach jedem Aufruf am Stack liegen? Rückprung-Addresse, Ergebnis und ?

knivil

Naja, man kann es auch tail recursiv / tail transfer schreiben.

jimmy086

So ist die Funktionsweise absolut verständlich (Endrekursiv):

#include <stdio.h>
 int pow(int m,int n,int acc){
     if(n == 0)
      return acc ;
     else
      return pow(m,n-1,acc*m);
  }

 int main (void)
 {
 printf("Ergebnis: %d\n",pow(3,2,1));
 getchar();
 return 1 ;
 }

Aber diese Rekursive Lösung ist für mich nicht nachvollziehbar!?:

int pow(int m,int n){ 
    if(n == 0) 
         return 1; 

    else 
         return pow(m, n-1)*m; //??
}

ist bei mir genau umgekehrt, die zweite verstehe ich sofort, bei der ersten musste ich ein paar mal hingucken.