Recursief programmeren moeilijk, waarom?

[Gerrit88]

Tweakers!

Ik heb een tijdje geleden in het kader van mijn stage recursief programmeren moeten toepassen. Het idee van recursief programmeren is niet zo moeilijk maar toch blijkt het beoorlijk lastig te zijn om te volgen wat er precies gebeurd. Navraag en onderzoek op internet maakte duidelijk dat ik niet de enige ben met dit probleem. Ik ben nu bezig met het schirjven van mijn eindverslag en ben eigenlijk nieuwschierig om te weten hoe dit komt zodat ik dit ook in mijn verslag kan vermelden. Waarom is dit zo complex? Is het menselijk brein niet toereikend om te kunnen volgen wat er gebeurt? Op internet kan ik niet terugvinden wat de verklaring hiervoor is.

Wat ik wel gevonden heb:
http://www-128.ibm.com/de...nux/library/l-recurs.html

Op deze site wordt het volgende gesteld, helaas niet echt een verklaring waarom het lastig is.

Recursive thinking is difficult because it almost seems like circular reasoning. It's also not an intuitive process; when we give instructions to other people, we rarely direct them recursively.

---

Recursion is a great art, enabling programs for which it is easy to verify correctness without sacrificing performance, but it requires the programmer to look at programming in a new light. Imperative programming is often a more natural and intuitive starting place for new programmers which is why most programming introductions focus on imperative languages and methods. But as programs become more complex, recursive programming gives the programmer a better way of organizing code in a way that is both maintainable and logically consistent.

Hebben jullie een verklaring waarom dit lastig is?

[Pogostokje]

Ik had het ooit eens vergeleken met schaken. Je moet niet alleen vooruit denken, maar dat ook recursief kunnen doen en dan alle tussenliggende stappen kunnen onthouden. Dat vereist een bijzonder goed korte termijn geheugen, iets wat niet iedereen heeft of getraind heeft. Top schaker wordt je ook niet in 1 dag en sommige mensen leren het gewoon nooit, terwijl ze heus niet dom zijn.

Je bent het ook niet gewend: de code die je ziet op je scherm, verandert als het ware van betekenis bij elke recursie terwijl de "lettertjes" hetzelfde blijven. Dat is in strijd met alles wat men sinds het spijkerschrift heeft gedaan.

[NMe]

Ik denk dat het een beetje van je talent als programmeur afhangt of, in welke mate en waarom iets als dit moeilijk is. Ik heb programmeurs gesproken die onderhand zelf recursief lijken te denken, en ik heb programmeurs gesproken die het gewoon niet konden bevatten wat recursie inhoudt, zelfs de simpelste vorm niet.

In elk geval zijn wij mensen redelijk straightforward over het algemeen, zoals je quotes ook al aanhalen. Recursie is een dermate andere manier van denken dat het gewoon onnatuurlijk is en derhalve complexer dan een lineair stukje code.

[xdcx]

Ik heb zelf ook afgelopen weken voor het eerste recursief moeten programmeren.

Ik denk zelf dat het zo lastig is omdat je het overzicht, van hoe je bij de oplossing komt, niet hebt.
Oftewel je deeld het niet steeds in kleinere stukjes het op te lossen probleem, van groot naar klein, maar je gaat van klein naar groot.

Het is idd lastig te omschrijven. Ik kan in ieder geval wel zelf zeggen dat ik er ook moeite mee had.

[Boudewijn]

Ik heb wel het idee dat het in functionele talen makkelijk er wordt gemaakt (ivm het definieren van cases enzo) dan in een imperatieve taal.

Ik merk dat sinds ik veel functioneel schrijf, ik imperatief ook beter ben in recursie.
Het is en blijft gewoon goed oefenen!

[Gerrit88]

Alvast bedankt voor de reacties!

Er worden hier goede dingen genoemd waar ik wat mee kan. Het is inderdaad een niet natuurlijke manier van denken, wat we niet gewend zijn. Oefenen is het sleutelwoord .

Ik ga proberen een mooie verklaring in mijn verslag op te nemen!

Bedankt!

[Marcj]

Boudewijn schreef op vrijdag 07 maart 2008 @ 15:19:
Ik heb wel het idee dat het in functionele talen makkelijk er wordt gemaakt (ivm het definieren van cases enzo) dan in een imperatieve taal.

Ik merk dat sinds ik veel functioneel schrijf, ik imperatief ook beter ben in recursie.
Het is en blijft gewoon goed oefenen!

Idd. Zodra je een beetje leert omgaan met functionele programeertalen, wordt het recursief denken ook steeds makkelijker. Ik heb er iig geen enkele moeite meer mee. Sterker nog: ik vind het vaak veel leesbaarder dan een vage loop.

Wat ik zelf wel een nadeel vind is dat in veel imperatieve talen recursie niet heel bruikbaar is, omdat je dat niet zo diep kan doen. Terwijl het een heel krachtig middel is.

[Boudewijn]

Klopt, en je moet recursie ook *goed* doen als je een opbouwend argument hebt.
Iets met een giga stack alloceren wat niet de bedoeling is, en dus maar tail-recursive werken .

[Johnny]

Ik denk niet dat recursie lastiger te begrijpen is dan een willekeurig ander concept bij het programmeren, maar omdat je als programmeur er meestal pas mee wordt geintroduceerd op het moment dat je al bekend bent met andere concepten waardoor recursie vreemd lijkt.

[Boudewijn]

Johnny schreef op vrijdag 07 maart 2008 @ 16:32:
Ik denk niet dat recursie lastiger te begrijpen is dan een willekeurig ander concept bij het programmeren, maar omdat je als programmeur er meestal pas mee wordt geintroduceerd op het moment dat je al bekend bent met andere concepten waardoor recursie vreemd lijkt.

ja het is een andere manier van problemen oplossen.
maar in imperatieve talen is het vaak minder duidelijk om cases aan te geven, waardoor je mi. makkelijker een infinite loop maakt (iets met end-case vergeten).

Maar dat is mijn persoonlijke ervaring (in haskell bijv zie je het een stuk duidelijker).

[Gerrit88]

Ik denk wel dat het complexer en lastiger te begrijpen is dan veel willekeurige andere aspecten. zoals hierboven ook gezegt is, het is een onnatuurlijke manier van denken. Ik kan me echter wel voorstellen dat er mensen zijn voor wie het gewoon een manier van denken is, deze zullen er dan ook weinig of geen problemen mee hebben.

[Orphix]

Ik heb zelf nooit veel moeite met recursie gehad. Wellicht ook omdat een recursieve method call net als een gewone method call altijd plaatsvindt in een specifieke context. Dus in elke methode/functie die je aan het proggen bent bedenk je altijd de context waar het in plaatsvindt. Je bedenkt van te voren de:
- start context (waar begin je)
- (intermediate) context (doe actie op je context en do een recursieve call naar een of meerdere onderliggende contexten)
- final context (onder welke voorwaarde stop je)

Het is wel zo imho dat het gemakkelijker recursief programmeren is als de context dichter bij de natuurlijke wereld ligt (bv een directory structuur) dan iets abstracts als wiskundige representaties (bv mandelbrot).

