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.

0