1) Ouvre n'importe quel bouquin de niveau licence/maîtrise pour faire de l'algo.
2) Choisis les chapitres concernant les graphes et les arbres plus particulièrement.
3) Prends un algo au hasard.
4) Surprise ! L'algo est récursif. Et c'est carrément « naturel » de penser ainsi, soit dit en passant. L'alternative itérative est beaucoup moins facile à imaginer.
5) Réessaie avec le chapitre sur les tris efficaces (pire cas ou cas moyen). Retourner en 4 pour la conclusion.
Il faut évidemment nuancer tout ça : si l'algo en question est récursif terminal, il existe une version équivalente itérative, et on peut même s'amuser à automatiser la transformation (certains compilateurs le font dans les cas assez simples).
Par contre, une chose est certaine : autant l'approche récursive est tout à fait naturelle dans certaines structures de données (les structures ... récursives, tiens donc !), autant, pour un langage comme le C, la récursivité peut faire très mal (surtout si elle n'est pas terminale).
Moralité : il faut des mecs super balaises en algo/prog C pour élaborer des algos itératifs pour gérer les cas (cf. la glibc, par ex), sinon il y a risque de faire exploser la pile des variables automatiques.
Corollaire : les programmeurs « moyens » utilisent des structures de données comme on le leur a dit, sans vraiment leur expliquer comment elles fonctionnent, et du coup bousillent totalement les perfs d'un programme. Par exemple, ils ont l'habitude d'utiliser des listes d'éléments (en Java, C#, que sais-je), et n'ont jamais entendu parler des arbres rouge-noir (pourtant implémentés en tant que TreeMap en Java par ex). Résultat : ils vont se faire chier à faire des sortes de « tri par insertion » sur une liste, plutôt que d'utiliser une structure spécifiquement élaborée pour ce genre de cas.
Maintenant, un langage fonctionnel a beau avoir une approche plus « mathématique » de la programmation (pour la forme), je pense avoir eu autant de mal au début à comprendre comment faire des boucles for/while/do-while en Perl/C qu'à faire des récursions en LISP pour la première fois. Non, pire. Ca avait été plus dur, car comme on m'avait relativement bien formé à C, on n'avait cessé de me répéter : « la récursivité, c'est le Mal » (à cause du passage des paramètres par valeur, etc). Donc j'étais bien endoctriné.
[^] # Re: bof
Posté par lasher . En réponse à la dépêche 23 mars: Conférence au LORIA sur Lisaac, un nouveau langage. Évalué à 4.
1) Ouvre n'importe quel bouquin de niveau licence/maîtrise pour faire de l'algo.
2) Choisis les chapitres concernant les graphes et les arbres plus particulièrement.
3) Prends un algo au hasard.
4) Surprise ! L'algo est récursif. Et c'est carrément « naturel » de penser ainsi, soit dit en passant. L'alternative itérative est beaucoup moins facile à imaginer.
5) Réessaie avec le chapitre sur les tris efficaces (pire cas ou cas moyen). Retourner en 4 pour la conclusion.
Il faut évidemment nuancer tout ça : si l'algo en question est récursif terminal, il existe une version équivalente itérative, et on peut même s'amuser à automatiser la transformation (certains compilateurs le font dans les cas assez simples).
Par contre, une chose est certaine : autant l'approche récursive est tout à fait naturelle dans certaines structures de données (les structures ... récursives, tiens donc !), autant, pour un langage comme le C, la récursivité peut faire très mal (surtout si elle n'est pas terminale).
Moralité : il faut des mecs super balaises en algo/prog C pour élaborer des algos itératifs pour gérer les cas (cf. la glibc, par ex), sinon il y a risque de faire exploser la pile des variables automatiques.
Corollaire : les programmeurs « moyens » utilisent des structures de données comme on le leur a dit, sans vraiment leur expliquer comment elles fonctionnent, et du coup bousillent totalement les perfs d'un programme. Par exemple, ils ont l'habitude d'utiliser des listes d'éléments (en Java, C#, que sais-je), et n'ont jamais entendu parler des arbres rouge-noir (pourtant implémentés en tant que TreeMap en Java par ex). Résultat : ils vont se faire chier à faire des sortes de « tri par insertion » sur une liste, plutôt que d'utiliser une structure spécifiquement élaborée pour ce genre de cas.
Maintenant, un langage fonctionnel a beau avoir une approche plus « mathématique » de la programmation (pour la forme), je pense avoir eu autant de mal au début à comprendre comment faire des boucles for/while/do-while en Perl/C qu'à faire des récursions en LISP pour la première fois. Non, pire. Ca avait été plus dur, car comme on m'avait relativement bien formé à C, on n'avait cessé de me répéter : « la récursivité, c'est le Mal » (à cause du passage des paramètres par valeur, etc). Donc j'étais bien endoctriné.