Python suite de Fibonacci

Ton argumentaire est pêté pour plein de raison, mais je ne vais m’attarder que sur une:

concrètement personne n’a rien à péter de cette fonction

En effet, pas plus que la fonction d’Ackerman pour ce que ça vaut.

Par contre, l’avantage d’une telle fonction (au delà du fait, qu’en vrai, elle a des applications !) c’est qu’elle est facile à comprendre, simple à coder et qu’il est relativement facile de comprendre comment l’améliorer. Même ce que tu défini comme une faiblesse (ça marche pas pour les "grandes" valeurs, temps de calcul exponentiel) est pédagogiquement intéressant (puisque ça permet de rappeler qu’un ordinateur fonctionne avec des nombres de taille finie, et que oui, les grands principes généraux, ça reste du cas par cas). Les fameux "exemples motivant", c’est génial, mais pour des raisons de temps, tu te retrouve toujours à simplifier le problème à l’extrême, ce qui fait que ça n’a plus grand chose à voir avec la réalité et que pour le coup, Fibonacci fera tout aussi bien.

Pour prendre un cas similaire, c’est comme si, dans un cours dédié aux compilateurs, bah tu vois comment traiter une expression mathématique en ne voyant que comment gérer l’addition et la multiplication: ça sert à rien (erreur 1), aucune raison d’apprendre à faire autrement (erreur 2) et en vrai c’est probablement pas géré par des véritables compilateurs qui doivent utiliser des règles autrement plus complexes pour gérer les autres opérations, les parenthèses, etc (erreur 3)

Je n’ai pas l’impression que tu aies compris de quoi je parlais. Je ne dis pas que la fonction factorielle ou fibonacci soit difficile à coder récursivement. Au contraire.

Je dis que quand elle arrive dans un cours de programmation comme exercice de programmation récursive après avoir servi d’exemple pour la programmation impérative, ça fait un gros bide, pour les raisons indiquées. Parce qu’à ce moment-là, les apprenants ne veulent se lancer dans de nouveaux trucs uniquement quasi ça leur permet de faire des trucs nouveaux qu’ils ne voient pas comment faire (facilement) autrement.

Un bon exemple ça serait explorer un répertoire. Récursivement c’est très facile, avec des boucles faudrait gérer une pile, on n’est pas sorti de l’auberge surtout quand on n’a pas encore abordé la notion de pile .

D’où la question, pourquoi on ne dégaine pas plus souvent cet exemple ? Une explication, c’est le background souvent matheux de ceux qui enseignent, qui ramènent "par facilité" la récursivité à la récurrence dans N. Parler de fichiers et de répertoires, ça voudrait dire sortir de ce cadre, parler de l’API des système de fichiers, par exemple.

Il y a très longtemps, les cours de Prolog prenaient comme exemple l’arithmétique de Peano, on programmait les opérations arithmétiques sur des termes construits comme successeurs de 0. C’est très amusant quand on est enclin à ce genre de trucs. Pour les autres, la conclusion, c’est que Prolog était un langage tordu où c’est le bordel pour faire des calculs. Conclusion certes hâtive et erronée, mais clairement c’était l’impression laissée à la majorité.

En plus si c’est pour profiter de l’initiation à la programmation récursive pour venir exposer les les emmerdements éventuels qui sont de fait communs à toute programmation (temps de calcul, débordement de pile etc), si ça s’appelle pas se tirer une balle dans le pied pour la pédagogie ?

Je pense que tu devrais prendre la peine d’expliquer les autres raisons qui font que mon argumentaire serait tout pété, parce là "on prend fibonacci parce que c’est un exemple simple, et que pédagogiquement les nombres sont plus finis avec des calculs récursifs qu’avec d’autres", c’est pas convaincant.

Je pense qu’il y a plusieurs points sur lesquels ont est pas d’accord.

Premièrement, la pédagogie. Pour moi, la pédagogie, c’est pas cacher la difficulté sous le tapis. En l’occurrence, aucune approche (impératif, récursif, fonctionnel, que sais-je) n’est LA réponse, puisque ça dépend du problème: comme tu le dis très bien, certains problèmes se traitent très bien en récursif, d’autre moins. Donc pour moi, présenter les différentes approches en pointant leurs forces et leurs faiblesses, c’est pas se casser la baraque tout seul en montrant que le truc qu’on enseigne, ça fait pas le boulot, c’est plutôt ouvrir les yeux de l’étudiant sur le fait que l’approche en question a ses limites (et si le prof est malin, il aura également parlé des limites d’une approche impérative).

