Discussion :

[prgasp77]

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.

[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.

[pseudocode]

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.

[prgasp77]

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

PS : j'aime beaucoup l'incrustation de ton père noël

[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ï

[FR119492]

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

[phryte]

Bonjour.

Ç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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

Que c'est beau!

[Jean-Marc.Bourguet]

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.

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.

[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ï

[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), ...

[souviron34]

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.

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.

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...

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), ...

[Jean-Marc.Bourguet]

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é.

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

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

[SpiceGuid]

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

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 OCaml :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[jack-ft]

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(

[FR119492]

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

[Jean-Marc.Bourguet]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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;
}

• 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

[SpiceGuid]

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.