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

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

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