Re: Loupé

Ce qui fait réagir, c'est de pas l'avoir dit dans le contexte d'un langage particulier.

Moi qui n'écris pratiquement presque que du OCaml, j'aurais pu écrire ton inversion de demande de légitimité. Si on prend le vénérable taptempo en OCaml, le premier qui vient me demander de justifier ma boucle loop récursive par rapport à une immonde boucle while risque de regretter sa demande de justification. ;-)

Les fonctions récursives c'est le pendant calculatoire des constructions par récurrence et du raisonnement par récurrence. Le plus simple d'entre eux étant le raisonnement par récurrence sur les nombres entiers (représentés de manière unaire) :

• si une propriété est vraie de 0 ;
• si elle est vraie de n alors elle est vraie de n + 1 ;
• alors elle est vraie de tout entier.

Il existe une autre version de l'hypothèse de récurrence qui devient :

• si elle est vraie de tout entier ≤ n alors est vraie de n + 1

Dans la première formulation la taille de l'hypothèse est constante (le cas n), dans la seconde elle croît linéairement avec n (la conjonction de tous les cas jusqu'à n).

Dans le premier cas, on a une récursion terminale qui utilise un espace constant sur la pile; dans le second l'espace consommé croît linéairement avec la taille de l'entrée, on risque le débordement de pile.

Les entiers unaires n'étant rien d'autres que des listes chaînées, le module des listes de la bibliothèque standard de OCaml contient une grande quantité de fonctions récursives (dont certaines ne sont pas terminales récursives).

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.