[Récursivité] Existe-t-il des cas où elle est inévitable ?

Version imprimable

19/12/2008, 18h16
prgasp77

[Récursivité] Existe-t-il des cas où elle est inévitable ?

Bonjour à toutes et à tous.
J'ai entendu des dizaines de fois des phrases comme "Ça me gêne d'utiliser une fonction récursive, mais j'ai pas le choix" ... Mais je pense, sans pouvoir le démontrer, qu'il est toujours possible de l'éviter.
Quelqu'un pourrait-il, si cela existe, me trouver un cas où il n'est à priori pas possible de l'éviter ?

Merci.
19/12/2008, 18h28
Sylvain Togni

Toute fonction récursive peut-être transformée en fonction non-récursive, par exemple en utilisant une pile.

D'ailleurs la machine de Turing n'est pas récursive, elle permet pourtant de calculer tout ce qui est calculable.
19/12/2008, 18h32
pseudocode

Citation:

Envoyé par prgasp77

J'ai entendu des dizaines de fois des phrases comme "Ça me gêne d'utiliser une fonction récursive, mais j'ai pas le choix" ... Mais je pense, sans pouvoir le démontrer, qu'il est toujours possible de l'éviter.

La récursivité est un style de programmation, ce n'est pas une solution "obligatoire" à un problème.

C'est vrai qu'il est plus simple d'employer le style récursif lorsque l'algorithme utilise une méthode inductive (= un raisonnement par récurrence). Mais on peut très bien employer un autre style comme l'itératif ou le fonctionnel.

De toutes façons, dans les langages impératifs, les appels récursifs sont transformés en appels séquentiels (call & return) avec une pile de mémoire pour sauvegarder/restaurer le contexte local entre chaque appel.
19/12/2008, 18h41
prgasp77

Citation:

Envoyé par pseudocode

De toutes façons, dans les langages impératifs, les appels récursifs sont transformés en appels séquentiels (call & return) avec une pile de mémoire pour sauvegarder/restaurer le contexte local entre chaque appel.

Exact ... cela constitue en quelque sort une preuve :king:

PS : j'aime beaucoup l'incrustation de ton père noël :)
20/12/2008, 00h33
Jedai

Il faut tout de même voir que même si toute fonction récursive peut-être transformé en itération, ce n'est pas toujours pertinent de le faire, certaines solutions sont naturellement récursive et leur équivalent itératif demande de simuler la récursion par une structure de donnée type pile... L'intérêt est alors limité.
Evidemment ça dépend aussi du langage, par exemple les langages qui optimisent la récursivité terminale n'ont pas besoin de boucles, par contraste, certains langages supportent très mal le style récursif parce que leur pile est trop petite ou les appels de fonctions trop couteux. C'est le cas par exemple du C et d'autres langages impératifs historiques, qui ont malheureusement forgé cette mauvaise réputation de la récursivité dans toute une génération de programmeurs. :(

--
Jedaï
20/12/2008, 11h55
FR119492

Simple curiosité:
L'algorithme de Strassen peut-il être programmé sans récursivité ?
Jean-Marc Blanc
20/12/2008, 11h56
phryte

Bonjour.

Citation:

Ça me gêne d'utiliser une fonction récursive

On évite d'utiliser la récursivité quand :
- l'horizon est trops grand (nombre d'itérations qui nécessite des sauvegarde de mémoires et de registres)
- en programmation temps-réel qui privilégie les interruptions.
Mais on l'utilise quand on veut faire un "beau programme" (la programmation est aussi de l'art).
La récursivité permet la meilleure concision (logiciel le plus court)
exemple en Caml de la factorielle :

Code:

let rec fac=fun 0 ->1 |n ->n*fac(n-1);;

Que c'est beau!
20/12/2008, 12h27
Jean-Marc.Bourguet

Citation:

Envoyé par Jedai

Il faut tout de même voir que même si toute fonction récursive peut-être transformé en itération, ce n'est pas toujours pertinent de le faire, certaines solutions sont naturellement récursive et leur équivalent itératif demande de simuler la récursion par une structure de donnée type pile... L'intérêt est alors limité.

Nous sommes d'accord jusqu'ici.

Citation:

Evidemment ça dépend aussi du langage, par exemple les langages qui optimisent la récursivité terminale n'ont pas besoin de boucles, par contraste, certains langages supportent très mal le style récursif parce que leur pile est trop petite ou les appels de fonctions trop couteux. C'est le cas par exemple du C et d'autres langages impératifs historiques, qui ont malheureusement forgé cette mauvaise réputation de la récursivité dans toute une génération de programmeurs. :(

