GUÍA 02-09-26 Teoría de la Computación

NE111 · miércoles 02/09/2026 · 16:00-17:15 · Sesión 8

Recursión: definición y funcionamiento

QUÉ ES LA RECURSIÓN

Definir algo en términos de sí mismo, con un caso base que detiene la definición. Es la contraparte natural de la iteración y, en teoría de la computación, es el otro camino histórico hacia la noción de computabilidad.

LAS DOS PIEZAS OBLIGATORIAS

• Caso base — el valor que se conoce sin recurrir a la definición.
• Caso recursivo — se define el valor en función de un caso más pequeño, que debe acercarse al caso base.

Si falta el caso base, o si el caso recursivo no reduce el problema, la definición no termina. Es la versión matemática de un ciclo infinito.

EJEMPLOS

• Factorial: 0! = 1 y n! = n·(n−1)!
• Fibonacci: F(0) = 0, F(1) = 1 y F(n) = F(n−1) + F(n−2).
• Potencia: a⁰ = 1 y aⁿ = a·aⁿ⁻¹.

DEFINICIONES RECURSIVAS DE CONJUNTOS

Muchos objetos del curso ya se definieron así, aunque no lo dijéramos con ese nombre.

• Las cadenas sobre Σ: ε es una cadena, y si w es cadena y a ∈ Σ, entonces wa es cadena.
• Las expresiones regulares, que se definirán en la sección 4 exactamente con esta forma.
• Los árboles de derivación de una gramática, en la sección 5.

RECURSIÓN E INDUCCIÓN

Son la misma idea vista al derecho y al revés. La recursión construye objetos desde el caso base; la inducción demuestra propiedades de objetos así construidos. Toda definición recursiva viene con un principio de inducción asociado, y esa es la herramienta con la que se demostrarán casi todos los teoremas del curso.

RECURSIÓN Y LA PILA

Al ejecutarse, cada llamada recursiva ocupa un marco en la pila con sus parámetros y su dirección de retorno. La recursión no es magia del lenguaje: es la pila haciendo el trabajo. Es el mismo mecanismo que estás viendo en Estructuras de Datos.

RECURSIÓN Y MÁQUINAS DE TURING

La conexión con el bloque anterior: una máquina de Turing puede simular cualquier definición recursiva, y toda función computable por MT puede escribirse recursivamente. Son dos formas de decir lo mismo, y la próxima sesión lo hace preciso.

EJERCICIO

Escribir definiciones recursivas para: máximo común divisor, longitud de una cadena, y reverso de una cadena. Demostrar por inducción que el reverso del reverso es la cadena original.