Introducción a la inducción

La recursión se define a partir de tres elementos; uno de éstos es la cláusula de inducción. A través de la inducción matemática se puede definir un mecanismo para encontrar todos los posibles elementos de un conjunto recursivo partiendo de un subconjunto conocido, o bien, para probar la validez de la definición de una función recursiva a partir de un caso base.

El mecanismo que la inducción define, parte del establecimiento de reglas que permiten generar nuevos elementos tomando como punto de partida una semilla (caso base).

Existen dos principios básicos que sustentan la aplicación de la inducción matemática en la definición de recursión:

Primer principio. Si el paso base y el paso inductivo asociados a una función recursiva pueden ser probados, la función será válida para todos los casos que caigan dentro del dominio de la misma. Asimismo, establece que si un elemento arbitrario del dominio cumple con las propiedades definidas en las cláusulas inductivas, su sucesor o predecesor, generado según la cláusula inductiva, también cumplirá con dichas propiedades.

Segundo principio. Se basa en afirmaciones de la forma x P(x). Esta forma de inducción no requiere del paso básico, ya que asume que P(x) es válido para todo elemento del dominio.

Fuente: Apunte Análisis, diseño e implantación de algoritmos de la facultad de contaduría y administración, UNAM