Het is wel foutgevoelig omdat je al snel de verkeerde argumenten doorgeeft aan de recursieve call, waardoor je of in een infinte loop terecht komt of verkeerde waardes teruggegeven worden. Het is altijd zaak om dit goed te testen!

[RayNbow]

Gerrit88 schreef op vrijdag 07 maart 2008 @ 16:37:
zoals hierboven ook gezegt is, het is een onnatuurlijke manier van denken. Ik kan me echter wel voorstellen dat er mensen zijn voor wie het gewoon een manier van denken is, deze zullen er dan ook weinig of geen problemen mee hebben.

Recursief denken is redelijk normaal in de wiskunde. Denk bijv. aan inductie.

Informatieve linkjes
Wikipedia: Structural induction
Wikipedia: Mathematical induction
Wikipedia: Recursion
Wikipedia: Recursion (computer science)
Wikipedia: Corecursion
Wikipedia: Coinduction
etc...

[roy-t]

Ik heb toevallig het tijdens dat ik in aanraking kwam met recursie in lessen OOP bij mijn lessen Abstracte wiskunde inductie behandeld.

Als je het dan zo van 2 kanten krijgt is het ineens een stuk beter te doen.

Verder vind ik recursie niet zo vreemd meer. bijvoorbeeld voor een parser, die moet binnen een loop opnieuw gaan parsen.

Dan wordt het: probeer alle statements te parsen->loop gevonden->in een loop kunnen alle statements (inc loops) weer voorkomen, dus: begin opnieuw (probeer alle statements te parsen)

Dit gaat dan per recursieve loop door tot dat het loop closing bracket gevonden wordt. dan exit je die recursieve loop en kom je weer 1 trapje hoger, enzovoorts.

Dit is best wel brainfuck als je er over nadenkt, maar het schrijven zelfs was eigenlijk niet al te moeilijk.

[Spockz]

roy-t schreef op zaterdag 08 maart 2008 @ 08:24:
Dit is best wel brainfuck als je er over nadenkt, maar het schrijven zelfs was eigenlijk niet al te moeilijk.

Ik zou niet zeggen dat het brainfuck is. Het is in feite je probleem opdelen in kleinere deelproblemen. Dat die deelproblemen vervolgens van dezelfde aard kunnen zijn als je hoofdprobleem is alleen maar gunstig.

[Confusion]

Gerrit88 schreef op vrijdag 07 maart 2008 @ 15:43:
Het is inderdaad een niet natuurlijke manier van denken, wat we niet gewend zijn. Oefenen is het sleutelwoord .

Recursief denken is iets heel natuurlijks. Mensen gebruiken het op tenminste twee manieren:
1) Wanneer ze aan zelfreflectie doen.
2) Wanneer ze de bedoelingen van een ander proberen te doorgronden, rekening houdende met de kennis die die anderen van hen hebben. (Ik denk dat jij denkt dat ik denk ...)

Het aantal niveaus waarop mensen recursief kunnen denken is beperkt, omdat van elk niveau een context in gedachten moet houden. Niemand kan tien niveaus met verschillende contexten en verbanden tussen die contexten goed bijhouden. Een oplossing daarvoor is inzien dat de contexten in softwareproblemen vaak grotendeels hetzelfde zijn en in plaats van alle losse contexten 1 unificatie/abstractie van de verschillende contexten in gedachten houden. De tussenliggende contexten kan je dan vergeten en het past weer binnen onze vermogen. Om dat te kunnen moet je het vermogen hebben om het verband tussen de situatie op diepte n en de situatie op andere diepten te zien. Zeker bij een abstract probleem als quicksort, betekent dat dat je een abstractie bovenop een toch al abstract probleem legt. Ik denk dat het daar in schuilt: niet iedereen slaagt er in om het verband tussen de contexten goed voor ogen te krijgen. Ik denk ook dat juist een algoritme als quicksort niet geschikt is om mensen recursie mee aan te leren

[hars73]

Op het moment dat je problemen met je programma hebt of een bug moet fixen, dan is een recursief programma soms wat moeilijker te debuggen. Maar over het algemeen is een recursief programma vaak de eenvoud zelve. Dat is nou net de kracht van recursief programmeren. Gewoon vaak doen, dan krijg je er vanzelf een gevoel bij en zie je hoe krachtig en effectief het kan zijn.

[Rukapul]

Tja, in de TS wordt het al gemeld:

Imperative programming is often a more natural and intuitive starting place for new programmers

Imperatief programmeren brengt al vrij snel een (tussen)resultaat, terwijl recursief programmeren toch vereist dat er eerst een mentaal beeld wordt gecreeerd. Wellicht kun je het vergelijken met de mensen die het concept invariant begrijpen en de mensen die het niet kennen. Als ik moet gokken dan vermoed ik dat mensen die recursie beheersen, ook elegantere lusconstructies schrijven.

[YopY]

Ben ik blij dat ik recursief programmeren snap, we kregen eigenlijk niks anders tijdens toetsen programmeren in het eerste en tweede jaar (in pascal en java). Hoge cijfers daarop, maar da's omdat het concept van recursie ergens wel logisch is. Zolang je het maar duidelijk voor jezelf houdt en het goed kunt visualiseren.

[MSalters]

Confusion schreef op dinsdag 11 maart 2008 @ 10:05:
[...]
Recursief denken is iets heel natuurlijks. Mensen gebruiken het op tenminste twee manieren:
1) Wanneer ze aan zelfreflectie doen.
2) Wanneer ze de bedoelingen van een ander proberen te doorgronden, rekening houdende met de kennis die die anderen van hen hebben. (Ik denk dat jij denkt dat ik denk ...)

Ik moet je teleurstellen. Recursie heeft een paar kenmerkende eigenschappen die in jouw voorbeelden ontbreken. De eerste is dat je de oplossing voor een deelprobleem uitbreidt naar een groter probleem, het tweede is dat je die methode onbeperkt kunt toepassen, en het derde is dat er een kleinste, triviaal probleem bestaat. Zelfreflectie heeft geen kleinste probleem, en hetzelfde geldt voor het doorgronden van een ander. Recursie is fundamenteel eindig.

Het aantal niveaus waarop mensen recursief kunnen denken is beperkt, omdat van elk niveau een context in gedachten moet houden.Niemand kan tien niveaus met verschillende contexten en verbanden tussen die contexten goed bijhouden.

Dat klopt, daarom zijn recursieve algoritmes niet geschikt om zelf dingen uit te rekenen.10 stackframes zijn simpelweg te complex.

Een oplossing daarvoor is inzien dat de contexten in softwareproblemen vaak grotendeels hetzelfde zijn en in plaats van alle losse contexten 1 unificatie/abstractie van de verschillende contexten in gedachten houden. De tussenliggende contexten kan je dan vergeten en het past weer binnen onze vermogen.

Je vergelijkt helaas appels en peren. Om een recursief algoritme te begrijpen hoef je geen 10 nivo's diep te redeneren. Er zijn namelijk geen tussenliggende contexten. Om het algoritme te begrijpen moet je alleen de stap van N naar N-1 zien.

