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

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

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.

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

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.