¿"Inductivo" y "recursivamente" tienen significados muy similares?

11

¿"Inductivamente" y "recursivamente" significan muy similares?

Por ejemplo, si hay un algoritmo que determina un vector n-dim mediante la determinación de sus primeros componentes k + 1 en función de que se hayan determinado sus primeros componentes k, y se inicializa con el primer componente, ¿llamaría que funciona recursivamente o inductivamente? He estado usando "recursivamente", pero hoy alguien lo dijo "inductivamente".

Tim
fuente
Este artículo sobre inducción y recursión lo resume muy bien, pero lo esencial es que están estrechamente relacionados; Una prueba de inducción matemática se puede escribir como un algoritmo recursivo.
Merbs
Inductivamente generalmente significa recursivamente de a , por lo que recursivamente es el adverbio más general. n + 1nn+1
Yuval Filmus
¿Qué tipo de recursivo no es inductivo, @YuvalFilmus?
Tim
@YuvalFilmus: Esa es una noción muy limitada de inductivo.
Dave Clarke el
Para mí significan lo mismo fuera de contexto. En un contexto específico, pueden significar cosas diferentes.
Gilles 'SO- deja de ser malvado'

Respuestas:

6

No , pero no por las razones que otras personas han dado. La diferencia entre recursión e inducción no es que la recursión sea "de arriba abajo" y la inducción sea "de abajo hacia arriba". La inducción es isomorfa a algo llamado "recursividad primitiva", pero, en general, la recursión es estrictamente más poderosa que la inducción .

La distinción entre descendente y ascendente es trivial: cualquier programa recursivo primitivo "descendente" puede convertirse mecánicamente en algo "ascendente". De hecho, cualquier prueba por inducción puede convertirse en un programa recursivo. En el marco del cálculo de las construcciones inductivas, si desea probar que cada número natural es froopuloso, lo escribiría como una función que construye una prueba de que n es froopuloso haciendo una llamada recursiva para construir una prueba de que n- 1 es froopuloso.

El factor clave de la inducción es que las cosas se definen en términos de cosas más pequeñas, y "tocan fondo" después de muchos pasos. Los números naturales son inductivos porque cada natural es 0 o el sucesor de un natural más pequeño. Las listas son inductivas porque cada lista está vacía o puede desglosarse ("desplegarse") en un elemento y una lista más pequeña.

Sin embargo, a veces los programas recursivos no se escriben en términos de cosas más pequeñas. Por ejemplo, tome esta función de 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

Esta función no va de arriba hacia abajo ni de abajo hacia arriba, y por lo tanto no es inductiva sobre los números naturales.

Puede haber una orden para tratar eso inductivamente, pero para la mayoría de las cosas simplemente no hay forma. Las funciones sobre flujos infinitos son un gran ejemplo. De hecho, las corrientes son el ejemplo prototípico de un tipo "coinductivo".

"Fundamentos prácticos para lenguajes de programación" de Bob Harper, disponible en línea de forma gratuita, tiene una buena introducción a los tipos inductivos, coinductivos y recursivos.

James Koppel
fuente
2

Para mí es principalmente una cuestión de punto de vista. Si defino objetos basados ​​en uno más pequeño, lo hago inductivamente, de modo que es de abajo hacia arriba. Si resuelvo un problema dividiéndolo en partes más pequeñas que se resuelven de la misma manera que lo llamo recurrencia, eso es de arriba hacia abajo.

(editar) PS. Vea una pregunta similar en nuestro departamento hermano de Matemáticas, Definición recursiva vs. inductiva . Cito de la respuesta de Carl Mummert:

Mi mejor descripción es que la "definición inductiva" es más común cuando definimos un conjunto de objetos "de la nada", mientras que la "definición recursiva" es más común cuando definimos una función en una colección de objetos ya existente.

Pero mas importante:

no vale la pena perder el sueño

Hendrik Jan
fuente
entonces "recursión = dividir y conquistar", ¿cuál de arriba hacia abajo y luego de abajo hacia arriba?
Tim
1

No, no son lo mismo. Y tienes razón (estoy asumiendo sobre el algoritmo que estás describiendo): es recursivo.

La razón es la definición de ambas palabras, que puedes leer en un diccionario o Wikipedia.

La inducción (suponiendo 'inducción matemática') se trata específicamente de probar que todos los casos de un argumento son verdaderos.

La recursión es específicamente sobre un proceso que puede repetirse de alguna manera dentro del mismo proceso.

RE: respuestas de otras personas:

Después de ver las respuestas de otras personas, puedo entender por qué hay confusión: al definir estructuras de datos, funciones y lenguajes, algunos teóricos parecen usar 'inductivo' y 'recursivo' de una manera confusa (ver comentarios a esta pregunta). No creo que la respuesta de Koppel (incluso con los votos más altos actuales) realmente refleje esa confusión. Como estamos hablando de un algoritmo, no diría que hay 'algoritmos inductivos'; Creo que es una categorización innecesaria.

Tom
fuente
La inducción no se trata solo de pruebas. También lo usa todo el tiempo para definir inductivamente estructuras recursivas (estructuras de datos, idiomas, etc.)
hugomg
@missingno Proporcione una fuente para esa definición.
Tom
Un ejemplo en el que podría pensar es aquí : "El lenguaje de \ mathcal {L}, también conocido como su conjunto de fórmulas, fórmulas bien formadas o wffs, se define inductivamente por las siguientes reglas:"
hugomg
@missingno que lleva a esta página de Wikipedia donde creo que hay un uso redundante y confuso de la palabra 'inductivo', que se usa esencialmente como 'recursivo'
Tom
Por favor, no me hagas buscar aún más ejemplos. Aunque no esté de acuerdo con él, definitivamente es un idioma muy común y también puede encontrarlo en muchos libros si lo busca. Y no es como si alguien editara el artículo de Wikipedia a propósito para probar mi punto ...
hugomg