Tous les algorithmes itératifs peuvent-ils être exprimés de manière récursive ?

Question

Sinon, existe-t-il un bon contre-exemple montrant un algorithme itératif pour lequel il n'existe pas de contrepartie récursive ?

S'il est vrai que tous les algorithmes itératifs peuvent être exprimés de manière récursive, existe-t-il des cas où cela est plus difficile à faire ?

Par ailleurs, quel rôle le langage de programmation joue-t-il dans tout cela ? Je peux imaginer que les programmeurs Scheme ont une vision différente de l'itération (= récursion en queue) et de l'utilisation de la pile que les programmeurs Java.

Answer 1

Il existe une preuve ad hoc simple pour cela. Puisque vous pouvez construire un langage complet de Turing en utilisant des structures strictement itératives et un langage complet de Turing en utilisant uniquement des structures récursives, les deux sont donc équivalents.

Answer 2

Tous les algorithmes itératifs peuvent-ils être exprimés de manière récursive ?

Oui, mais la preuve n'est pas intéressante :

1. Transformez le programme avec tout son flux de contrôle en une seule boucle contenant une seule déclaration de cas dans laquelle chaque branche est un flux de contrôle en ligne droite comprenant éventuellement break , return , exit , raise et ainsi de suite. Introduisez une nouvelle variable (appelée "compteur de programme") que l'instruction case utilise pour décider du bloc à exécuter ensuite.

   Cette construction a été découverte pendant les grandes "guerres de programmation structurée" des années 1960, lorsque les gens discutaient du pouvoir expressif relatif de diverses constructions de flux de contrôle.

2. Remplacez la boucle par une fonction récursive, et remplacez chaque variable locale mutable par un paramètre de cette fonction. Voilà ! L'itération est remplacée par la récursion.

Cette procédure revient à écrire un interprète pour la fonction d'origine. Comme vous pouvez l'imaginer, cela donne un code illisible, et ce n'est pas une chose intéressante à faire. Cependant Dans le cas de l'apprentissage de la programmation fonctionnelle, certaines des techniques peuvent être utiles à une personne ayant une expérience de la programmation impérative et qui apprend à programmer dans un langage fonctionnel pour la première fois.

Answer 3

Comme vous le dites, toute approche itérative peut être transformée en approche "récursive", et avec des appels de queue, la pile n'explosera pas non plus :-) En fait, c'est ainsi que Scheme implémente toutes les formes courantes de boucles. Exemple en Scheme :

(define (fib n)
  (do ((x 0 y)
       (y 1 (+ x y))
       (i 1 (+ i 1)))
      ((> i n) x)))

Ici, bien que la fonction semble itérative, elle récure en fait un lambda interne qui prend trois paramètres, x , y y i et s'appelle lui-même avec de nouvelles valeurs à chaque itération.

Voici une façon dont cette fonction pourrait être macro-étendue :

(define (fib n)
  (letrec ((inner (lambda (x y i)
                    (if (> i n) x
                        (inner y (+ x y) (+ i 1))))))
    (inner 0 1 1)))

De cette façon, la nature récursive devient plus apparente visuellement.

Answer 4

Définir itératif comme :

function q(vars):
  while X:
    do Y

Peut être traduit par :

 function q(vars):
    if X:
      do Y
      call q(vars)

Dans la plupart des cas, Y inclut l'incrémentation d'un compteur testé par X. Cette variable devra être transmise dans 'vars' d'une manière ou d'une autre si l'on utilise la voie récursive.

Answer 5

Comme l'a noté Plinth dans le leur réponse nous pouvons construire des preuves montrant comment récursion et l'itération sont équivalentes et peuvent toutes deux être utilisées pour résoudre le même problème. Cependant, même si nous savons que les deux sont équivalentes, il existe des inconvénients à utiliser l'une plutôt que l'autre.

Dans les langages qui ne sont pas optimisés pour la récursion, vous pouvez constater qu'un algorithme utilisant l'itération s'exécute plus rapidement que le récursif. De même, même dans les langages optimisés, vous pouvez constater qu'un algorithme utilisant l'itération écrit dans un langage différent s'exécute plus rapidement que le récursif. En outre, il se peut qu'il n'y ait pas une manière évidente d'écrire un algorithme donné en utilisant la récursion par rapport à l'itération et vice versa. Cela peut conduire à un code difficile à lire, ce qui entraîne des problèmes de maintenabilité.