Et mauvais exemples récursivité
Si vous demandez à une informatique diplômé typique du Kerala pour écrire un programme pour imprimer le n e nombre de Fibonacci, d'entre eux * la plupart seront toujours vous donner la fonction suivante:
int fibonacci (int n) ( if (n <2) ( n retour; ) Else ( Fibonacci retour (n-1) + de Fibonacci (n-2); ) )
Jusqu'ici tout va bien, sauf que la réponse est fausse.
La récursivité est la pire façon de trouver un nombre de Fibonacci. La dernière fois que j'ai vérifié qu'il était impossible d'utiliser la récursivité pour calculer même les 50 ème nombre de Fibonacci dans un ordinateur personnel!
S'il est impossible de calculer, même les 50 ème nombre de Fibonacci en utilisant cette fonction, comment avez-vous pu apprendre quelque chose comme cela dans un cours d'informatique? La seule façon de nombres de Fibonacci doit être calculé de façon linéaire est par adjonction des numéros dans une boucle ou par n'importe quelle formule directe que vous avez. Bien entendu, pour certaines applications, vous pouvez accélérer la récursivité en se rappelant les nœuds enfants dans l'arbre et ainsi éviter de faire les mêmes calculs à nouveau dans une autre branche.
Le plus effrayant est encore à venir. Dans de nombreux collèges qu'ils utilisent trouver le n e nombre de Fibonacci comme le principal exemple de récursivité d'enseignement!
Pourquoi ne pas enseigner aux élèves la meilleure façon possible pour trouver le n e nombre de Fibonacci? Pourquoi ne pas enseigner un exemple concret de la récursivité? Est-il nécessaire d'apprendre les notions en informatique en utilisant des exemples moche?
* Prendre des déclarations couverture avec un grain de sel.
Bien dit. Je ne me souviens pas comment j'ai appris la récursivité - mais je crois que c'était factorielles. Même si cela peut se faire avec une simple boucle, factorielle est un bon exemple d'introduire la récursivité à un étudiant, je crois.
Btw, atteint ici des SO - où est le bouton upvote?
Même si je conviens que la récursivité n'est pas la bonne façon de trouver un nombre de Fibonacci, je dois dire que l'utiliser pour enseigner la récursivité est une bonne idée. Parce que son simple. Facile à obtenir le concept à travers cet exemple.
L'application la plus courante du monde réel pour la récursivité est de marcher à travers une structure arborescente. Cet exemple va être compliqué. Aussi, vous devez avoir une compréhension des arbres et des trucs avant main.
Et puis, il peut être un simple, mais l'exemple du monde réel que je ne suis pas encore au courant. Si quelqu'un sait de l'une, faites le moi savoir.
Binny,
Comme Amarghosh souligné, factorielle est un bon exemple.
Un autre exemple très simple est plus:
add(0, x) = x,add(n, x) = add(n-1, x) + 1
Pour autant que je sais cet exemple est souvent utilisé dans les cours d'informatique dans de nombreuses excellentes universités à travers le monde.
Je pense que Fibonacci devrait être enseignée comme un exemple pour mauvaise utilisation de la récursivité. Bien sûr, le fait est que il ya un temps énorme espace de compromis dans l'utilisation de la récursivité et qui doit être enseigné correctement.
Première chose: Arrêtez de penser que ceux qui font syllabus / programme sont des imbéciles ou obsolètes, ils savent plus que vous dans la programmation (je me réfère à ceux qui font programme des cours et non votre maître de conférences à Coll)
Deuxième chose: avant d'apprécier crois pas une seule fois, mais avant de critiquer pense mille fois.
Troisième chose: Recherche Google, Wikipedia Reportez-vous et puis après ce que tu ressens, c'est à dire. quand vous faites blog technologique.
Quatrième point: Fibonacci est intrinsèquement récursifs, trouver ce qui est la récursivité en mathématiques, des relations de récurrence et de fonctions récursives.
Cinquième point: j'ai fait toutes les erreurs mentionnées ci-dessus moi-même. Gardez à bascule dude!
sabithpocker,
Même si la définition de Fibonacci est récursive, cela ne signifie pas que vous pouvez calculer les nombres de Fibonacci en utilisant la récursivité.
Alors que le meilleur algorithme pour la génération de la séquence de Fibonacci n'est pas un algorithme récursif, la suite de Fibonacci est encore un exemple très utile d'expliquer la récursivité. Pour les personnes qui voient la récursivité pour la première fois, c'est quelque chose de très facile à visualiser et a un nombre assez faible des appels récursifs à rendre le dessin de l'arbre récursivité possible.
La manière que j'ai vu il a enseigné dans divers endroits normalement utiliser la séquence de Fibonacci comme segue dans la programmation dynamique et memoization. Parce que l'algorithme récursif est si terrible, il est un excellent exemple de la façon dont le rendement peut être considérablement améliorée par la prévention de double appel.
Factorielle et plus ne se prêtent pas à une telle segue, et sont donc moins fréquemment utilisés. Aussi, lorsque vous faites des cours de programmation d'introduction - faire factorielle sera limitée beaucoup plus tôt par la capacité d'entiers que ce sera par la complexité des calculs.
Nous ne cherchons pas à 'Calculer' nombres de Fibonacci en utilisant l'ordinateur .. sommes-nous?
Nous sommes plutôt l'étude d'un concept appelé «récurrence».