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 |