Est-ce que «inductivement» et «récursivement» ont des significations très similaires?

11

Est-ce que "inductivement" et "récursivement" signifient très similaires?

Par exemple, s'il existe un algorithme qui détermine un vecteur n-dim en déterminant ses premiers k + 1 composants en fonction de ses premiers k composants ayant été déterminés et est initialisé avec le premier composant, l'appelleriez-vous fonctionne récursivement ou inductivement? J'utilise "récursivement", mais aujourd'hui, quelqu'un l'a dit "par induction".

Tim
la source
Cet article sur l' induction et la récursivité le résume bien, mais l'essentiel est qu'ils sont étroitement liés; une preuve d'induction mathématique peut être écrite comme un algorithme récursif.
Merbs
Inductivement signifie généralement récursivement de à , donc récursivement est l'adverbe le plus général. n + 1nn+1
Yuval Filmus
Quel type de récursivité n'est pas inductif, @YuvalFilmus?
Tim
@YuvalFilmus: C'est une notion très limitée d'inductif.
Dave Clarke
Pour moi, cela signifie la même chose hors contexte. Dans un contexte spécifique, elles peuvent signifier différentes choses.
Gilles 'SO- arrête d'être méchant'

Réponses:

6

Non , mais pas pour les raisons avancées par d'autres personnes. La différence entre la récursivité et l'induction n'est pas que la récursivité est "de haut en bas" et l'induction est "de bas en haut". L'induction est isomorphe à quelque chose appelé «récursion primitive», mais, en général, la récursivité est strictement plus puissante que l'induction .

La distinction entre top-down et bottom-up est triviale - tout programme récursif primitif "top-down" peut être mécaniquement converti en quelque chose de "bottom-up". En fait, toute preuve par induction peut être transformée en programme récursif. Dans le cadre du calcul des constructions inductives, si vous voulez prouver que chaque nombre naturel est froopuleux, vous l'écririez comme une fonction qui construit une preuve que n est froopuleux en faisant un appel récursif pour construire une preuve que n- 1 est froopuleux.

Le facteur clé de l'induction est que les choses sont définies en termes de plus petites choses, et qu'elles «se terminent» après un nombre fini d'étapes. Les nombres naturels sont inductifs car chaque naturel est soit 0, soit le successeur d'un plus petit naturel. Les listes sont inductives car chaque liste est soit vide, soit décomposée ("dépliée") en un élément et une liste plus petite.

Parfois, les programmes récursifs ne sont pas écrits en termes de petites choses. Par exemple, prenez cette fonction Collatz:

fun collatz(n) 
   if n <= 1
      return 0;
   else if n % 2 == 0
     return 1 + collatz(n / 2)
   else
     return 1 + collatz(3 * n + 1)
end

Cette fonction ne va ni de haut en bas ni de bas en haut et n'est donc pas inductive sur les nombres naturels.

Il pourrait y avoir une ordonnance pour traiter cela de manière inductive, mais pour la plupart des choses, il n'y a tout simplement aucun moyen. Les fonctions sur des flux infinis en sont un excellent exemple. En fait, les flux sont l'exemple prototypique d'un type "coinductif".

Les «Fondements pratiques des langages de programmation» de Bob Harper, disponibles gratuitement en ligne, présentent une belle introduction aux types inductifs, coinductifs et récursifs.

James Koppel
la source
2

Pour moi, c'est surtout une question de point de vue. Si je définis des objets sur la base d'un plus petit, je le fais par induction, c'est donc de bas en haut. Si je résous un problème en le décomposant en petits morceaux qui sont résolus de la même manière, je l'appelle récursivité, c'est de haut en bas.

(modifier) ​​PS. Voir une question similaire dans notre département sœur Mathématiques, définition récursive vs inductive . Je cite la réponse de Carl Mummert:

Ma meilleure description est que la "définition inductive" est plus courante lorsque nous définissons un ensemble d'objets "à partir de rien", tandis que la "définition récursive" est plus courante lorsque nous définissons une fonction sur une collection d'objets déjà existante.

Mais plus important:

ça ne vaut pas la peine de dormir

Hendrik Jan
la source
donc "récursion = diviser pour mieux régner", lequel d'abord de haut en bas puis de bas en haut?
Tim
1

Non, ce n'est pas pareil. Et vous avez raison (je suppose sur l'algorithme que vous décrivez): c'est récursif.

La raison en est la définition des deux mots, que vous pouvez lire dans un dictionnaire ou Wikipedia.

L'induction (en supposant une «induction mathématique») consiste spécifiquement à prouver que tous les cas d'un argument sont vrais.

La récursivité concerne spécifiquement un processus qui peut être répété d'une manière ou d'une autre au sein du même processus.

RE: réponses des autres:

Après avoir vu les réponses des autres, je peux comprendre pourquoi il y a de la confusion: lors de la définition des infrastructures de données, des fonctions et des langages, certains théoriciens semblent utiliser `` inductif '' et `` récursif '' de manière confuse (voir les commentaires de cette question). Je ne pense pas que la réponse de Koppel (même avec les votes les plus élevés actuels) reflète vraiment cette confusion. Puisque nous parlons d'un algorithme, je ne dirais pas qu'il existe des «algorithmes inductifs»; Je pense que c'est une catégorisation inutile.

À M
la source
L'induction ne concerne pas seulement les preuves. Vous l'utilisez également tout le temps pour définir de manière inductive des structures récursives (structures de données, langages, etc.)
hugomg
@missingno Veuillez fournir une source pour cette définition.
Tom
Un exemple auquel je pourrais penser est ici : "Le langage de \ mathcal {L}, également connu sous le nom de son ensemble de formules, formules bien formées ou wffs, est défini par induction par les règles suivantes:"
hugomg
@missingno qui mène à cette page Wikipedia où je pense qu'il y a une utilisation redondante et déroutante du mot «inductif», essentiellement utilisé comme «récursif»
Tom
Veuillez ne pas me faire chercher encore plus d'exemples. Même si vous n'êtes peut-être pas d'accord avec lui, c'est certainement un idiome très courant et vous pouvez le trouver dans de nombreux livres aussi si vous le recherchez. Et ce n'est pas comme si quelqu'un avait édité l'article wikipedia dans le but de prouver mon point ...
hugomg