17.4. Listas y recursividad

Es natural expresar muchas operaciones con listas por medio de métodos recursivos. El siguiente ejemplo es un algoritmo recursivo para imprimir una lista hacia atrás:

1. Separar la lista en dos partes: el primer nodo (llamado cabeza) y el resto (llamado cola).
   
2. Imprimir la cola hacia atrás.
   
3. Imprimir la cabeza.
   

Por supuesto, el paso 2, la llamada recursiva, supone que tenemos una manera de imprimir una lista del revés. Pero si suponemos que la llamada recursiva funciona |el acto de fe| entonces podemos estar convencidos de que este
algoritmo funciona.

Todo lo que necesitamos es un caso básico y una forma de demostrar que para cualquier lista podemos obtener el caso básico. Dada la definición recursiva de una lista, un caso básico natural es la lista vacía, representada por None:

   1: def imprimeAlReves(lista):

   2:     if lista == None: return

   3:     cabeza = lista

   4:     cola = lista.siguiente

   5:     imprimeAlReves(cola)

   6:     print cabeza,

 

La primera línea maneja el caso inicial no haciendo nada. Las dos siguientes líneas dividen la lista en cabeza y cola. Las dos ultimas líneas imprimen la lista. La coma que hay al final de la ultima l³nea evita que Python salte de línea después de imprimir un nodo.

Llamamos este metodo tal como antes invocamos a imprimeLista:

   1: >>> imprimeAlReves(nodo1)

   2: 3 2 1

El resultado es una lista invertida.
Es posible que se pregunte por que imprimeLista e imprimeAlReves son funciones y no métodos de la clase Nodo. La razón es que queremos usar None para representar la lista vacía y no es legal llamar un metodo sobre None. Esta limitación resulta algo incomoda a la hora de escribir código para manipular listas con un estilo orientado a objetos puro.

¿Podemos demostrar que imprimeAlReves siempre acabara? En otras palabras,
¿siempre alcanzaremos el caso básico? De hecho, la respuesta es no. Algunas listas harán que el metodo no funcione.