1. Definición Recursiva

Una definición recursiva describe un objeto (como una secuencia o estructura) en términos de versiones más pequeñas de sí mismo. Tiene dos componentes:

• Caso base: Define el valor inicial o condición de parada.
• Paso recursivo: Define cómo construir el siguiente elemento a partir de los anteriores.

Ejemplos Clásicos

1. Números de Fibonacci :
   • Caso base: $F(0)=0$, $F(1)=1$.
   • Paso recursivo: $F(n)=F(n−1)+F(n−2)$ para $n≥2$.
2. Listas Enlazadas :
   • Una lista enlazada es:
     • Caso base: Vacía (null).
     • Paso recursivo: Un nodo que contiene un valor y una referencia a otra lista enlazada.
3. Árboles de Parse :
   • Caso base: Un nodo hoja (un símbolo terminal).
   • Paso recursivo: Un nodo interno con subárboles como hijos.
4. Fractales :
   • Ejemplo: El conjunto de Cantor.
     • Caso base: Un segmento inicial.
     • Paso recursivo: Dividir cada segmento en tres partes y eliminar la parte central.

1.1 Pruebas Inductivas

La inducción es una herramienta poderosa para probar propiedades de objetos definidos recursivamente.

Ejemplo: Probar una Propiedad de Fibonacci

Probar que $F(n) < 2^n$ para todo $n≥0$.

1. Base de Inducción :
   • Para $n=0$: $F(0)=0< 2^0=1$. Verdadero.
   • Para $n=1$: $F(1)=1< 2^1=2$. Verdadero.
2. Paso Inductivo :
   • Supongamos que $F(k)< 2^k$ y $F(k-1)< 2^{k-1}$ para algún $k≥1$.
   • Entonces:
   $$F(k+1)=F(k)+F(k-1)< 2^k+2^{k-1}=2^{k-1}(2+1)=2^{k+1}$$
   • Por lo tanto, $F(k+1)< 2k+1$.

Conclusión: $F(n)< 2^n \text{para todo} n≥0$

1.2 Relaciones de Recurrencia

Una relación de recurrencia describe cómo calcular un término en función de términos previos.

Métodos de Solución

• Iteración : Expandir la recurrencia hasta encontrar un patrón.
• Fórmula cerrada : Resolver explícitamente para obtener una expresión no recursiva.

Ejemplo: Resolver $T(n)=2T(n−1)+1$ con $T(0)=0$

1. Expandir: $$T(n)=2T(n−1)+1=2(2T(n−2)+1)+1=2^2T(n−2)+2+1$$ Continuando: $$T(n)=2^nT(0)+(2^{n-1}+2^{n-2}+⋯+1)$$
2. Simplificar: La suma es una serie geométrica: $$2^{n-1}+2^{n-2}+⋯+1=2^n-1$$ Por lo tanto: $$T(n)=2^n-1$$

Pasos para Analizar un Problema

• Identificar el caso base.
• Determinar cómo se construye el problema a partir de casos más pequeños.
• Escribir la relación de recurrencia.

Ejemplo: Torres de Hanoi

El problema consiste en mover n discos de una varilla a otra, siguiendo ciertas reglas.

• Caso base: $T(1)=1$ (un solo disco requiere un movimiento).
• Paso recursivo: Para mover $n$ discos, primero mueve $n−1$ discos a una varilla auxiliar, luego mueve el disco más grande, y finalmente mueve los $n−1$ discos restantes.

1.3 Análisis de Código Recursivo/Iterativo

Dado un código recursivo, identifica su relación de recurrencia y prueba su forma cerrada. Ejemplo: Función Factorial

def factorial(n): # se define la funcion factorial con parametro n
    if n == 0: # caso base: si f(0) entonces retorna 1
        return 1
    else: # Paso recursivo: si no es f(0) entonces f(n) = n * f(n-1) por ejemplo f(3)= 3 * f(3-1)
        return n * factorial(n-1)

1. Relación de Recurrencia:
   • Caso base: $F(0)=1$
   • Paso recursivo: $F(n)=n⋅F(n−1)$
2. Forma Cerrada:
   • Hipótesis: $F(n)=n!$
   • Prueba por inducción:

     • Base: $F(0)=1=0!$ Verdadero.

     • Paso inductivo: Supongamos $F(k)=k!$

     • Entonces:$F(k+1)=(k+1)⋅F(k)=(k+1)⋅k!=(k+1)!$

     • Conclusión: $F(n)=n!$