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:

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 últimas lı́neas imprimen la lista. La coma que hay al final de la última lı́nea evita que Python salte de lı́nea después de imprimir un nodo.

Llamamos este método tal como antes invocamos a imprimeLista:

El resultado es una lista invertida.

Es posible que se pregunte por qué 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 método sobre None. Esta limitación resulta algo incómoda a la hora de escribir código para manipular listas con un estilo orientado a objetos puro.

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