Il y a déjà assez de bonnes raisons pour critiquer le C que pour ne pas en inventer des fausses. Le C n'a pas de limitations intrinsèque sur la profondeur de pile -- elles sont le fait de l'OS -- et ses conventions d'appels de fonctions sont parmi les moins coûteuses qui soient, et historiquement c'est un des premiers langages avec les Lisp à permettre les appels récursifs sans marquage particulier. Il faut remonter à bien plus loin pour comprendre d'où vient la réputation de lenteur des appels de fonctions, et en particulier des appels de fonctions récursifs. Et ce n'est pas dû aux langages, mais aux architectures.

Il a fallu du temps pour établir les conventions actuelles à base de pile. Une technique courante d'appel de fonction était de placer les paramètres à un endroit fixe en mémoire. L'adresse de retour était soit un des paramètres placés aux même endroit, soit carrément patchée dans l'instruction de saut terminant la routine. Naturellement, avec un tel mécanisme de base, les fonctions récursives étaient difficiles à supporter.
20/12/2008, 14h10
Jedai

Désolé, ma formulation n'était pas très claire, je ne voulais pas dire que les appels de fonctions en C étaient couteux, c'était juste l'un des exemples de problèmes potentiel pour la récursivité dans un langage. Je disais simplement que C n'était pas adapté à la récursivité, d'une part parce que la pile est souvent trop petite (même si je suis d'accord que ce n'est pas spécifié dans le standard), d'autre part parce qu'il est très difficile d'écrire des closures ou même de simple fonctions imbriquées (ce n'est pas supporté par le langage), ce qui réduit l'intérêt de la récursivité pour le programmeur.

--
Jedaï
20/12/2008, 15h07
Alp

La tâche est clairement rendue aisée dans les langages fonctionnels c'est certain.
Après, le plus important pour le PO c'est de saisir autant que possible les notions clés rattachées à la récursivité et la "façon de penser récursif". Le langage ne sera qu'un moyen de mettre en oeuvre finalement, comparé à la compréhension de la récursivité (terminale ou pas), ...
20/12/2008, 15h28
souviron34

Citation:

Envoyé par Jean-Marc.Bourguet

Il y a déjà assez de bonnes raisons pour critiquer le C que pour ne pas en inventer des fausses. Le C n'a pas de limitations intrinsèque sur la profondeur de pile -- elles sont le fait de l'OS -- et ses conventions d'appels de fonctions sont parmi les moins coûteuses qui soient, et historiquement c'est un des premiers langages avec les Lisp à permettre les appels récursifs sans marquage particulier. Il faut remonter à bien plus loin pour comprendre d'où vient la réputation de lenteur des appels de fonctions, et en particulier des appels de fonctions récursifs. Et ce n'est pas dû aux langages, mais aux architectures.

:king:

Citation:

Envoyé par Jedai

Désolé, ma formulation n'était pas très claire, je ne voulais pas dire que les appels de fonctions en C étaient couteux, c'était juste l'un des exemples de problèmes potentiel pour la récursivité dans un langage. Je disais simplement que C n'était pas adapté à la récursivité, d'une part parce que la pile est souvent trop petite (même si je suis d'accord que ce n'est pas spécifié dans le standard), d'autre part parce qu'il est très difficile d'écrire des closures ou même de simple fonctions imbriquées (ce n'est pas supporté par le langage), ce qui réduit l'intérêt de la récursivité pour le programmeur.

:roll: Euh franchement je ne te suis pas.... pour le C..

Le C est très bien adapté à la récursivité dans certains cas, et comme on l'a dit la taille de la pile ne dépend pas en grande partie du langage...

Citation:

Envoyé par Alp

La tâche est clairement rendue aisée dans les langages fonctionnels c'est certain.
Après, le plus important pour le PO c'est de saisir autant que possible les notions clés rattachées à la récursivité et la "façon de penser récursif". Le langage ne sera qu'un moyen de mettre en oeuvre finalement, comparé à la compréhension de la récursivité (terminale ou pas), ...

:king:
20/12/2008, 17h25
Jean-Marc.Bourguet

Citation:

Envoyé par Jedai

Je disais simplement que C n'était pas adapté à la récursivité, d'une part parce que la pile est souvent trop petite (même si je suis d'accord que ce n'est pas spécifié dans le standard),

Je ne suis pas convaincu; j'attends toujours de voir le moment où elle m'explose à la figure pour autre chose qu'un bug. Et je n'ai pas peur d'utiliser la récursivité.

Citation:

d'autre part parce qu'il est très difficile d'écrire des closures ou même de simple fonctions imbriquées (ce n'est pas supporté par le langage)

Ca je sais. Mais je ne vois pas le rapport avec

Citation:

ce qui réduit l'intérêt de la récursivité pour le programmeur.

Citation:

D'ailleurs la machine de Turing n'est pas récursive, elle permet pourtant de calculer tout ce qui est calculable.

Très bon exemple :ccool:

Voici mon implémentation (oui, contrairement aux apparences, elle est bien récursive terminale!) de la machine de Turing universelle inventée en 1962 par Marvin Minsky
(http://mathworld.wolfram.com/Univers...ngMachine.html) :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 (* les 4 couleurs *) type color = C3 | C2 | C1 | C0 (* une transition: écrire une couleur c, curseur + i, passer à l'état s *) let trans (c3,c2,c1,c0) (i3,i2,i1,i0) (s3,s2,s1,s0) tape cursor = match tape.(cursor) with | C3 -> tape.(cursor) <- c3; s3 tape (i3 cursor) | C2 -> tape.(cursor) <- c2; s2 tape (i2 cursor) | C1 -> tape.(cursor) <- c1; s1 tape (i1 cursor) | C0 -> tape.(cursor) <- c0; s0 tape (i0 cursor) (* arrêter la machine *) let stop cursor = cursor let halt tape cursor = () (* les 7 états et leur transition associée *) let rec s0 t = trans (C2,C0,C3,C2) (pred,pred,succ,succ) (s4,s1,s0,s0) t and s1 t = trans (C1,C0,C3,C0) (pred,pred,succ,pred) (s1,s1,s0,s1) t and s2 t = trans (C1,C2,C3,C2) (succ,succ,succ,pred) (s2,s2,s2,s4) t and s3 t = trans (C1,C2,C3,C3) (succ,succ,succ,pred) (s3,s3,s3,s4) t and s4 t = trans (C1,C2,C3,C0) (pred,pred,pred,stop) (s5,s4,s4,halt) t and s5 t = trans (C1,C2,C1,C2) (pred,pred,pred,succ) (s5,s5,s6,s2) t and s6 t = trans (C0,C0,C1,C2) (succ,succ,succ,succ) (s0,s6,s6,s3) t
Maintenant j'aimerais bien voir :

une implémentation itérative tout aussi élégante
une implémentation récursive en C qui ne déborderait pas la pile

29/12/2008, 17h27
jack-ft

Citation:

Envoyé par FR119492

Simple curiosité:
L'algorithme de Strassen peut-il être programmé sans récursivité ?
Jean-Marc Blanc

Ben oui, comme tout le reste: il suffit d'implémenter la récursivité sans récursivité!

Mais ça risque d'être coûteux!

)jack(
29/12/2008, 20h29
FR119492

Citation:

Mais ça risque d'être coûteux!

Ce n'est pas trop grave, puisqu'en pratique personne n'utilise l'algorithme de Strassen!
Jean-Marc Blanc

Citation:

Envoyé par SpiceGuid

Maintenant j'aimerais bien voir :

une implémentation itérative tout aussi élégante

Tu donnes une implémentation itérative (la récursivité terminale, c'est de
l'itération, en particulier quand on dépend du fait qu'elle est compilée
comme telle!) et tu demandes à voir une implémentation itérative tout aussi
élégante? Bon, virer la récursivité terminale, c'est trivial. Voici le
coeur exprimé en C -- c'est de la pure translittération.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 #define STATE(c0, c1, c2, c3, s0, s1, s2, s3, n0, n1, n2, n3) \ switch(tape[pos]) { \ case C3: tape[pos] = c0; pos += s0; goto n0; \ case C2: tape[pos] = c1; pos += s1; goto n1; \ case C1: tape[pos] = c2; pos += s2; goto n2; \ case C0: tape[pos] = c3; pos += s3; goto n3; \ } \ break ... S2: STATE(C1, C0, C3, C0, +1, +1, +1, -1, S2, S2, S2, S4); ...
Dans un language sans macro, c'est un peu plus redondant. Quoiqu'en Algol
(un langage de 1960!) ou en Pascal (le vrai!) qui peuvent passer des
labels comme paramètre, ca ne pose naturellement aucun problème de
concision non plus.

En passant, j'ai du mal à voir en quoi elle est particulièrement élégante.
Je préfère une implémentation plus purement conduite par les données:
Code:

1 2 3 4 5 6 7 while (state >= 0) { StateDesc desc = transitions[state, tape[pos]]; tape[pos] = desc.new_color; pos += desc.step; state = desc.next_state; }
Citation:

une implémentation récursive en C qui ne déborderait pas la pile

J'ai deux compilateurs C ici (gcc, SunStudio), tous les deux remplacent les appels finaux par des sauts ;)

29/12/2008, 22h50
SpiceGuid

Citation:

En passant, j'ai du mal à voir en quoi elle est particulièrement élégante.

L'élégance est une notion assez personnelle.
Disons que mon implantation est complète et "minimale", il n'y a pas de variables globales, si je devais multithreader il n'y aurait rien à ajouter.