Quicksort is een goed voorbeeld: Een array met 1 of 2 elementen is triviaal te sorteren, OK? Dat is je eindpunt. De volgende vraag is hoe je een array met N elementen sorteert. Ook dat is simpel: je kiest at random een element ("pivot"), en deelt je array in 2 subarrays op: groter en kleiner. Die sorteer je ook met quicksort (dit is je N-1 stap; elke subarray is hooguit N-1 groot.), n vervolgens zet je alles op een rijtje: klein-pivot-groot.

Er is dus helemaal geen context die je moet begrijpen halverwege N en 2. Maar als je het in je hoofd wil uitvoeren met 100 echte getallen, dan heb je wel een geheugenprobleem met al die contexten.

[Confusion]

MSalters schreef op dinsdag 11 maart 2008 @ 19:36:
Ik moet je teleurstellen. Recursie heeft een paar kenmerkende eigenschappen die in jouw voorbeelden ontbreken.

Als je recursie op een strict computerwetenschappelijke manier definieert, dan is die definitie niet van toepassing op een psychologisch verschijnsel. Maar dat concept is niet in de computerwetenschap uitgevonden en dat is niet de definitie van recursie. Er is sprake van dezelfde denktechnieken bij zowel het psychologische als het computerwetenschappelijke verschijnsel en dezelfde onderliggende verbanden (ik denk dat ik dacht dat ik hoorde..., ik dacht dat jij dacht dat ik zou denken...). Daarbij kan wel degelijk sprake zijn van kleiner wordende subproblemen: je denkt ergens over na en uit alles dat relevant is, focus je op een gedachte die je eerder had. In die gedachte, focuste je weer ergens op, etc.

Om het algoritme te begrijpen moet je alleen de stap van N naar N-1 zien.

Daarmee ben je er nog niet. Je moet ook begrijpen hoe het resultaat van stap N weer in N-1 gebruikt kan worden; welk deel van het probleem al opgelost is en welk deel nog opgelost moet worden. Het resultaat van N-1 gaat de context van stap N in; het is essentieel om te zien welk deel het daar van uitmaakt en welk deel van het uiteindelijke probleem het uitmaakt.

Er is dus helemaal geen context die je moet begrijpen halverwege N en 2.

Als dat alles zou zijn, dan zou recursie niet zo moeilijk zijn voor zoveel mensen.

[ Voor 8% gewijzigd door Confusion op 11-03-2008 21:54 ]

[Creepy]

Recursie is ook een niet moeilijk iets. Het concept is vrij simpel, als je tenminste snapt wat een functie aanroep is en doet en dat een functie die zichzelf aanroept niets anders is dan elke andere functie aanroept.

Wat ik vaak zie is dat er nogal wat verwarring is over het gebruik van de variabelen en parameters in recursieve functies. Maar als je snapt wat een stack (en heap) is en wat er gebeurd op de stack als je een functie aanroep doet dan is de werking van een recursieve functie simpel uit te leggen. Als je het concept van een stack al niet snapt (en er zijn helaas genoeg mensen die dat niet snappen) dan is het concept van een recursieve functie ineens een stuk moeilijker (en moeilijker uit te leggen). Helaas is dit een stukje basiskennis dat in een gemiddelde tutorial niet wordt meegenomen en erger nog: opleidingen die dit stukje basiskennis maar volledig overslaan.

Grappig ook wel dat het volgende stukje is gequote:

Recursive thinking is difficult because it almost seems like circular reasoning.

"seems like", maar recursie is dus niet een cirkel redenering, wat mij betreft verre van zelfs. Het is gewoon linear. Je laatste functie aanroep (op de stack) kan niet ineens naar de eerste functie aanroep (op de stack) dus er kan nooit een cirkel zijn.

[ Voor 18% gewijzigd door Creepy op 11-03-2008 23:27 ]

[Verwijderd]

Mijn eerste recursiepogingen waren ook niet bepaald efficiënt. Maar nadat je inductie hebt gehad en discrecte wiskunde en nadat het kwartje eenmaal gevallen is stelt het eigenlijk niet zoveel voor. Ik denk dat het wel de moeite waard is door te zetten. Het kan nooit in je nadeel werken als je hebt geleerd om op meerdere manieren tegen een bepaald probleem aan te kijken.

Op je oorspronkelijke vraag waarom het zo moeilijk is voor het brein, denk ik dat je het kunt vergelijken met wiskunde. Voor de één lastiger dan de ander en vaak even je gedachten in dezelfde manier duwen als het algoritme en dan stelt het opeens niet zoveel meer voor. Totdat je het weer een paar jaartjes niet gedaan hebt.

inductie is wel de moeite waard om te kijken. Het leidt je namelijk exact tot de juiste manier van denken. Doe een stap en gebruik daarbij het resultaat van de volgende stap. Dat resultaat is zelf precies hetzelfde, namelijk een stap wat iets doet met het resultaat van de volgende stap. Zolang je maar ergens een stopconditie komt dat dan vanzelf goed.

[RayNbow]

MSalters schreef op dinsdag 11 maart 2008 @ 19:36:
Recursie is fundamenteel eindig.

Het hangt waarschijnlijk af van je definitie van recursie. In de breedste betekenis van het woord is een recursieve definitie een definitie die zichzelf bevat.

Bijv. de volgende definitie is recursief.

code:

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

Maar de volgende definitie is ook recursief.

code:

fibs = 0 : 1 : zipWith (+) (tail fibs) fibs

De eerste definitie is alleen een functie en geeft voor een natuurlijk getal in een eindig aantal het bijbehorende Fibonacci getal. De tweede definitie is een definitie van een oneindige lijst (alle Fibonacci getallen).

[TGEN]

Marcj schreef op vrijdag 07 maart 2008 @ 15:53:
[...]

Idd. Zodra je een beetje leert omgaan met functionele programeertalen, wordt het recursief denken ook steeds makkelijker. Ik heb er iig geen enkele moeite meer mee. Sterker nog: ik vind het vaak veel leesbaarder dan een vage loop.

Wat ik zelf wel een nadeel vind is dat in veel imperatieve talen recursie niet heel bruikbaar is, omdat je dat niet zo diep kan doen. Terwijl het een heel krachtig middel is.

Tail recursion he, om je stack te sparen . Of een stackloze imperatieve taal gebruiken...

[ Voor 3% gewijzigd door TGEN op 12-03-2008 17:56 ]

[Marcj]

TGEN schreef op woensdag 12 maart 2008 @ 17:56:
[...]


Tail recursion he, om je stack te sparen . Of een stackloze imperatieve taal gebruiken...

Wat ik dan meestal doe is de recursie zelf al omzetten in een iteratie. Al vind ik in veel gevallen de recursieve manier makkelijker te begrijpen.

Om bijvoorbeeld een Depth First Search in Java te implementeren die diep moet kunnen zoeken, is recursie niet de meest efficiente manier.

Of kan de Sun JVM al tail recursion efficient aan?

[LauPro]

Ik denk niet dat recursie 'moeilijk' is, maar dat bij implementaties waar recursie verkeerd wordt gebruikt het wel moeilijk begrijpelijk kan zijn. Bijv. als er allemaal globale variabelen worden gevuld icm parameters.

