INICIO

Resolución

de problemas

 

 

RECURSIVIDAD

  

Algunas veces es posible particularizar un problema de una forma especial: relacionándolo con una versión más sencilla del mismo problema. A esto se le llama recursividad o recurrencia. Si conocemos cómo se relacionan ambas versiones del problema podríamos realizar un descenso hacia versiones cada vez más sencillas. por lo tanto deberemos conocer cuál es la condición de finitud de este proceso, es decir, la versión más sencilla posible del problema.       

 

Ejemplo: Los números factoriales, que nos dan el número de permutaciones de n elementos como   n! = 1 · 2 · 3 · ... · n

Pueden ser definidos recursivamente así:

                           n! = (n - 1)! · n         siendo  1! = 1  (condición de finitud)

 

Ejemplo: Las Torres de Hanoi.

El problema consiste en lo siguiente: Hay n discos apilados según anchuras decrecientes en un palo A. Hay que pasarlos al palo C, utilizando el palo B como auxiliar. Para ello hay dos normas: nunca se puede pasar más de un disco a la vez y nunca se puede colocar un disco sobre otro de menor tamaño. ¿Cuántos movimientos son necesarios?

Llamemos al problema:    

HANOI  con N discos, desde A pasando por B hasta C

Situación inicial:

En algún momento del proceso hay que pasar el disco mayor desde A a C, y para ello los N-1 discos restantes deben estar en B. Es decir, hay que llegar a este estado:

Para lograrlo, se debe resolver en primer lugar el problema

  HANOI  con N-1 discos, desde A pasando por C hasta B

Y, una vez lograda esa situación:

Pasar el disco N de A a C

Entonces el disco N ya no se debe mover en el resto del proceso y el problema que nos queda es

HANOI  con N-1 discos, desde B pasando por A hasta C

Llegando a la situación final:

 

En resumen:

HANOI  con N discos, desde A pasando por B hasta C

se desglosa en tareas:

HANOI  con N-1 discos, desde A pasando por C hasta B

Pasar el disco N de A a C

HANOI  con N-1 discos, desde B pasando por A hasta C

Es decir, hemos expresado la solución al problema de HANOI con N discos mediante dos llamadas recursivas al problema de HANOI con N-1 discos y un movimiento más.

¿Cuál es el número de movimientos necesarios?... con N discos será el número de movimientos necesarios con N-1 discos, multiplicado por 2, más uno. El caso más sencillo, con 1 disco, se resuelve con 1 movimiento (condición de finitud).

Lo expresamos en una tabla e intentamos encontrar un término general de esa sucesión:

discos                             movimientos                  

   1                                   1                             = 2 -1

   2                                   2 · 1 + 1 = 3             = 4 - 1

   3                                   2 · 3 + 1 = 7             = 8 - 1

   4                                   2 · 7 + 1 = 15           = 16 - 1

 ......

 64                                   ...                            = 264 - 1 = 1,8446744 · 1019

 .....

 N                                                                   = 2N - 1

Dice la leyenda que unos monjes del Tibet se dedican a resolver este problema con 64 discos desde el comienzo de los tiempos y que el fin del mundo llegará cuando terminen su tarea. Según el cálculo anterior, deben hacer decenas de trillones de movimientos... ¡qué alivio!

  

 

 

 

 

 

 

 

 

 

 

 

(C) José María Sorando Muzás

jmsorando@ono.com