18.5. Una función recursiva matemática

Es muy común tener definiciones inductivas de operaciones, como por ejemplo:

x! = x ∗ (x − 1)! si x > 0, 0! = 1

Este tipo de definición se traduce naturalmente en una función en Python:

def factorial(n):
    """ Precondición: n entero >=0
        Devuelve: n! """
    if n == 0:
        return 1

    return n * factorial(n-1)

Esta es la ejecución del factorial para n=0 y para n=3.

>>> factorial(0)
1
>>> factorial(3)
6

El sentido de la instrucción de la instrucción n * factorial (n-1) es exactamente el mismo que el de la definición inductiva: para calcular el factorial dense debe multiplicar n por el factorial de n − 1.

Dos piezas fundamentales para garantizar el funcionamiento de este programa son:

• Que se defina un caso base (en este caso la indicación, no recursiva, de cómo calcular factorial(0)), que corta las llamadas recursivas.
• Que el argumento de la función respete la precondición de que n debe ser un entero mayor o igual que 0.

Dado que ya vimos la pila de evaluación, y cómo funciona, no debería llamarnos la atención que esto pueda funcionar adecuadamente en un lenguaje de programación que utilice pila para evaluar.

Para poder analizar qué sucede a cada paso de la ejecución de la función, utilizaremos una versión más detallada del mismo código, en la que cada paso se asigna a una variable.

def factorial(n):
    """ Precondición: n entero >=0
        Devuelve: n! """
    if n == 0:
        r = 1
        return r

    f = factorial(n-1)
    r = n * f
    return r

Esta porción de código funciona exactamente igual que la anterior, pero nos permite ponerles nombres a los resultados intermedios de cada operación para poder estudiar qué sucede a cada paso. Analicemos, entonces, el factorial(3) mediante la pila de evaluación: