rekursion

Beechen

hi@all,

ich hab mich ja gestern schon im forum bemerkbar gemacht, weil ich keinen kleinen denkanstoß zum thema assembler brauchte

nun bräuchte ich glaub ich noch einen - es geht um folgendes ich soll die fakultät rekursiv berechnen. in normalem c würde das ungefähr so aussehen:

int fak_rec(int num) {
  if (num == 1 || num == 0) return num;
  else 
    return num*fak_rec(num-1);  
}

kann sein, dass da jetzt ein paar fehlerchen drin sind, habs hier direkt im forum geproggt

jedenfalls will ich dass in assembler umsetzten und meins sieht ungefähr so aus:

int fak_rec(int num) {
  __asm {
        cmp num, 1;   // num == 1 ?
        ja  NOCHMAL;  // if(num > 1) nochmal
        jbe ENDE;     // else ende
NOCHMAL:
        pop  eax;     // hol eax aus dem stack
        mul  num;     // eax *= num
        push eax;     // eax in den stack
        dec  num;     // num--
        push num;     // fragt mich mal warum man das machen muss
        call fak_rec; // und nicht: call fak_rec(num) ???
ENDE:
        pop  eax;
        }
}

aber es funzt nich - kann ja auch nicht weil ein undefinierter wert beim ersten aufruf aus dem stack geholt wird.

meine frage ist nun: gibt es eine möglichket das in einer funktion zu lösen? ich hätte schon eine idee, wie ich das mit einer hilfsfunktion lösen könnte, aber ich vermute mal mein prof. möchte das nicht so sehen...

habt dank

Simon

[ Dieser Beitrag wurde am 25.06.2002 um 07:59 Uhr von SimonBee editiert. ]

TriPhoenix

Bau die Rekursion doch mal andersrum auf, nämlich gehts mir um diese Zeile:

return num*fak_rec(num-1);

Wenn du erst fak_rec(num - 1) berechnest und dann multiplizierst, brauchst du keine Zwischenergebnisse rumreichen...ein versuch in asm (ungetestet, sollte aber klappen ;))

int fak_rec(int num) {
  __asm {
        mov eax, num; // eax = num
        cmp num, 1;   // num == 1 ?
        ja  NOCHMAL;  // if(num > 1) nochmal
        jbe ENDE;     // else ende
NOCHMAL:
        dec  eax;     // num - 1 berechnen
        push eax;     // Parameter auf Stack ablagen
        call fak_rec; // fak_rec(num - 1);
        mul  num;     // eax *= num
ENDE:
        pop  eax;
        }
}

phreaking

int fak(int num)
{
    __asm
    {
        cmp num, 1
        ja  CALC
        mov eax, 1
        jmp END
    CALC:
        mov eax, num
        dec eax
        push eax
        call fak
        add esp, 4
        mul num
    END:
    }
}

lg, phreaking

Beechen

danke erstaml euch beiden!

@TriPhoenix: leider hat deine version nicht gefunzt, da wird immer mit einem fehler abgebrochen

@phreaking: deins hat mal wieder gefunzt doch leider weis ich nicht was folgende zeile bewirkt:

add esp, 4

das hat sicher irgendwas mit nem stackpointer zu tun aber ich weis ned was. kannst du mir das vielleich noch kurz erläutern?

danke euch beiden!

Simon

japro

also wenn es hier um optimierung geht dann ist das sinnlos da die rekursion in diesem fall overkill ist... eine normale c variante mit einer schleife dürfte schneller sein als die rekursive asm version. ich nehme an die meisten wussten das schon... wollts nur gesagt haben

Beechen

darum geht es nicht - mir gefällt die schleifenvariante auch besser (weil ich sie verstehe) ich MUSS aber die lösung auch rekursiv erzeugen.

Mir gefällt die lösung von TriPhoenix ziemlich gut, leider funzt sie nicht. die von phreaking hat den nachtel, das sie sich ESP bedient, und dass darf ich nicht (übung) sondern muss irgendwie mit eax, ebx, ecx, edx uns stack klarkommen.

Simon

Beechen

hmm also nach endlosem probieren hab ich eine funtkionierende lösung gefunden:

int fak_rec(int num) {
  __asm {
        cmp num, 1;      // (num == 1) ?
        ja  NOCHMAL;     // num > 1: nochmal
        mov eax, 1;      // sonst: eax = 1
        jmp ENDE;        //        ENDE
NOCHMAL:
        dec  num;        // num -= 1
        push num;        // parameter ablegen
        call fak_rec;    // rekursiver aufruf
        pop  ebx;        // ergebnis v. fak_rec interessiert nicht (siehe eax)
        inc  num;        // stelle num wieder her
        mul  num;        // eax *= num
ENDE:
        }
}

mir gefallen aber ein paar sachen daran nicht:

das ergebniss vom rekursiven aufruf wird einfach weggepoppt (nach ebx) weil das eigentliche ergebniss ja in eax steht
ich weis nicht genau wie ich einer funktion den rückgabewert vestlege - also die funktion int test(int t) gibt ja ein int zurück, doch wie kann ich die return zuweisung machen? wird einfach dass, was in eax steht als rückgabewert interpretiert?! kann man das auch per hand - um punkt 1) zu beheben???

vielen dank im vor.aus

Simon

[ Dieser Beitrag wurde am 25.06.2002 um 16:22 Uhr von SimonBee editiert. ]

phreaking

Also, der Rückgabewert einer Funktion liegt in C üblicherweise in eax. Das funktioniert so, dass die Funktion aufgerufen wird, die Funktion schreibt etwas nach eax und nach einem ret kann der Aufrufer der Funktion mit dem Wert in eax weiterarbeiten (oder auch nicht: void *gg*). Aus diesem Grund ist es auch möglich, die Multiplikation direkt nach dem Aufruf der Funktion durchzuführen.
Auf dem Stack werden nur die Parameter ausgelagert. Vor dem Aufruf mittels call werden die Parameter mittels push auf den Stack gelegt. Da unter C der Stack vom Aufrufer wieder aufgeräumt werden muss, muss das in unserem Fall der Aufrufer, also die Funktion fak selbst machen. Üblicherweise wird ein Wert mittels push auf den Stack gelegt, wobei implizit auch der Wert von ESP vermindert. Um einen Wert vom Stack zu holen, wird für gewöhnlich pop aufgerufen. Mittels diesem Befehl wird der Wert also vom Stack an eine bestimmte Stelle im Speicher kopiert, und anschließend der Wert von ESP wieder erhöht. Da bei meiner Funktion der Wert, der auf dem Stack lag, nach dem Aufruf nicht mehr wichtig war, habe ich mich damit begnügt, den ESP zu erhöhen.

lg, phreaking