¿Cuál es la relación entre la recursión y la prueba por inducción?

Question

¿Cuál es la relación entre la recursión y la prueba por inducción?

Digamos fn(n),

recursividad es fn(n) llamadas sí mismo hasta se reúnen base condition;

inducción es cuando base condition se encuentra, intenta probar (base case + 1) también es correcto.

Parece recursividad e inducción en una dirección diferente. Uno comienza desde n hasta base case, el otro comienza desde base case hasta infinite.

¿Podría alguien explicar la idea en detalle?

Answer 1

¡La recursividad y la inducción son casi lo mismo! Esto se vuelve obvio si usa un lenguaje de programación con tipos dependientes, como Agda, pero se puede demostrar hasta cierto punto sin ellos también.

Recuerde, que debido a la Curry-Howard correspondence, los tipos son proposiciones y los programas son pruebas. Cuando está escribiendo una función del tipo Nat -> Nat (utilizaré la notación Haskell), está tratando de demostrar que, dado un número natural, su programa terminará y producirá otro número natural. Ahora podemos tener una definición así:

f 0 = 1 
f (1 + n) = n * f n 

que es tanto una definición recursiva de f y una prueba inductiva de su terminación, al mismo tiempo!

Usted puede leer como una prueba de una manera siguiente:

Vamos a demostrar que f x termina por cualquier x.

• Caso base: tenemos f 0 constante por definición, por lo que termina.
• Caso inductivo: si asumimos f n termiatos, f (1 + n) termina también (porque todas las funciones que llama terminan).

Tenga en cuenta que como la recursión no se limita a una función que disminuye su contador, la inducción no se limita a los números naturales tampoco. También hay inducción estructural, que corresponde a la recursión estructural, ambos son muy populares en matemáticas/programación. Estos se deben usar cuando se trata de probar cosas/definir funciones en estructuras de datos más complejas (listas/árboles/etc.).

Ahora, para abordar su preocupación sobre la "dirección" de la recursión/inducción. Es útil considerar "dirección de la demanda" y "dirección de suministro" aquí, que son opuestas.

Cuando define la función recursiva, la demanda (llamadas al método) fluye desde valores más grandes al caso base. Por otro lado, el suministro (los valores de retorno) fluye desde el caso base a los valores más grandes del parámetro. "definición" es otra forma de pensar sobre el suministro. Comienza en el caso base y se propaga hasta el infinito a través del caso recursivo.

Ahora, cuando está haciendo pruebas inductivas, los teoremas son su suministro mientras los objetivos son su demanda.Puede hacer un teorema T 0 fuera del caso base y luego mejorarlo a la T n grande que desee con el caso inductivo: su suministro fluye de 0 a infinito. Ahora bien, si tienes un objetivo G n, puedes hacer un objetivo más pequeño G (n-k) usando el paso inductivo hasta llegar a cero. De esta manera su demanda va de n a 0.

Como puede ver, la dirección de suministro es "infinito" en ambos casos y la dirección de la demanda es "a cero" en ambos casos.

También puede invertir el orden aparente en las descripciones de inducción y recursividad sin cambiar su significado:

inducción es el momento de demostrar que P n sostiene que necesita para reducir primero su objetivo de P 0 aplicando repetidamente la caso inductivo y luego probar el objetivo resultante utilizando el caso base.

De manera similar, la recursión ocurre cuando define por primera vez un caso base y luego define los valores adicionales en términos de los anteriores. ¡Mira, las instrucciones se intercambian fácilmente!