Recursie & slechte voorbeelden
Als je een typische informatica afgestudeerde van Kerala naar nummer een programma schrijven om af te drukken van de n-de Fibonacci, de meesten van hen zal steevast * geeft u de volgende functie:
Fibonacci int (int n) ( if (n <2) ( terug n; Else () terug Fibonacci (n-1) + fibonacci (n-2); ) )
Tot zover is alles goed, behalve dat het antwoord fout is.
Recursie is de slechtste manier om een Fibonacci getal te vinden. De laatste keer dat ik keek was het onmogelijk om recursie te gebruiken om te berekenen, zelfs de 50 e Fibonacci getal in een personal computer!
Indien het onmogelijk is om de functie berekent zelfs de 50 e Fibonacci getal met behulp van dit, hoe kan je eventueel iets te leren, zoals dit op een informatica opleiding? De enige manier Fibonacci getallen moeten worden berekend door de getallen lineair toe te voegen in een lus of door het gebruik van een directe formule die je hebt. Natuurlijk voor sommige toepassingen kunt u versnellen door het onthouden van de recursie kind nodes in de boom en zich daardoor onttrekken om hetzelfde te doen berekeningen weer in een andere branche.
Het griezeligste deel moet nog komen. In veel scholen gebruiken ze het vinden van de n-de Fibonacci getal als de primaire bijvoorbeeld voor het onderwijs recursie!
Waarom niet leren studenten de best mogelijke manier te vinden n th Fibonacci getal? Waarom niet leren een echte wereld bijvoorbeeld voor recursie? Is het nodig om les te geven van de begrippen in de informatica met slechte voorbeelden?
* Neem deken uitspraken met een korreltje zout.
Goed gezegd. Ik weet niet meer hoe ik was recursie geleerd - maar ik denk dat het was faculteiten. Hoewel het kan worden gedaan met een simpele lus, faculteit is een goed voorbeeld van recursie te introduceren aan een student geloof ik.
Btw, hier bereikt van SO - waar is de upvote knop?
Hoewel ik het ermee eens dat recursie niet de juiste manier om een Fibonacci getal te vinden, moet ik zeggen gebruiken om recursie te leren is een goed idee. Vanwege zijn eenvoudige. Makkelijk om het concept te krijgen door middel van dit voorbeeld.
De meest voorkomende echte applicatie voor recursie is om te lopen via een boomstructuur. Dat voorbeeld zal worden gecompliceerd. Ook zul je voor een goed begrip van bomen en spullen voor de hand.
Dan weer, kan er een eenvoudige, maar echte wereld bijvoorbeeld dat ik nog niet van bewust. Als iemand weet van een, laat het me weten.
Binny,
Zoals Amarghosh opgemerkt, faculteit is een goed voorbeeld.
Een ander voorbeeld is zeer eenvoudig worden toegevoegd:
add(0, x) = x,add(n, x) = add(n-1, x) + 1
Voor zover ik weet dit voorbeeld wordt vaak gebruikt in de informatica opleidingen in veel goede universiteiten over de hele wereld.
Ik denk dat Fibonacci moet worden onderwezen als een voorbeeld van slecht gebruik van recursie. Natuurlijk is het punt is dat er een enorme tijd-ruimte-trade-off in het gebruik van recursie en die correct moeten worden onderwezen.
Het eerste ding: stoppen met te denken dat degenen die te maken syllabus / curriculum zijn dwazen of verouderd zijn, ze weten meer dan je in programmeren (ik verwijs naar degenen die syllabus en curriculum niet uw docent aan coll)
Het tweede ding: Voordat waarderen denk zelfs niet een keer, maar voor kritiek denk dat duizend keer.
Derde ding: Zoeken op Google, Wikipedia Verwijs en vervolgens na wat je voelt, dat wil zeggen. als je tech blog.
Vierde punt: Fibonacci is inherent recursief, vinden wat recursie is in de wiskunde, herhaling relaties en recursieve functies.
Vijfde punt: ik heb alle van de bovengenoemde fouten mezelf. Houd rockende dude!
sabithpocker,
Hoewel de definitie van Fibonacci is recursief, maar dat betekent niet dat je kunt Fibonacci-getallen te berekenen met behulp van recursie.
Terwijl de beste algoritme voor de generatie van de Fibonacci-reeks is niet een recursieve algoritme, de Fibonacci-reeks is nog steeds een zeer goed voorbeeld voor het uitleggen van recursie. Voor mensen die recursie te zien voor de eerste keer, het is iets heel eenvoudig te visualiseren en heeft een laag genoeg aantal recursieve oproepen te maken het tekenen van de recursie-boom haalbaar is.
De manier waarop ik heb het gezien onderwezen in verschillende plaatsen die gewoonlijk zal de Fibonacci-reeks te gebruiken als een segue in dynamische programmering en memoization. Omdat de recursieve algoritme is zo verschrikkelijk, het maakt een uitstekend voorbeeld van hoe de prestaties drastisch kan worden verbeterd door het voorkomen van dubbele oproepen.
Factoriële en bovendien niet lenen voor een dergelijke segue, en zijn daarom minder vaak gebruikt. Ook wanneer het doen van inleidende cursussen programmeren - het doen van factoren zal veel sneller worden beperkt door de capaciteit van de gehele getallen dan zal worden door de computationele complexiteit.
We zijn niet bezig om 'Berekenen' Fibonacci-getallen met de computer .. zijn wij?
Wij zijn in plaats het bestuderen van een concept genaamd "recursie".