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:

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

             e-mail                         web bajo licencia Ceative Commons 3.0 España