En gezien de meeste talen waardeloos omgaan met recursieve functies die zich duizenden keren herhalen zit je ook nog eens met die beperking (en de workarounds).

[TGEN]

Marcj schreef op woensdag 12 maart 2008 @ 18:57:
[...]

Wat ik dan meestal doe is de recursie zelf al omzetten in een iteratie. Al vind ik in veel gevallen de recursieve manier makkelijker te begrijpen.

Om bijvoorbeeld een Depth First Search in Java te implementeren die diep moet kunnen zoeken, is recursie niet de meest efficiente manier.

Of kan de Sun JVM al tail recursion efficient aan?

Over de JVM durf ik geen positieve uitspraken te doen aangaande efficientie, maar in C kan het wel, praktisch inherent aan de ABI specs op de meeste/alle platformen.

[MSalters]

Wat heeft de JVM er mee te maken? Dat lost een compiler hopelijk op.

[Marcj]

Ik ga ervan uit dat de Java compiler zelf dit niet gaat oplossen, juist omdat deze niets weet over het doelsysteem. De JIT compiler van de JVM doet daarom ook de meeste optimalisaties, deze weet pas wat de meest efficiente oplossing voor een specifiek platform is.

Maar ik kwam net dit artikel tegen, waaruit blijkt dat de huidige versie dit nog niet ondersteund. En ook dat het toevoegen van deze optie aan de JVM niet meevalt.

[TGEN]

Marcj schreef op woensdag 12 maart 2008 @ 20:51:
Ik ga ervan uit dat de Java compiler zelf dit niet gaat oplossen, juist omdat deze niets weet over het doelsysteem. De JIT compiler van de JVM doet daarom ook de meeste optimalisaties, deze weet pas wat de meest efficiente oplossing voor een specifiek platform is.

Maar ik kwam net dit artikel tegen, waaruit blijkt dat de huidige versie dit nog niet ondersteund. En ook dat het toevoegen van deze optie aan de JVM niet meevalt.

Uit dat artikel blijkt echter wel dat de voor ogen staande implementatie vanuit de compiler is, waar de JVM alleen de stack frames hoeft op te ruimen e.d..

[curry684]

Ik snap niet echt waarom hier recursie als iets 'tegennatuurlijks' wordt omschreven?

Recursie is net zoals al het andere programmeerwerk op deze wereld perfect te begrijpen zolang je maar goed het onderscheid bewaakt tussen code en context. Who cares dat een stuk code zichzelf al dan niet via een omweg kan aanroepen, dat gebeurt gewoon binnen een andere context, net zoals dat geldt voor multithreaded programmatuur. In het ene geval zit je op een andere plek in je stack, in het andere heb je een andere stack. Boeie, andere context, zelfde code. How hard can it be?

[LauPro]

curry684 schreef op woensdag 12 maart 2008 @ 22:33:
Boeie, andere context, zelfde code. How hard can it be?

Toch blijft bij recursie het totale effect afhankelijk van een subcontext als het ware. Je moet dus meerdere contexten overzien daar waar je bij een niet-recursieve functies slechts 1 context/scope hebt (beetje open deur maargoed).

[Verwijderd]

Ik vind het maken van een recursief programma altijd makkelijker dan het begrijpen van een recursief programma van een ander. Mijn ervaring is dat je je zelf dit gewoon moet aanleren. Op mijn studie heb ik er best wel lang mee zitten ploeteren, maar op een gegeven moment had ik er helemaal geen moeite meer mee en tegenwoordig gebruik ik het voor alles en nog wat.

Meestal "probeer ik gewoon wat" en na 2 of 3 keer bijschaven werkt het dan. Als je het eenmaal door hebt gaat het bijna automatisch (bij mij dan iig).

[ Voor 7% gewijzigd door Verwijderd op 13-03-2008 02:41 ]

[franssie]

eeehhh, eerste post in dit forumdeel en ik probeer het te begrijpen.
Gaat het er nu om dat elk stukje code binnen zijn eigen (deel)wereld (parameters en variabelen etc) iets berekent/doet en dat dan teruggeeft aan een hoger niveau? (gosub^n)
Dat snap ik dan nog wel maar hoe structureer je dat toch zo dat je onverlet de terugkomst van de vorige (hogere) sub-routine weer juist verder gaat?
Sorry voor deze newby post in dit topic, mijn laatste en enige programmeer ervaring is in Z80 assembler en dat is ook al weer 25 jaar geleden (maar dat is vast een andere stack?).

Kan iemand een boek aanraden hierover?

[ Voor 4% gewijzigd door franssie op 13-03-2008 02:41 . Reden: layout en zo ]

[Verwijderd]

franssie schreef op donderdag 13 maart 2008 @ 02:36:

Kan iemand een boek aanraden hierover?

Ik denk niet dat de theorie moeilijk is, want het principe is simpel. Maar om het zelf succesvol te kunnen toepassen vereist een bepaalde manier van denken welke je alleen kan krijgen door zelf te oefenen. Een boek over recursief programeren lijkt me daarom ook niet heel erg nuttig.

[franssie]

Verwijderd schreef op donderdag 13 maart 2008 @ 02:55:
[...]

Ik denk niet dat de theorie moeilijk is, want het principe is simpel. Maar om het zelf succesvol te kunnen toepassen vereist een bepaalde manier van denken welke je alleen kan krijgen door zelf te oefenen. Een boek over recursief programmeren lijkt me daarom ook niet heel erg nuttig.

ok, een case dan? iets om de manier van denken te oefenen?

Ik ben zelf goed in wiskunde, maar dat is ook iets wat je moet 'zien' - als je het niet ziet haal je met veel moeite maximaal een 6 en als je het ziet haal je met gemak slapend een 6.

Dit lijkt mij net zoiets?

[Verwijderd]

Ja exact. Op het begin vond ik het moeilijk om een recursieve functie goed te begrijpen en nog steeds kijk ik wel eens scheef tegen zoiets. Het is gewoon lastig om van buiten af precies te zien waarom een recursieve functie werkt. Maar zodra je een bepaalde intuitie hebt opgebouwt kun je ze redelijk makkelijk uit je mouw schudden. Bij mij werkt het meestal niet de eerste poging, omdat het moeilijker is om te volgen dan bv een gewoon for-lusje maar na verloop van tijd wordt je er steeds handiger in om het goed te krijgen. Als ik eerlijk ben begrijp ik ook niet altijd precies waarom een door mij gemaakt recursieve functie werkt (dwz ik vind het lastig om 5 recursies diep te denken) maar dat is ook geen noodzaak. Wat voor mij sneller werkt is om het gewoon even op een verstandige manier te experimenteren tot je een goed eindresultaat krijgt.

Een simpel voorbeeld is de faculteit functie:

code:

int fac(int i)
{
    if(i == 0)
        return(1);
    else
        return(i*fac(i-1));
}


int main()
{
    cout << "fac6 = " << fac(3) << endl;
    return 0;
}

