Basis recursie in C breinbreker

[Verwijderd]

Dus ik had vandaag examen C en ik moest zeggen wat deze recursie functie teruggaf:

code:

#include <stdio.h>
#include <stdlib.h>

void recurse(int n){
    if(n==0){
        return;

    }
    recurse(n-1);
    printf("\n recurse %d ", n);
    recurse(n-1);


}
int main(int argc, char**argv) {
    recurse(3);
    return 0;
}

En dat kwam uit op 1 2 1 3 1 2 1
Maar ik kan niet goed begrijpen wat er zich op de stack afspeelt. Ik heb heel veel gezocht en het zelf proberen begrijpen, maar ik breek mijn kop er echt over!

Ik weet dat tweakers geen online leerkracht is, maar als iemand mij zou kunnen vertellen waarom dit gebeurt en wat er zich op de stack afspeelt bent u hartelijk bedankt!

[ Voor 14% gewijzigd door Verwijderd op 31-05-2012 19:31 ]

[ibmos2warp]

Volgens mij is het niet zo moeilijk te begrijpen. Gewoon op een papiertje opschrijven wat erin gaat op welke positie en wat er dan daarna gebeurd zou volgens mij het al duidelijk moeten maken. Er gebeurd niks spannends op de call stack.

Zoiets kan je wel gaan opzoeken op het internet o.i.d. maar het is een kwestie van snappen. Door het op te zoeken snap je het niet. Door te doen wel. Ga dus zelf het programma "handmatig uitvoeren", zelf er doorheen lopen.

[ Voor 32% gewijzigd door ibmos2warp op 31-05-2012 19:38 . Reden: meer blabla ]

[leuk_he]

Heb je de mogelijkheid dit programmatin een visuele debugger te stoppen, en stap voor stap door te lopen, en af en toe een stack trace te bekijken?

code:

stack         geprinte waarde
r(3) r(2) r(1)   1
r(3) r(2)         2
r(3) r(r2) (1)   1
...

[ Voor 27% gewijzigd door leuk_he op 31-05-2012 19:42 ]

[Verwijderd]

Eeuh denk wel dat eclipse die mogelijkheid biedt, Btw ibmos dat heb ik 1000 keer gedaan, maar met een dubbele recursieve aanroep kan ik niet meer goed volgen.

[ibmos2warp]

Verwijderd schreef op donderdag 31 mei 2012 @ 19:38:
Eeuh denk wel dat eclipse die mogelijkheid biedt, Btw eval dat heb ik 1000 keer gedaan, maar met een dubbele recursieve aanroep kan ik niet meer goed volgen.

Ja eclipse kan dat. Wat bedoel je met eval?

[leuk_he]

Verwijderd schreef op donderdag 31 mei 2012 @ 19:38:
Eeuh denk wel dat eclipse die mogelijkheid biedt, Btw eval dat heb ik 1000 keer gedaan, maar met een dubbele recursieve aanroep kan ik niet meer goed volgen.

mee schrijven? en kun je daar de stack trace bekijken? Het feit dat hij dubbel is maakt hem niet echt anders he? elke keer dat je recurse aanroept komt er iets bij op de stack. elke keer dat een return doet (impliciet aan het eind van de recurse functie) gaat er 1 waarde van de stack af.

[Verwijderd]

Dat met "eval" was een pure fail laat maar hangen..
Ik ga het nog eens proberen uit tekenen dan!

[Verwijderd]

Als ik het goed begrijp zou het zo lopen:

Ik doe recurse(3)
-> 1ste recurse voert zichzelf uit = 2
-> 2de recurse functie = 1
Afdruk = 2 1

-> 1ste recurse = 1
-> 2de = 0
Afdruk = 1 2 1

n => 3 omdat voor 2 aparte recurse 3 moet doorlopen worden
print -> 3
Afdruk 3 1 2 1

->2de recurse = 2
-> 1ste recurse = 1
Afdruk: 2 1 3 1 2 1

->2de recurse = 1
-> 1ste recurse = 0
Afdruk: 1 2 1 3 1 2 1

Is die logica juist? Want tis enkel omdat ik het antwoord weet dat het nu juist uitkomt

[ZaPPZion]

Dit is wat er gebeurt, als ik inspring betekend dat dat er een function call is geweest, een sprong terug komt alleen na een return (ook als er geen expliciete return staat natuurlijk)

code:

r(3)
    r(2)
        r(1)
            r(0) -> return;
        printf(recurse 1)
            r(0) -> return;
        return
    printf(recurse 2)
        r(1)
            r(0) -> return;
        printf(recurse 1)
            r(0) -> return;
        return
    return
printf(recurse 3)
    r(2)
        r(1)
            r(0) -> return;
        printf(recurse 1)
            r(0) -> return;
        return
    printf(recurse 2)
        r(1)
            r(0) -> return;
        printf(recurse 1)
            r(0) -> return;
        return
    return
return

[Verwijderd]

Ge zijt nen held!
Maar kebbet ondertussen wel door !
n = 3

Je loopt door eerste recurse me 3 tot je aan stopconditie komt = 0 -> n = 1
Je print daarna 2 af omdat da je volgende n is (3-1) en het kan aan de printf functie-> printf 2
Je recursed 2 en komt terug aan 1 -> n= 1
_____________________________________ RECURSE 1 AFGELOPEN
n=3

printf 3
zelfde stappen als 2 enige verschil n van recurse 2 kan aan printf

[.oisyn]

Met recursie vind ik het altijd lastig om in mijn hoofd depth-first er doorheen te lopen - je verliest dan al snel de staat waarin je zit.

Praktischer is om het uit te schrijven als een lijstje die je steeds verder uitbreidt, waarbij je elke functioncall vervangt door het resultaat. Je begint dus met recurse(3):

code:

recurse(3)

Als je nu met n=3 de functie ingaat, dan kun je het dus vervangen door:

code:

recurse(2)
print(3)
recurse(2)

Vervolgens ga je een van de overgebleven recurse calls vervangen met wat er daadwerkelijk gebeurt. Hier pak ik de eerste recurse(2):

code:

recurse(1)
print(2)
recurse(1)
print(3)
recurse(2)

En zo verder:

code:

recurse(0)
print(1)
recurse(0)
print(2)
recurse(1)
print(3)
recurse(2)

recurse(0) returnt meteen, dus die kun je wegstrepen.

code:

print(1)
print(2)
recurse(1)
print(3)
recurse(2)

Rinse and repeat. Uiteindelijk kom je op:

code:

print(1)
print(2)
print(1)
print(3)
print(1)
print(2)
print(1)

[Verwijderd]

Zo vindk et wel logischer, allesinds dank voor u hulp :D! Nieuwe inzicht in recursie gekrege!

code:

recurse(3) -> n = 3, maar gen printf in buurt
recurse(2) -> doorloop recursie
recurse(1)
printf(1) ->eindwaarde recursie 1

code:

recurse(2) -> recursie 1 deel 2 (n-1), wordt afgeprint
printf(2)
recurse(1) ->eindwaarde recursie 1 deel 2
printf(1)

code:

printf(3) -> recursie 2 deel 1 -> n = 3 printf staat erboven
recurse(3) ->enzoverder
recurse(2)
recurse(1)
printf(1)

code:

recurse(2)
printf(2)
recurse(1)
printf(1)

[ Voor 59% gewijzigd door Verwijderd op 31-05-2012 21:23 ]

[Soultaker]

Wellicht mosterd na de maaltijd, maar je kunt de call stack ook als een binaire boom zien:

        3
      /   \
    2       2
   / \     / \
  1   1   1   1

Voor elke knoop in de boom (een functieaanroep met n > 0) wordt exact één cijfer geprint, en wel ná het evalueren van de linkertak en vóór het evalueren van de rechtertak. Dat zijn de cijfers precies in de volgorde waarin ze van links naar rechts in de boom voorkomen:

        3
      /   \
    2   |   2
   / \  |  / \
  1 | 1 | 1 | 1
    |   |   |  
  | | | | | | |
  v v v v v v v
  1 2 1 3 1 2 1

[Verwijderd]

Soultaker schreef op donderdag 31 mei 2012 @ 22:19:
Wellicht mosterd na de maaltijd, maar je kunt de call stack ook als een binaire boom zien:

        3
      /   \
    2       2
   / \     / \
  1   1   1   1

Voor elke knoop in de boom (een functieaanroep met n > 0) wordt exact één cijfer geprint, en wel ná het evalueren van de linkertak en vóór het evalueren van de rechtertak. Dat zijn de cijfers precies in de volgorde waarin ze van links naar rechts in de boom voorkomen:

        3
      /   \
    2   |   2
   / \  |  / \
  1 | 1 | 1 | 1
    |   |   |  
  | | | | | | |
  v v v v v v v
  1 2 1 3 1 2 1

YOU ARE THE FUCKING MAN