Deuxièmement, les exemples motivants. Je ne nie pas qu’appliquer l’approche récursive à un truc plus sexy que ce bon vieux fibo() peut être plus motivant pour les étudiants. Néanmoins, l’exemple que tu donne (les systèmes de fichier) démontre bien ce que je dit dans mon message précédent: la quantité de notions que tu dois aborder avant de pouvoir dérouler ton exemple (ici, essentiellement l’API de fichier UNIX¹) est, je pense, démesurée par rapports aux objectifs du cours, qui sont généralement d’apprendre l’algorithmique. Encore une fois, et sans prétendre que fibo() est le meilleur exemple pour ça, je pense que sont avantage est d’être extrêmement simple à expliquer, ce qui permet de passer du temps sur le but du cours: l’algorithmique.

Troisièmement, "les maths". J’entends très bien que les maths, c’est pas le délire de tout le monde. Sauf que c’est encore une fois oublier l’objectif du cours. Me concernant, le contexte sous-jacent, c’était le cours d’algorithmique, donc d’une part la complexité algorithmique de telles approches, et d’autre par la preuve de programme. Dans les deux cas, c’est triste à dire, mais ça s’explique plus facilement en manipulant des nombres (et à fortiori des entiers). Je ne pense donc pas que [les profs] qui ramènent "par facilité" la récursivité à la récurrence dans N le font par plaisir, sadisme ou je ne sais quoi d’autre, mais au contraire pour commencer par des exemples "simples" dont les preuves sont faciles à comprendre.² Par ailleurs, tu noteras que pour en arriver à la conclusion que Fibonacci possède une solution en temps constant (impliquant, donc, le nombre d’or), il faut en faire, des maths

Pour toutes ces raisons, j’ai l’impression que tu t’acharne sur la suite de Fibonacci comme étant un mauvais exemple, pas du tout motivant, déconnecté de la réalité, etc là ou le but de ceux qui utilise cette suite est totalement différent (ça n’est pas fait pour être motivant, c’est fait pour être simple et qu’on puisse se concentrer sur autre chose, genre, par exemple, le cours³).

PS: à toutes fins utiles, je tiens à rappeler que cette fameuse suite de Fibonacci ne sert pas à rien et apparait, par exemple, à différents endroits quand on s’amuse à jouer avec des arbres. Donc, et en étant un peu taquin, je pourrai dire que même l’exemple du système de fichier (qui, quand on le regarde en clignant un peu des yeux, est un arbre) est un mauvais exemple

Soyons brefs

Pour toutes ces raisons, j’ai l’impression que tu t’acharne sur la suite de Fibonacci comme étant un mauvais exemple, pas du tout motivant,

Il se trouve que c’est le sujet. Que j’ai un peu élargi à la manière habituelle d’aborder la récursivité avec les débutants (ce qui fut en partie mon job en IUT pendant 37 ans, en gros)

Néanmoins, l’exemple que tu donne (les systèmes de fichier) démontre bien ce que je dit dans mon message précédent: la quantité de notions que tu dois aborder avant de pouvoir dérouler ton exemple (ici, essentiellement l’API de fichier UNIX1) est, je pense, démesurée par rapports aux objectifs du cours, qui sont généralement d’apprendre l’algorithmique

• Pas spécifiquement l’API Unix, on peut dire ça de tout machin qui se modélise par des termes.
• ceci dit, j’enseignais à des gens qui étaient censés aller bosser ensuite, donc c’était préférable d’ancrer fermement les concepts dans des situations concrètes.
• si la partie "programmation récursive" n’est pas applicable aux vrais problèmes qui se posent aux débutants au moment où c’est abordé, c’est que ce n’est pas le moment de l’aborder. Et que ça risque d’être plus un obstacle à la compréhension du reste (on ne peut pas être au four et au moulin, ni gaspiller des heures qui sont en nombre forcément limité, etc ). Mais bon, au moment des tris de tableaux, on a certainement des occasions.

je tiens à rappeler que cette fameuse suite de Fibonacci ne sert pas à rien

Certes, tout ce qui existe a certainement une utilité quelque part. Mais dans ce cadre, je voudrais bien que tu me dises quelle est l’utilité spécifique de cette suite. et pourquoi pas les nombres de Catalan ? Les coefficients de Bernouilli ?

