Resolución por recurrencia.
Hemos ido viendo varias herramientas para resolución de problemas que en principio parecen difíciles, pero que se disuelven en la más meridiana claridad después de ser enfocados desde una perspectiva conveniente para ellos. Vimos el principio de correspondencia, que convertía por arte de magia algunos problemas muy difíciles en apariencia en cuestiones sencillísimas si era bien aplicado. Comentamos en su día que este método tiene un precio: para si aplicación no existen más fórmulas que la agudeza mental y la habilidad.Otro método muy corriente y de resultados magníficos si es bien empleado es el de recurrencia .
El método de inducción para demostrar afirmaciones que implican a los números reales consistía en demostrar la afirmación para n=1, y demostrar que si se cumple para n, se cumple necesariamente para (n+1). Pues bien; en cierto modo, la resolución de problemas por recurrencia es la inversa de la inducción. Me explico:
Cuando debemos encontrar la solución de un problema para cualquier valor de uno de sus parámetros enteros, si abordar el problema directamente nos es imposible podemos hallar la solución para N= n en función del valor de la solución para N=(n-1). A veces esto no será posible, y la función solución deberá ser expresada en función de varios valores anteriores , no de uno solo. Cuando tengamos expresada esta relación de recurrencia, más el calor inicial o los valores iniciales necesarios, diremos que la función objetivo está ya definida de forma recursiva .
En efecto, la función, a pesar de su apariencia extraña, definida en función de sí misma, está perfectamente definida. El paso de la forma recursiva a la forma habitual en función del parámetro n puede no ser trivial, y necesitar de ciertas herramientas algebraicas, pero esa es otra cuestión.
Vemos un ejemplo de un problema aparentemente dificil resuelto de por recurrencia.
Si trazamos una serie de rectas en un plano, sin orden ni concierto alguno, ¿en cuántas regiones queda dividido el plano?
Cuando trazamos al azar, la probabilidad de que dos rectas sean paralelas es nula, así como la probabilidad de que tres rectas se corten en el mismo punto, así que supondremos esta situación: no hay rectas paralelas, ni puntos de corte de más de dos rectas.
Por la ilustración podeis ver que la cuestión es algo enmarañada en apariencia. Pensemos que tenemos ya (n-1) rectas y dibujamos la número n. Como no hay paralelas, nuestra nueva recta cortará a las (n-1) actuales en (n-1) puntos, que la dividirán en n trozos. Dos de estos trozos serán semirectas infinitas y el resto simples segmentos. Lo que es muy fácil e ver es que cada uno de estos n trozos de recta dividen una región en dos, por lo que nuestra nueva recta incrementará en n el número de regiones del plano.
Expresado en fórmulas: siendo Rn el número de regiones pedido:
Rn = Rn-1 + n
R1 = 2 (condición inicial).
Esta es la definición recursiva de nuestra función objetivo. Como no necesitamos más que una llamada a la propia función en un valor anterior, necesitamos una sola condición inicial: el plano es dividido en dos regiones por la primera recta.
Una mínima manipulación en este caso nos lleva a la expresión de Rn en función de n:
Rn = R1 + [ n + (n-1) + ... + 2 ]
Rn = 1 + [n(n-1)]/2.
El problema que vimos hace algunos meses de los apretones de manos también puede ser resuelto de forma recursiva sin ninguna complicación. En todo caso, obtenemos una definición recursiva de la función objetivo del problema, que condensa toda la información de la misma, aunque no está expresada de la forma habitual. Encontrar esta forma habitual (dependencia funcional del parámetro n) es tarea de dificultad muy diversa. Era caso trivial en nuestro ejemplo, y en otros casos es bastante más complicado. Aún así, cuando no podemos o no sabemos encontrar dicha forma normal, si tenemos la definición recursiva , tenemos resuelto el problema.
10 comentarios
claudio -
abner -
abner -
damian -
He llegado ha esta página (http://tiopetrus.blogia.com/2004/2004/010901-resolucion-por-recurrencia-.php) por el tema del método de la recurrencia. He leído tu ejemplo y me parece que la expresión dada como solución es incorrect.
R[n] = 1 + n(n-1)/2
no da el valor 2 para n=1 (condición inicial del enunciado). Creo que la expresión correcta sería:
R[n] = 2 + (n-1)(n+2)/2
Un saludo
P.D: me sorprende que nadie se haya dado cuenta del error. Ya hace más de año y medio que se publicó.
jose -
Sam Berimbad -
Tio Petros -
Tio Petros -
1.- Fibonacci está tratado en mil sitios, y en muchos de ellos muy bien.
2.- No sé si no será un poco difícil explicar la forma de pasar de una forma a otra con las utilidades tipográficas del blog... ya veremos.
Shunt -
Rimblow -