10

Universidad de Santiago de Chile
Facultad de Ingeniería
Fundamentos de Computación y Programación

Recursión en Python
Recordemos el problema planteado anteriormente:
Supongamos que vamos a la casa de un amigo pero se nos olvidó traer la dirección completa y
sólo tenemos el nombre de la calle en la que vive. Al llegar nos damos cuenta que es un pasaje
con 8 casas a cada lado ¿Qué podemos hacerpara no perder el viaje? Asumiendo que los
vecinos no se conocen entre sí, y que no tenemos forma de contactarlo previamente, lo mejor
sería simplemente ir y golpear en la primera casa, y preguntar si nuestro amigo vive ahí. En
caso de que la respuesta sea no, tendríamos que repetir el proceso con las siguientes casas,
hasta encontrar la de nuestro amigo.

En la clase anterior aprendimos la forma enque podíamos resolver este problema,
planteando un ciclo while. Sin embargo, esta no es la única posibilidad. En el problema
anterior, supongamos que a la casa del amigo vamos cuatro personas. Para encontrar
más velozmente a nuestro amigo, ¿no sería mejor, en vez de ir todos preguntando casa
por casa, qué cada uno de nosotros preguntara en dos casas distintas?
De esta forma cada uno de nosotrosestá resolviendo instancias más pequeñas del
problema de búsqueda. Luego podemos reunirnos nuevamente y conocer cuál es la
casa de nuestro amigo.

Funciones recursivas
Para ver como esto se puede llevar a Python miremos el siguiente programa.
Recursivo.py
1. def recursivo(n):
2.
if n == 0 :
3.
return 1
4.
return n * recursivo(n - 1)
5.
6.
7. #
8. # Bloque principal
9. #
10.
11.print recursivo(5)¿Qué tiene de especial? Si nos fijamos, la función recursivo() se llama a sí misma,
pero cambiando el valor del parámetro actual. A esta forma de repetir las sentencias del
cuerpo de una función se le conoce como recursión.
1

Universidad de Santiago de Chile
Facultad de Ingeniería
Fundamentos de Computación y Programación

Recuerda
Como primera aproximación, podemos decir que una función recursivaes aquella
que se define en términos de sí misma: “para entender la recursividad hay que
entender la recursividad”. Para entender mejor la definición, miremos la siguiente
imagen de una lata de polvos de hornear ROYAL:

Si miramos la etiqueta es autorreferente, pues su etiqueta es la misma lata, y
dentro de esa lata, está nuevamente una lata y así sucesivamente.

Pregunta 1
Trabaja ahora con tugrupo en responder la pregunta 1 de la actividad.

Si nos fijamos en el recuadro, tanto en la foto como en la definición de recursividad escrita
en cursiva, existe el problema de que hipotéticamente podemos realizar el proceso de
repetir la definición de recursividad, o encontrar la etiqueta dentro de la lata de la etiqueta
infinitamente, es decir, no hay forma de detenerla. Sin embargo, elprograma
Recursivo.py, si se detiene. ¿Qué hace la función recursivo(n) para no llamarse a sí
misma infinitamente?

2

Universidad de Santiago de Chile
Facultad de Ingeniería
Fundamentos de Computación y Programación

La respuesta a esta pregunta es sencilla. Si miramos cuidadosamente veremos que, en
cada llamada, mientras el valor de n sea positivo (no cumple la condición del if de la
línea 2), elvalor de n disminuye en 1 (llamada de la línea 4). Por otra parte, la función
deja de llamarse a sí misma cuando n llega al valor 0 (sentencia de retorno de la línea 3
si la condición del if de la línea 2 se cumple).
Importante
Una función recursiva necesariamente debe contener por lo menos estos dos
elementos:
Regla de recursión:
n * recursivo (n - 1)
Condición de borde:
if(n == 0):
return 1

Ejemplo1
Se define el factorial de un entero no negativo n, denotado por n!, como la
multiplicación de todos los números naturales menores o iguales que n.
Además se define que:

Podemos ver fácilmente que el caso de 0! es la condición de borde de la función
factorial de un entero no negativo n.
Veamos ahora la regla de recursión. Sabemos que:

(
Que es lo mismo que decir:

) (

(
(
(

)

)
) (
)

)...