J’ai l’impression que tu insiste sur le côté "pratique" de la chose (en gros, tout ce qui est expliqué doit avoir une utilité), là ou je te parle du côté "conceptuel" de la chose (en gros, pour moi, l’exemple est moins important que le concept qu’il y a derrière, donc les exemples artificiels ne me dérangent pas). Je comprend ton point de vue, mais je ne le partage pas.

Mais dans ce cadre, je voudrais bien que tu me dises quelle est l’utilité spécifique de cette suite.

Si je ne dis pas de bêtises, il s’agissait d’arbres balancés et des calculs de complexité algorithmiques associés (profondeur maximale, etc). De manière générale, quand tu commence à compter des éléments (feuilles, nœuds, etc) dans ce genre de structure … Ça fini en suite

et pourquoi pas les nombres de Catalan ? Les coefficients de Bernouilli ?

Encore une fois, j’ai pas dit que Fibonacci était le meilleur exemple, je dis juste que ce n’est pas aussi déconnecté de la réalité que ça n’en a l’air. Par exemple, et puisque tu en parles, regarde la section arbres binaires de la page Wikipédia sur les nombres de Catalan ! Pour le coup, c’est concret (nombre possible d’arbres binaires, soit une super structure de donnée pour plein de trucs) et ça a des applications assez évidentes.

Le truc, c’est que ce genre de suite, qui ont l’air très artificielles quand elles sont énoncées en terme mathématiques sur leurs pages Wikipédia respectives ou dans tout les bouquins de maths, apparaissent en fait dans plein d’exemple (de dénombrement, en l’occurrence) qui finissent toujours par arriver à des endroits ou on les attend le moins (les bases de données, le machine learning, les problèmes d’optimisation … Des trucs très concrets quoi). Sauf qu’encore une fois, je suis convaincu qu’il ne faut pas attendre d’avoir vu les bases de données, l’API UNIX, ou je ne sais quoi d’autre pour expliquer un truc aussi simple que la récursivité.

Bref, je pense qu’on est d’accord de ne pas être d’accord. Je propose qu’on évite de pourrir le topic là dessus

Dans mes études, j’ai eu ces deux types de profs :

• Ceux qui enseignaient en mode « Aujourd’hui on va apprendre la programmation récursive. Ça sert par exemple à calculer la suite de Fibonacci. Voici comment on calcule cette suite de façon récursive… »
• Ceux qui enseignaient en mode « Aujourd’hui on va apprendre la programmation récursive. Ça sert à [plein d’exemples concrets ici]. Pour le premier exemple j’ai besoin d’un cas simple, alors on va prendre la suite de Fibonacci, en plus on peut facilement vérifier si ça fonctionne bien ou pas. Voici comment on peut faire… ».

Ça ne change à peu près rien à la suite du cours ; pourtant, la seconde façon de faire est beaucoup plus intéressante. Et pourtant il y avait des profs complètement coincés dans la première, pour lesquels tout n’était que pure théorie, sans jamais aucune application pratique. Le pire qui me revienne à l’esprit, c’était un cours sur les SGBD, dans lequel on a appris toutes les formes normales, les calculs de complexité, de temps de réponse et de consommation de ressources… mais dans lequel il n’a jamais été question ni de l’utilité d’un SGBD, ni de la moindre requête SQL réelle.

Comment, on ne vous pas montré l’équivalence entre le modèle relationnel et le modèle algébrique (où les opérations sont des combinaisons de projections, sélections etc) ? Ni la complétude des axiomes d’Armstrong ?

Pour revenir là dessus

Sauf qu’encore une fois, je suis convaincu qu’il ne faut pas attendre d’avoir vu les bases de données, l’API UNIX, ou je ne sais quoi d’autre pour expliquer un truc aussi simple que la récursivité.

Mais j’en suis également convaincu. Le point que que soulignais, c’est que c’est souvent très mal fait à cause du choix des exemples qui sont des repoussoirs plutôt que des motivations alléchantes dont on imagine facilement qu’elles apportent des solutions évidentes à des problèmes courants. Entre l’intention (louable) et la réalisation, il y a de la marge.

Pour ne pas faire une fixette sur fac, fib et ack, on peut aussi taper "exercice récursivité" sous google et constater (en soupirant) qu’on trouve hélas "calculer la taille (ou la somme) d’un tableau", "tester si un entier positif est pair", … toutes choses que le débutant, sans y trouver d’intérêt, sait déjà faire autrement.

Malgré le léger déterrage, veillez à ne pas trop faire dévier le sujet svp (libre à vous de créer un sujet sur la pédagogie en illustrant par cet exemple).