38. Introducción a la recurrencia en combinatoria

Una recurrencia expresa el conteo de un problema en función de conteos de tamaños menores, junto con casos iniciales que permiten comenzar el cálculo.

38.1 Introducción

Muchos problemas combinatorios se vuelven más sencillos cuando observamos cómo se relaciona un caso grande con casos pequeños. En lugar de contar directamente todas las configuraciones de tamaño n, clasificamos según la primera decisión y usamos resultados ya conocidos.

Una relación de recurrencia describe esa dependencia. Para obtener valores concretos necesitamos también condiciones iniciales.

38.2 Qué es una recurrencia

Una recurrencia define cada término de una sucesión utilizando uno o varios términos anteriores.

an = regla que utiliza an-1, an-2, ...
junto con uno o más valores iniciales

En combinatoria, an suele representar la cantidad de configuraciones de un problema de tamaño n.

38.3 Partes de una relación de recurrencia

  • Sucesión: valores que representan el conteo.
  • Regla recurrente: relación entre un término y anteriores.
  • Casos base: valores iniciales conocidos.
  • Interpretación: explicación combinatoria de la descomposición.

Sin casos base, una recurrencia no permite calcular ningún valor concreto.

38.4 Ejemplo de una recurrencia simple

Consideremos:

a0 = 1
an = 2an-1

Los valores son:

1, 2, 4, 8, 16, ...

La sucesión cuenta configuraciones en las que cada etapa duplica las posibilidades.

38.5 Simulación de una recurrencia

Elige el tipo de recurrencia y la cantidad de términos. La simulación muestra la sucesión generada paso a paso.

Generador de sucesiones recurrentes

38.6 Recurrencia por casos finales

Una técnica común consiste en clasificar una configuración según su último elemento o su última etapa. Si una solución termina de una forma o de otra, sumamos los conteos de ambos casos.

an = an-1 + an-2

La suma indica que cada configuración termina en uno de dos tipos de casos excluyentes.

38.7 Ejemplo: cubrir una fila

Supongamos que queremos cubrir una fila de n posiciones usando piezas de longitud 1 o 2. Una solución puede terminar con:

  • Una pieza de longitud 1, precedida por una cobertura de n-1 posiciones.
  • Una pieza de longitud 2, precedida por una cobertura de n-2 posiciones.
T(n) = T(n - 1) + T(n - 2)
T(0) = 1, T(1) = 1

38.8 Un ejemplo en JavaScript

La recurrencia de cobertura puede calcularse de forma iterativa.

function formasDeCubrir(n) {
  if (n === 0 || n === 1) return 1;
  let anteriorDos = 1;
  let anteriorUno = 1;

  for (let posicion = 2; posicion <= n; posicion += 1) {
    const actual = anteriorUno + anteriorDos;
    anteriorDos = anteriorUno;
    anteriorUno = actual;
  }
  return anteriorUno;
}

console.log(formasDeCubrir(6));

El algoritmo conserva solo los dos valores anteriores porque son los únicos necesarios para calcular el siguiente.

38.9 Recurrencias y doble conteo

Una recurrencia correcta debe dividir las configuraciones en casos:

  • Que no se superpongan.
  • Que cubran todas las soluciones.
  • Que puedan relacionarse con problemas más pequeños.

Si una configuración pertenece a dos casos, se contará dos veces. Si no pertenece a ninguno, quedará fuera del resultado.

38.10 Casos base

Los casos base representan los problemas más pequeños que podemos resolver directamente.

Para una recurrencia con an-1 y an-2, normalmente necesitamos a0 y a1.

Sin esos valores, la secuencia no queda determinada.

38.11 Recursión y recurrencia

Una recurrencia es una relación matemática. Una función recursiva es una implementación que se llama a sí misma. Ambas ideas están relacionadas, pero no son exactamente lo mismo.

ConceptoDescripción
RecurrenciaDefine un valor mediante términos anteriores.
RecursiónImplementa una función que se invoca con un problema menor.
IteraciónCalcula sucesivamente los valores sin llamadas anidadas.

38.12 Aplicaciones en informática

  • Contar caminos, coberturas y configuraciones.
  • Construir algoritmos de programación dinámica.
  • Analizar sucesiones de soluciones.
  • Descomponer problemas en casos menores.
  • Estudiar el costo de algoritmos recursivos.
  • Resolver distribuciones y particiones.

38.13 Errores frecuentes

  • Omitir un caso base.
  • Usar una recurrencia que cuenta casos superpuestos.
  • No cubrir todas las formas posibles de terminar una configuración.
  • Confundir el índice n con la cantidad de términos.
  • Usar recursión directa sin analizar la repetición de cálculos.

38.14 Qué debes recordar de este tema

  • Una recurrencia relaciona un conteo con problemas más pequeños.
  • Los casos base permiten iniciar el cálculo.
  • La descomposición debe ser completa y sin superposiciones.
  • Las recurrencias pueden implementarse con recursión o iteración.
  • Muchas recurrencias combinatorias surgen al clasificar por la última decisión.
  • Son una base para la programación dinámica.

38.15 Conclusión

La recurrencia permite resolver problemas combinatorios relacionando configuraciones grandes con casos más pequeños. Definir correctamente los casos base y la división en situaciones es tan importante como realizar el cálculo.

En el próximo tema estudiaremos relaciones de recurrencia aplicadas directamente al conteo.

Volver al índice