Wat hier in de code goed te zien is dat ik het "probleem" bij elke iteratie kleiner te maken tot je uiteindelijk bij het simpelste geval terecht komt. Conceptueel probeer ik me altijd iets voor te stellen als ik heb een bekende situatie voor n-1 en ik wil de situatie voor n berekenen, wat voor handeling moet je dan uitvoeren om vanuit de situatie bij n-1 uit te komen bij n. Vervolgens moet je dan nog voor een "basis geval" bepalen wat je moet doen en er voor zorgen dat je altijd (!) uitkomt in het "basis geval".

PS je kan ook omgekeer werken, stel ik zit bij n... hoe kom je dan terecht bij n-1 en dan als laatste nog even een basis geval bepalen.

(ik hoop dat het een beetje duidelik is, ik heb geprobeerd om het zo makkelijk mogelijk uit te leggen)

ALs ik terug denk aan hoe ik begon, is het misschien het beste om op het begin bij alles wat moeilijker is dan een super simpel voorbeeld niet helemaal te proberen te begrijpen wat een recursieve functie doet. Je kan het beter maar "geloven" en zodra je er de feeling voor krijgt kan je het ook makkelijker doorzien. Anders kan je vaak blijven steken als je het even niet ziet (en dat is zonde van je tijd).

[ Voor 18% gewijzigd door Verwijderd op 13-03-2008 03:39 ]

[Orphix]

Ik begrijp dat bovenstaande code een voorbeeld is, maar in het geval van f(-1) kom je dus in een oneindige recursie (in theorie) of een stack overflow (in de praktijk) en crasht je applicatie dus keihard. Nu is dit goed te doorzien, maar je kan je voorstellen dat het veel subtieler kan, bijvoorbeeld als je met userinput werkt. Dat je input niet helemaal is wat je verwacht (om wat voor redenen dan ook). Mijn ervaring is dat juist in recursieve functies je extra goed moet opletten op je input en output, en defensief moet gaan programmeren. Doe een sanity check en zorg dat je final context (waarin de recursie stopt) altijd plaatsvindt. Bij malifide input wil je snel falen ipv eerste zeer veel dure berekeningen uitvoeren voordat een overflow je op de fout wijst.

[Verwijderd]

Orphix schreef op donderdag 13 maart 2008 @ 12:32:
Ik begrijp dat bovenstaande code een voorbeeld is, maar in het geval van f(-1) kom je dus in een oneindige recursie (in theorie) of een stack overflow (in de praktijk) en crasht je applicatie dus keihard. Nu is dit goed te doorzien, maar je kan je voorstellen dat het veel subtieler kan, bijvoorbeeld als je met userinput werkt. Dat je input niet helemaal is wat je verwacht (om wat voor redenen dan ook). Mijn ervaring is dat juist in recursieve functies je extra goed moet opletten op je input en output, en defensief moet gaan programmeren. Doe een sanity check en zorg dat je final context (waarin de recursie stopt) altijd plaatsvindt. Bij malifide input wil je snel falen ipv eerste zeer veel dure berekeningen uitvoeren voordat een overflow je op de fout wijst.

Dat klopt helemaal, maar zelf vind ik het altijd prettig wanneer een programmeer voorbeeld zoveel mogelijk zich tot de kern beperkt van datgene wat het moet laten zien. Maar ik ben met je eens dat je wanneer je user-input op wat voor manier dan ook hebt dat je vooraf moet controleren of het programma er wel mee om kan gaan. Hoe raar de user input ook is, persoonlijk vind ik niet dat een programma er door hoort vast te lopen. Maar ik controleer de user input op een andere plek en geef dan een nette error als deze niet klopt. Dan hou je de controle en het "echte" programma een beetje gescheiden wat uiteindelijk overzichtelijker is. Wat ik soms ook wel doe is een exception gooien in een (recursieve) functie die controleert of de argumenten van de functie wel goed zijn, en dan het programma beeindigen wanneer er toch iets fout is met een interne error melding oid.

[ Voor 14% gewijzigd door Verwijderd op 13-03-2008 12:56 ]

[Verwijderd]

Als ik de comments lees lijkt het me eerder dat recursief programmeren niet moeilijk is. Maar door de meeste mensen wel als moeilijk wordt ervaren. Zelf vind ik het natuurlijke manier van werken, maar ik ken andere programmeurs die bij elke recursie roepen dat er een oneindige lus in de code zit en die recursie als iets *evil* aanschouwen. Ook in veel handboeken over diverse talen word er flink overdreven in de moeilijkheidsgraad van recursie, zo heb ik ooit een boek over C++ vast gehad dat letterlijk zei recursie niet te behandelen omdat het te moeilijk is. (Ok, het was zoiets van C++ voor 10-jarigen maar kom,..)

Aan de andere kant zie ik soms recursie om simpele lussen te doorlopen die ook met een gewone constructie kunnen gedaan worden, iemand een idee over de verschillen in performantie-stabiliteit hierover ?

Ik zie recursie als iets dat je kunt of je kunt het niet en binnen de "niet kunnen" heb je er die het kunnen leren en die het wellicht nooit zullen snappen.

Edit:
een situatie die veel mensen echt "confused" achterlaat is als een functie A een functie B of C aanroept, en die roepen elk weer A aan (maar dan wel met veranderende parameters) dan heb je ook recursie maar die is niet zo herkenbaar + gevoelig voor fouten + gewoon een rotte/bizarre logica in het programma

[ Voor 14% gewijzigd door Verwijderd op 13-03-2008 17:17 ]

[ACM]

Zoals al gezegd, recursie is helemaal niet moeilijk Het blijven gewoon functiecalls die nog eens hetzelfde zijn als het origineel. Wat recursie wat lastiger te doorgronden maakt is dat je niet in een simpele loop de nuttige code wordt uitgevoerd, maar dat de loop in de recurrente functie-calls verwerkt zit.
Wat echter de recursie echt moeilijk kan maken, is niet zozeer het feit dat het recursie is, maar dat het ingezet wordt voor de doorgaans wat complexere problemen. Het bekende voorbeeld Quicksort is gewoon niet heel makkelijk te doorgronden, maar de meest triviale recursieve versie is waarschijnlijk beter te doorgronden dan de meest triviale non-recursieve versie...

[.oisyn]

ACM schreef op donderdag 13 maart 2008 @ 17:11:
Het bekende voorbeeld Quicksort is gewoon niet heel makkelijk te doorgronden

Meen je dat nou? Ik wilde het eerder al zelf als voorbeeld nemen om aan te tonen dat recursie juist helemaal niet moeilijk is, maar heb dat niet gedaan omdat het wellicht een te simpel voorbeeld is.

Quicksort is juist een heel makkelijk te begrijpen recursieve functie, en bovendien elegant: Kies een willekeurige pivot, maak twee deellijsten waarvan de ene lijst elementen bevat die kleiner zijn dan de pivot, en de andere lijst de overige elementen (dus die groter zijn), en sorteer nu beide lijsten op dezelfde manier. En het resultaat is vervolgens: { de gesorteerde kleinere lijst; pivot; de gesorteerde grotere lijst }. En een lege lijst sorteren geeft natuurlijk een lege lijst - dit is de stopconditie.

