5.5. Más recursividad

Hasta ahora, usted ha aprendido solamente un pequeño subconjunto de Python, pero puede que le interese saber que ese subconjunto es ya un lenguaje de programación completo; con esto queremos decir que cualquier cosa que pueda computarse se puede expresar en este lenguaje. Cualquier programa que se haya escrito alguna vez puede reescribirse utilizando únicamente las características del lenguaje que ha aprendido hasta el momento (de hecho, necesitaría algunas ordenes para controlar dispositivos como el teclado, el ratón, los discos, etc. pero  eso es todo).

Probar tal afirmación es un ejercicio nada trivial, completado por primera vez por Alan Turing, uno de los primeros científicos informáticos (algunos argumentaran que era un matemático, pero muchos de los científicos informáticos pioneros comenzaron como matemáticos). En correspondencia, se la conoce como la tesis de Turing. Si estudia un curso de Teoría de la Computación, tendrá oportunidad de ver la prueba.

Para darle una idea de lo que puede hacer con las herramientas que ha aprendido hasta ahora, evaluaremos una serie de funciones matemáticas que se definen recursivamente. Una definición recursiva es semejante a una definición circular, en el sentido de que la definición contiene una referencia a lo que se define. Una definición verdaderamente circular no es muy útil: fangoso: adjetivo que describe algo que es fangoso.

Si usted viera esa definición en el diccionario, se quedaría confuso. Por otra parte, si ha buscado la definición de la función matemática factorial, habrá visto algo semejante a lo siguiente:

0! = 1
n! = n ¢ (n ¡ 1)!

Esta definición establece que el factorial de 0 es 1, y que el factorial de cualquier otro valor, n, es n multiplicado por el factorial de n ¡ 1.
Así pues, 3! es 3 veces 2!, que es 2 veces 1!, que es una vez 0!. Juntándolos todos, , 3! es igual a 3 veces 2 veces 1 vez 1, que es 6.

Si puede escribir una definición recursiva de algo, normalmente podrá escribir un programa de Python para evaluarlo. El primer paso es decidir cuales son los parámetros para esta función. Con poco esfuerzo llegara a la conclusión de que factorial toma un único parámetro:

   1: def factorial(n):

   2:     Si resultase que el argumento fuese 0, todo lo que hemos de hacer es devolver 1:

   3: def factorial(n):

   4:     if n == 0:

   5:     return 1

   6:     

 

En otro caso, y he aquí la parte interesante, tenemos que hacer una llamada recursiva para hallar el factorial de n ¡ 1 y luego multiplicarlo por n:

   1: def factorial(n):

   2:     if n == 0:

   3:         return 1

   4:     else:

   5:         recursivo = 

   6:         factorial(n-1)

   7:         resultado = n * recursivo

   8:         return resultado

El flujo de ejecucion de este programa es similar al de cuenta atras de la Sección 4.9. Si llamamos a factorial con el valor 3:

Puesto que 3 no es 0, tomamos la segunda rama y calculamos el factorial de n-1...

Puesto que 2 no es 0, tomamos la segunda rama y calculamos el factorial de n-1...

Puesto que 1 no es 0, tomamos la segunda rama y calculamos el factorial de n-1...

Puesto que 0 es 0, tomamos la primera rama y devolvemos el valor 1 sin hacer mas llamadas recursivas.

El valor de retorno (1) se multiplica por n, que es 1, y se devuelve el resultado.

El valor de retorno (1) se multiplica por n, que es 2, y se devuelve el resultado.

El valor de retorno (2) se multiplica por n, que es 3, y el resultado 6, se convierte en el valor de retorno de la llamada a la funcion que comenzo todo el proceso.

He aquí el aspecto que tiene el diagrama de pila para esta secuencia de llamadas a función:

Los valores de retorno se muestran segun se pasan hacia la parte superior de la pila. En cada marco, el valor de retorno es el valor de resultado, que es el producto de n por recursivo.

Nótese que en el ultimo marco las variables locales recursivo y resultado no existen porque la rama que las crea no se ejecuta.