Ver índice de contenidos del libro

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:

Instrucción Contexto de factorial Resultado
factorial(3) n → 3 -
if n == 0: n → 3 -
f = factorial (n-1) n → 3 Se suspende el cálculo. Se llama a factorial(2)
factorial(2) n → 2 / n → 3 -
if n == 0: n → 2 / n → 3 -
f = factorial (n-1) n → 2 / n → 3 Se suspende el cálculo. Se llama a factorial(1)
factorial(1) n → 1 / n → 2 / n → 3 -
if n == 0: n → 1 / n → 2 / n → 3 -
f = factorial (n-1) n → 1 / n → 2 / n → 3 Se suspende el cálculo. Se llama a factorial(0)
factorial(0) n → 0 / n → 1 / n → 2 / n → 3 -
if n == 0: n → 0 / n → 1 / n → 2 / n → 3 -
r = 1 n → 0 r → 1 / n → 1 / n → 2 / n → 3 -
En factorial(0): return r n → 1 f → 1 -
En factorial(1): f = factorial (n-1) n → 2 / n → 3 -
r = n * f n → 1 f → 1 r → 1 / n → 2 / n → 3 -
En factorial(1): return r n → 2 f → 1 -
En factorial(2): f = factorial (n-1) n → 3 -
r = n * f n → 2 f → 1 r → 2 / n → 3 -
En factorial(2): return r n → 3 f → 2 -
En factorial(3): return r n → 3 f → 2 -
r = n * f n → 3 f → 2 r → 6 -
return r Pila vacía Devuelve el valor 6
Copyright (c) 2011-2014 Rosita Wachenchauzer, Margarita Manterola, Maximiliano Curia, Marcos Medrano, Nicolás Paez. La copia y redistribución de esta página se permite bajo los términos de la licencia Creative Commons Atribución - Compartir Obras Derivadas Igual 3.0 siempre que se conserve esta nota de copyright.