[ Voor 5% gewijzigd door .oisyn op 13-03-2008 17:33 ]

[Orphix]

Verwijderd schreef op donderdag 13 maart 2008 @ 12:48:
Dat klopt helemaal, maar zelf vind ik het altijd prettig wanneer een programmeer voorbeeld zoveel mogelijk zich tot de kern beperkt van datgene wat het moet laten zien.

Begrijp ik. Ik nam je voorbeeld ook enkel als aanleiding

Maar ik controleer de user input op een andere plek en geef dan een nette error als deze niet klopt. Dan hou je de controle en het "echte" programma een beetje gescheiden wat uiteindelijk overzichtelijker is.

Prima, zolang je de daadwerkelijke recursieve functie dan maar private houdt Deze techniek kan natuurlijk niet altijd wanneer je bv over lijsten moet itereren die van buitenaf komen. Het vooraf checken hiervan is dan net zo tijdrovend als het daadwerkelijk uitvoeren van de recursieve functie.

Verwijderd schreef op donderdag 13 maart 2008 @ 16:38:
Edit:
een situatie die veel mensen echt "confused" achterlaat is als een functie A een functie B of C aanroept, en die roepen elk weer A aan (maar dan wel met veranderende parameters) dan heb je ook recursie maar die is niet zo herkenbaar + gevoelig voor fouten + gewoon een rotte/bizarre logica in het programma

Maar dat is geen recursie (zoals ik het zou definieren), maar circular dependency en is een erg sterke 'code smell'. Vaak kan dit opgelost worden door te refactoren naar een ander design waarbij de dependency niet circular is. Dit probleem is uiteraard wel zeer lastig, zo niet een van de meeste moeilijke problemen in software development: high-level interdependency kan voor zeer rotte, subtiele en moeilijk te traceren bugs zorgen.

[Confusion]

.oisyn schreef op donderdag 13 maart 2008 @ 17:29:
Quicksort is juist een heel makkelijk te begrijpen recursieve functie, [..]

Het ligt nogal aan de implementatie die gepresenteerd wordt. Als ik op de wikipedia pagina kijk, dan vind ik de eerste pseudocode glashelder (vrijwel identiek aan wat je hierboven zegt). De versie daaronder, degene die ik het eerst tegenkwam in mijn leven, vind ik nog steeds moeilijk te doorgronden.

[kenneth]

ACM schreef op donderdag 13 maart 2008 @ 17:11:
Het bekende voorbeeld Quicksort is gewoon niet heel makkelijk te doorgronden, maar de meest triviale recursieve versie is waarschijnlijk beter te doorgronden dan de meest triviale non-recursieve versie...

Kan je iedere recursie niet-recursief herschrijven? Los van de vraag of je dat wil

Ik ga dat artikel van developerWorks maar 'ns lezen, lang niet aan het ophalen van theorie gedaan, wel interessant onderwerp Waar trouwens hier meer over te vinden is

[Verwijderd]

Zoals eerder gezegd, recursie is niet zo heel moeilijk. Om het uit te leggen kan je het volgens mij het best vergelijken met Inductie, omdat de meeste mensen dit wel eens in een wiskunde boek hebben gezien. Feit blijft natuurlijk wel dat niet alle mensen inductie begrijpen...

Daarbij zijn de voorbeelden in een functionele taal zoals het fibonacci voorbeeld vaak het meest elegant.

[.oisyn]

Confusion schreef op donderdag 13 maart 2008 @ 18:13:
[...]

Het ligt nogal aan de implementatie die gepresenteerd wordt. Als ik op de wikipedia pagina kijk, dan vind ik de eerste pseudocode glashelder (vrijwel identiek aan wat je hierboven zegt). De versie daaronder, degene die ik het eerst tegenkwam in mijn leven, vind ik nog steeds moeilijk te doorgronden.

Maar wat vind je dan moeilijk: recursie, of het destilleren van een algoritmische beschrijving van een stuk code (waarin recursie gebruikt wordt, hoewel ik denk dat dit vrij weinig uitmaakt), waarin optimalisatiedetails verwerkt zitten?

Orphix schreef op donderdag 13 maart 2008 @ 17:49:
Maar dat is geen recursie (zoals ik het zou definieren), maar circular dependency en is een erg sterke 'code smell'.

Oh, dus als ik een recursieve quicksort omschrijf in deelfuncties is het ineens geen recursie meer . En is een recursieve functie die alleen zichzelf aanroept geen circular dependency?

kenneth schreef op donderdag 13 maart 2008 @ 18:20:
[...]
Kan je iedere recursie niet-recursief herschrijven? Los van de vraag of je dat wil

Dat ligt een beetje aan je definitie van recursie . Het concept 'stack' is voornamelijk belangrijk bij recursie, de top van de stack is je context. Naast een program-stack kun je natuurlijk net zo goed een eigen stack definieren (die vaak wat groter kan groeien dan de program-stack). Je hebt dan geen functie meer die zichzelf aanroept - dus geen recursie. Algoritmisch is er natuurlijk weinig veranderd, dus op zich is dat nog steeds recursie. Als in, je verdeeld het probleem nog steeds in deelproblemen die je op een gelijke manier oplost.

Wanneer is iets recursief, en wanneer is iets iteratief? Het faculteit-voorbeeld wat eerder werd aangehaald is bijvoorbeeld recursief geimplementeerd. Maar is dat voorbeeld eigenlijk wel recursief? Is het niet gewoon iteratief, waarbij in plaats van een loop structuur gebruik wordt gemaakt van een functie-aanroep?

[ Voor 53% gewijzigd door .oisyn op 13-03-2008 18:55 ]

[Verwijderd]

de som van iets is eigenlijk het makkelijkste voorbeeld.
1 + 2 + 3 + 4 + 5 reken je zelf uit door 1 + 2 = 3 te doen en vervolgens met de rest van de lijst opnieuw beginnen, namelijk 3 + 3 + 4 + 5. Dan doe je weer de eerste twee 3 + 3 is 6 en dan begin je weer opnieuw met je restant: 6 + 4 + 5. Dit wordt dan 10 + 5 en dat wordt 15.

Ofwel:
som :: [int] -> int //som is naam van de functie, [int] is een lijst getallen als input en -> geeft aan dat de output één getal is.
dan kunnen we vier situaties matchen:
som [] = 0 //lege lijst = 0
som [x] = x //er zit maar 1 getal in de lijst, dus uitput.
som [x,y] = x + y // maar twee getalen, simpel
som [x,y:xs] = som[x + y:xs] //2 getallen plus rest is de functie opnieuw uitvoeren over de lijst waarbij het eerste element van de nieuwe lijst de som van de eerste twee getallen zijn.

Ofwel, met recursie kun je exact je manier van denken volgen. Uiteraard kan xs ook voor een lege lijst staan, dus dit werkt ook

Clean:

som :: [int] --> int
som [] = 0
som [x] = x
som [x,y:xs] = som [x+y:xs]

//en uiteraard kan dit ook
som :: [int] -> int
som [] = 0
som [x:xs] = x+som xs
//immers we weten dat de som xs de som over xs uitrekend, dus de som over [x:xs] is slechts x plus de som over xs. Echter, nu laten we misschien onze denkwijze wat meer los en vertrouwen wat meer op de werking van de functie die we eigenlijk nog niet hebben kunnen testen

niet functionele benadering zou zijn

Java:

public int som(int[] input){
 int result = 0;
 for(int x : input){
   result += x;
  } 
}

Oftewel een variabele declareren, deze steeds aanpassen en terug geven wanneer klaar.
recursie/functionele programmeertaal freaks vinden dat rommelen met variabelen niks en al helemaal niet wanneer dat ook nog eens als de loop een variabele aan kan passen buiten die buiten zijn loop al geset is en daar wellicht nog aangepast kan worden (gelukkig werken we hier met primitieven... alhoewel, een array is een object).

[ Voor 21% gewijzigd door Verwijderd op 13-03-2008 20:39 ]

[Orphix]

.oisyn schreef op donderdag 13 maart 2008 @ 18:39:
Oh, dus als ik een recursieve quicksort omschrijf in deelfuncties is het ineens geen recursie meer . En is een recursieve functie die alleen zichzelf aanroept geen circular dependency?

Een stricte functie heeft geen eigen state en opereert enkel op de gegeven parameters. Een functie is ook compleet gespecificeerd (input->(..black box..)->output) op basis van deze data. Bij het type circular dependency waar ik op doelde, en die problematisch is, is de state wel van belang. Bij nader inzien zie ik dat de post waar ik op reageerde het ook enkel over functies had dus daar hoeft dit geen probleem te zijn. Maar wanneer je methodes hebt waarbij de aanroep invloed heeft op de state van het object zelf dan kan het problematisch worden. Dus als A een methode B.Method(A) aanroept, die op zijn beurt weer A.Method(B ) aanroept waarbij B zijn state verandert op basis van het resultaat van A.Method(B ), dan zie je al snel in dat dit potentieel fout kan gaan bij B.Method(A.Method(B.Method(A))). Bij een stricte functie heb je hier natuurlijk geen last en vandaar dat wiskunde zo lekker werkt.


In jouw voorbeeld van quicksort zal de functie in zijn eigen implementatie dus weer een call hebben naar quicksort terug, maar dit is wel een onderdeel van de gehele implementatie van jouw functie. Het gaat erom dat de implementatie van quicksort weet dat er een call naar zichzelf is, en hier ook weer afhankelijk van is voor een correcte werking. Dus A->B->A waarbij in de implementatie van A er enkel een expliciete call naar B staat is niet recursief. A->B->A waarbij B een interne functie is die weer A aanroept is wel recursief.

Ik denk dat onze interpretatie van de post anders is. Ik interpreteerde het als A->B->A waarbij in de implementatie van A enkel B staat en jij ervan uitgaat dat in de implementatie van A, B een interne deelfunctie is die weer A aanroept.

Van belang is dus op te merken dat enkel de implementatie recursief kan zijn (zoals je hierboven ook zegt). De functie interface zelf geeft geen recursiviteit aan.

Of je een recursieve functie implementatie ook circular dependent (ben ik zelf afhankelijk van mezelf?!) kan noemen weet ik niet, dit riekt al naar meta-fysische filosofie Ik zou het zelf niet op die manier aanduiden, ik vind dat er twee duidelijk verschillende entiteiten moeten zijn, maar wellicht dat een formele definitie hier wat stricter in is.

[RayNbow]

Orphix schreef op donderdag 13 maart 2008 @ 23:42:
[...]

Een stricte functie heeft geen eigen state en opereert enkel op de gegeven parameters. Een functie is ook compleet gespecificeerd (input->(..black box..)->output) op basis van deze data.

Iets als state kan je wel modeleren:

(input,state) -> (output,state)

Nadeel is alleen dat je het state argument telkens moet threaden (maar daarvoor zijn weer abstracties zoals de State monad).

[F-Tim]

Persoonlijk moet ik zeggen dat ik recursiviteit lastiger te doorgronden vindt dan 'normaal' programmeren omdat je achterstevoren moet denken.

Klein voorbeeldje; Stel je moet de lijst van 1 t/m N afdrukken, bij elke waarde deelbaar door 3 moet je achter het cijfer het woord "Bus" afdrukken, bij elke waarde deelbaar door 5 het woord "Vis". Deze kun je normaal en recursief oplossen. Bij normaal denk je van 1 tot 15, bij recursief van 15 naar 1, alhoewel ook dit op te lossen valt, maar dan krijg je een hardcoded eindwaarde. (In dit geval is de start van 1 bekend, en is de eindwaarde variabel, zodoende moet je ook omgekeerd denken!) Hieronder zal ik ff snel mijn interpretaties hiervan tonen:

Normaal:

C#:

        private static void RunRegular(int maxvalue)
        {
            for (int i = 1; i <= maxvalue; i++)
            {
                Console.Write("{0}", i);
                if (i % 3 == 0)
                    Console.Write(" Bus");
                if (i % 5 == 0)
                    Console.Write(" Vis");
                Console.WriteLine();
            }
        }

Recursief:

C#:

        private static void RunRecursive(int maxvalue)
        {
            if (maxvalue != 1)
                RunRecursive(maxvalue - 1);

            Console.Write("{0}", maxvalue);
            if (maxvalue % 3 == 0)
                Console.Write(" Bus");
            if (maxvalue % 5 == 0)
                Console.Write(" Vis");
            Console.WriteLine();
        }

Als iemand anders die code leest, is RunRegular in 1x duidelijk, terwijl bij RunRecursive de programmeur in kwestie vast 2/3x goed moet kijken. Misschien vinden mensen het dan wel niet zo 'netjes' om een extra variabele te declareren, maar uiteindelijk is dit wel leesbaarder.

Er zijn natuurlijk ook gevallen die recursief leesbaarder zijn, of zelfs niet normaal op te lossen zijn!
QuickSort is recursief vast beter leesbaar, daar geloof ik ACM blind in. Maar bv directory's met subdirs doorlopen is gewoon niet te doen zonder recursie; dir in dir in dir in dir in dir.... probeer dat maar eens niet recursief te doorlopen.... zeker niet als er dan de volgende run nóg een extra diepteniveau wordt toegepast.

Ik vind recursie dan ook een mooi idee/concept, maar ik vind ook dat het met mate gebruikt moet worden. Uiteindelijk is het belangrijker dat je code leesbaar en duidelijk is, niet dat je fancy technieken gebruikt die niet expliciet nodig zijn, but that's just my two cents. (En ja, soms is recursie leesbaarder, soms niet-recursief, dat is afhankelijk van de situatie.)

[ Voor 14% gewijzigd door F-Tim op 14-03-2008 09:12 ]

[Verwijderd]

Het is niet altijd het belangrijkst dat code leesbaar is. Soms is het belangrijker dat je wiskundig bewijs kunt overhandigen over de waarheid van je code. Een functionele taal met recursie kan je die garanties geven.
Het kromme denken is dat je je eigen functie aanroept alsware dat hij werkt terwijl je hem om dat moment nog aan het schrijven bent. Je gaat er bij de aanroep van uit dat hij werkt, maar hij werkt juist door die aanroep.

