Blogia
Tio Petros

Resolución por recurrencia.

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 -

me podrian ayudar como encontrar la solicion a esta relacion de recurrencia Rn = Rn-1 +Rn-2 +1 con Ro=1 y R1=2

abner -

quiero saber como se hace las recurrencias

abner -

quiero sabe r como se hace las recurrencias

damian -

Hola.

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 -

Si hablas de Fibonacci Tio Petros podrías incluir algo sobre el problema de tener que repetir muchos cálculos y las soluciones informáticas que existen para eso :D

Sam Berimbad -

No sé cuáles serán, exactamente, las limitaciones tipográficas del blog. Pero, respecto a tu primer motivo, no nos prives de disfrutar con tu versión del tema, ¡diosss, cómo las disfruto!. Es una buena oportunidad para que nos cuentes alguna curiosidad del número de oro...

Tio Petros -

Cuando en el mensaje anterior dice "se hace uso de los estados anteriores" debe decir "se hace uso de DOS estados anteriores".

Tio Petros -

Efectivamente, en la definición recursiva de Fibonacci se hace uso de los estados anteriores, de forma que se necesitan dos condiciones iniciales (los dos primeros valores de la sucesión. EL paso de la forma recursiva a la normal no es nada trivial, y necesita del auxilio de alguna técnica adicional ( funciones generatrices). Estoy dudando si hablar de ello por dos motivos:
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 -

Muy interesante. Me recuerda la serie de Fibonacci y la fórmula directa que no sé si será más habitual que la recursiva, pero sí muy misteriosa.

Rimblow -

Vaya peazo método que has descrito, todavía le estoy dando vueltas, hay que ver las cosas que se le ocurren a la gente,....que envidia....sana...