4.9. Recursividad

Ya mencionamos que es legal que una función llame a otra, y de ello hemos visto ya varios ejemplos. Olvidamos mencionar que también es legal que una función se llame a sí misma. Puede no resultar evidente por que es bueno esto, pero viene a resultar una de las cosas mas interesantes y curiosas que puede hacer un programa. Examine por ejemplo la siguiente función:

   1: def cuenta_atras(n):

   2:     if n == 0:

   3:         print "Despegando!"

   4:     else:

   5:         print  n cuenta_atras(n-1)

   6:     

cuenta atras espera que su parametro, n, sea un entero positivo. Si n el parámetro es cero, muestra la palabra “¡Despegando!". En otro caso, muestra n y luego llama a la funcion llamada cuenta atras (ella misma) pasandole como argumento n-1.

¿Que sucede si llamamos a la funcion de la siguiente manera?

   1: >>> cuenta_atras(3)

La ejecucion de cuenta atras comienza con n=3, y puesto que n no es cero, da como salida el valor 3, y luego se llama a sí misma ...

La ejecucion de cuenta atras comienza con n=2, y puesto que n no es cero, muestra el valor 2 y luego se llama a sí misma ...

La ejecucion de cuenta atras comienza con n=1, y puesto que n no es cero, muestra el valor 1, y luego se llama a
sí misma...

La ejecucion de cuenta atras comienza con n=0, y puesto que n es cero, muestra la palabra \Despegando!" y luego retorna.

La cuenta atras que dio n=1 retorna.

La cuenta atras que dio n=2 retorna.

La cuenta atras que dio n=3 retorna.

Y entonces ya esta de vuelta en main (menudo viaje). De manera que la salida completa presenta el siguiente aspecto:

3

2

1

¡Despegando!

Como segundo ejemplo, consideremos de nuevo las funciones nuevaLinea and tresLineas.

   1: def nuevaLinea():

   2:     print    

   3: def 

   4:     tresLineas():

   5:     nuevaLinea()

   6:     nuevaLinea()

   7:     nuevaLinea()

Aunque todas funcionan, no serían de mucha ayuda si quisiera mostrar 2 líneas nuevas o 106. Una mejor alternativa será:

   1: def nLineas(n):

   2: if n > 0:

   3: print

   4: nLineas(n-1)

Este programa es parecido a cuenta atras; mientras n sea mayor que cero, muestra una nueva l³nea, y luego se llama a sí misma para mostrar >n-1 nuevas líneas mas. De esta manera, el numero total de nuevas l³neas es 1 + (n-1), que si rescata su algebra vera que es n.

El proceso por el que una funcion se llama a s³ misma se llama recursividad, y dichas funciones se denominan recursivas.