[.oisyn]

Orphix schreef op donderdag 13 maart 2008 @ 23:42:
[...]

Een stricte functie heeft geen eigen state en opereert enkel op de gegeven parameters. Een functie is ook compleet gespecificeerd (input->(..black box..)->output) op basis van deze data.

Zoals RayNbow al aangaf kan hij prima een state hebben, door de state de modeleren als een parameter. Maar dat terzijde. Ik snap je punt wel, maar ik vind dat je te kort door de bocht gaat. Zo ook hier:

Dus A->B->A waarbij in de implementatie van A er enkel een expliciete call naar B staat is niet recursief. A->B->A waarbij B een interne functie is die weer A aanroept is wel recursief.

Dit is in feite een tegenspraak. In A staat alleen een call naar B, dus hij is volgens jou niet recursief. Alleen als B een "interne" functie is die A aanroept is het ineens wel recursie. Alleen kun je aan A niet zien of B intern is of niet.

Natuurlijk snap ik ook wel dat een functie niet meteen recursief is als een functie op een willekeurig moment twee keer in een call stack voorkomt, en dat wil ik ook niet beweren. Maar je gaat in je uitleg nogal kort door de bocht, en dat is waar ik op reageer

[.oisyn]

F-Tim schreef op vrijdag 14 maart 2008 @ 09:08:
Persoonlijk moet ik zeggen dat ik recursiviteit lastiger te doorgronden vindt dan 'normaal' programmeren omdat je achterstevoren moet denken.

Daar maak je een denkfout. Je hoeft niet per se éérst de diepte in, en derhalve hoef je ook niet per se achterstevoren te denken.

Om je voorbeeld aan te houden:

C#:

        private static void RunRecursive(int maxvalue, int i = 0)
        {
            Console.Write("{0}", maxvalue);
            if (i % 3 == 0)
                Console.Write(" Bus");
            if (i % 5 == 0)
                Console.Write(" Vis");
            Console.WriteLine();

            if (i < maxValue)
                RunRecursive(maxvalue, i + 1);
        }

Je ziet hier overigens wel dat je een extra parameter nodig hebt, om de huidige positie bij te houden. Je deelt het nog steeds op in deelproblemen.

Maar bv directory's met subdirs doorlopen is gewoon niet te doen zonder recursie; dir in dir in dir in dir in dir.... probeer dat maar eens niet recursief te doorlopen.... zeker niet als er dan de volgende run nóg een extra diepteniveau wordt toegepast.

Nou doe ik die liever niet recursief, om performance (memory) redenen

C++:

void OutputFiles(const std::string & dir)
{
    std::list<std::string> queue;
    queue.push_back(dir);

    while (!queue.empty())
    {
        std::vector<File> files = GetFilesFromDir(queue.front());
        std::sort(files.begin(), files.end());

        queue.pop_front();
        std::list<std::string> iterator insertPos = queue.begin();

        for (size_t i = 0; i < files.size(); i++)
        {
            std::cout << files[i].GetFullPath() << std::endl;
            if (files[i].IsDirectory())
                queue.insert(insertPos, files[i].GetFullPath());
        }
    }
}

Maar idd, boomstructuren lenen zich bij uitstek voor recursie (het is dan ook een recursieve datastructuur).

[ Voor 8% gewijzigd door .oisyn op 14-03-2008 11:40 ]

[ACM]

.oisyn schreef op donderdag 13 maart 2008 @ 17:29:
Meen je dat nou? Ik wilde het eerder al zelf als voorbeeld nemen om aan te tonen dat recursie juist helemaal niet moeilijk is, maar heb dat niet gedaan omdat het wellicht een te simpel voorbeeld is.

Zie Confusion. De simpelste implementatie - de gene die jij hier verteld - is inderdaad een goed volgbare en elegante oplossing. De versie die geoptimaliseerd is voor geheugen-ruimte is echter een stuk lastiger, omdat je dan niet meer met echte deellijsten werkt, maar met "pointers" naar de delen. En de non-recursieve versie met bijvoorbeeld een stack (kan het anders?) is ook lastiger dan die triviale recursieve versie.

.oisyn schreef op donderdag 13 maart 2008 @ 18:39:
Maar wat vind je dan moeilijk: recursie, of het destilleren van een algoritmische beschrijving van een stuk code (waarin recursie gebruikt wordt, hoewel ik denk dat dit vrij weinig uitmaakt), waarin optimalisatiedetails verwerkt zitten?

De vraag die je hier stelt is precies mijn punt

kenneth schreef op donderdag 13 maart 2008 @ 18:20:
Kan je iedere recursie niet-recursief herschrijven? Los van de vraag of je dat wil

Vziw wel, maar zie .oisyn over hoe je dat afhangt van je definitie van recursie. Als je puur wilt voorkomen dat een functie opnieuw aangeroepen wordt binnen de context van die functie, dan wel. Maar als je recursie ziet als iets in deelproblemen opsplitsen en de daadwerkelijke implementatie minder relevant ervoor vindt... QuickSort is bijvoorbeeld gewoon een recursief algoritme. Op het moment dat je daar een niet-recursieve versie van maakt, is het dan nog wel QuickSort? Of is het dan een ander algoritme dat dezelfde vergelijkingen maakt als QuickSort?

[.oisyn]

ACM schreef op vrijdag 14 maart 2008 @ 12:29:
Op het moment dat je daar een niet-recursieve versie van maakt, is het dan nog wel QuickSort? Of is het dan een ander algoritme dat dezelfde vergelijkingen maakt als QuickSort?

Interessant. Is het niet zo dat als het altijd dezelfde vergelijkingen maakt als een bepaald algoritme, het in feite gewoon exact datzelfde algoritme is? Maar dit wordt denk ik te filosofisch

[ Voor 4% gewijzigd door .oisyn op 14-03-2008 12:36 ]

[Verwijderd]

ACM schreef op vrijdag 14 maart 2008 @ 12:29:
[...]. QuickSort is bijvoorbeeld gewoon een recursief algoritme. Op het moment dat je daar een niet-recursieve versie van maakt, is het dan nog wel QuickSort? Of is het dan een ander algoritme dat dezelfde vergelijkingen maakt als QuickSort?

Zonder uit te willen wijken: dit lijkt me een geval voor copyright/patent kwesties, als ik het zelfde principe volg maar op een net iets andere manier dan schend ik geen copyright/patent (naar mijn mening)

[TGEN]

Verwijderd schreef op vrijdag 14 maart 2008 @ 13:16:
[...]


Zonder uit te willen wijken: dit lijkt me een geval voor copyright/patent kwesties, als ik het zelfde principe volg maar op een net iets andere manier dan schend ik geen copyright/patent (naar mijn mening)

QuickSort is (gelukkig) niet patenteerbaar. Imho is een non-recursieve iteratieve implementatie van het quicksort-algoritme nog steeds quicksort; inductie/recursie hoeft niet perse met recursieve functiecalls gemodelleerd te worden, alhoewel het soms flink lastiger kan zijn om zelf alles bij te houden wat anders stack frames voor je zouden doen als je een recursieve implementatie omzet naar puur iteratief.