Recursión

Funciones recursivas

Jonatan Gómez Perdomo, Ph. D.

jgomezpe@[Link]

Arles Rodrı́guez, Ph.D.

aerodriguezp@[Link]

Camilo Cubides, Ph.D. (c)

eccubidesg@[Link]

Carlos Andrés Sierra, [Link].

casierrav@[Link]

Research Group on Artificial Life – Grupo de investigación en vida artificial – (Alife)

Computer and System Department
Engineering School
Universidad Nacional de Colombia
 Introducción Recursión –1–

Agenda

1 Introducción

2 Programación recursiva

3 Ejemplos de funciones recursivas

4 Algunos problemas clásicos de programación recursiva

5 Teorema fundamental de la programación recursiva

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Introducción Recursión –2–

Introducción I

Aunque a muchos el término recursión les parece extraño, la recursión es

un concepto muy natural, tanto como para definir los números naturales.

Pensemos cuando tenemos un problema en nuestro diario vivir y un familiar

muy respetado por nosotros dice “sea recursivo”, ¿Qué nos quieren decir?

Que nos miremos a nosotros mismos, que sólo contemos con nuestros
propios recursos para solucionar nuestros problema, que no se necesita
algo adicional. Que pensemos que lo podemos solucionar para que lo
solucionemos.

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Programación recursiva Recursión –3–

Agenda

1 Introducción

2 Programación recursiva

3 Ejemplos de funciones recursivas

4 Algunos problemas clásicos de programación recursiva

5 Teorema fundamental de la programación recursiva

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Programación recursiva Recursión –4–

Recursividad I

Dado que la mayorı́a de los lenguajes de programación disponen de un

mecanismo para definir funciones (son estructurados), y dentro de la
definición del cuerpo de las funciones se puede invocar el llamado a
funciones (lo que se llama composición de funciones en matemáticas),
una pregunta natural que uno se puede hacerse es: ¿se puede invocar
dentro de una función a la misma función para definirse?, en algunos
lenguajes de programación esto si se puede hacer, a estos se les denominan
lenguajes de programación con recursividad. Por ejemplo: C++, Java,
Mathlab, Python, Lisp, y la mayorı́a de lenguajes de programación.

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Programación recursiva Recursión –5–

Recursividad II
El mecanismo de la recursión

Si un problema de cierto tamaño T puede ser solucionado usando

instancias del mismo problema pero de menor tamaño t (t < T ), y
además se conoce la solución de algunas instancias de menor tamaño (t0 )
que no dependan del problema, entonces se puede aplicar un mecanismo
recursivo para implementar la solución del problema usando un lenguaje de
programación.

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Programación recursiva Recursión –6–

Recursividad III

Definición (Definición débil de función recursiva)

Una función f : A → B se dice recursiva si y sólo si f está definida por

casos (mediante un predicado sobre los argumentos), en donde al menos
uno de los casos se define usando la misma función f y los argumentos, y
al menos uno de los otros casos se define usando solamente los
argumentos sin involucrar la función f .

Aquellos casos en los cuales se invoca a la misma función se llaman casos

recursivos, y aquellos casos en los cuales no interviene la función se
denominan casos base.

Nota
En teorı́a una función no necesita tener casos base, pero cualquier función
recursiva escrita sin casos base generará un bucle infinito (ciclo sin fin).

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Programación recursiva Recursión –7–

Recursividad IV
Metodologı́a para resolver problemas recursivamente

Solucionar problemas, y en particular programar, de manera “recursiva” se

puede alcanzar siguiendo las tres máximas del profesor Jonatan Gómez.

1 Piense que está bien para que esté bien.

2 Siempre se es el primero y el último.
3 Un problema es simple o se puede dividir en problemas que se pueden
solucionar siguiendo las tres máximas del profesor Jonatan Gómez.

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Programación recursiva Recursión –8–

Introducción
Problema 1.1

Problema
Calcular la suma de los números naturales desde el 0 hasta n.

Solución
Máximas dos y tres: El problema se puede solucionar si se pueden sumar
los números naturales desde el 0 hasta en n − 1 pues sólo
serı́a sumar ese número con el número n.
Máxima uno: Se supone que la función que suma los números naturales
desde el 0 hasta el n está bien por lo tanto se puede usar
para sumar los números naturales desde el 0 hasta el n − 1.
Máximas dos y tres: Sumar los números naturales desde el 0 hasta el 0 es
fácil, se debe retornar 0 pues es el primer número natural.
De esta manera será el último número en ser considerado en
la suma.
J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN
 Programación recursiva Recursión –9–

Introducción
Problema 1.2

Solución (continuación)

sumar : N → N
(
n + sumar (n − 1), si n > 0;
(n) 7→
0, en otro caso.

El programa quedarı́a como sigue

def sumar(n):
if n > 0:
return n + sumar(n-1)
else:
return 0

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Programación recursiva Recursión – 10 –

Introducción
Problema 2.1

Problema
Calcular la suma de los números almacenados en una lista.

Solución
Máximas dos y tres: Supongamos que la lista tiene n números. El
problema se puede solucionar si se pueden sumar los
primeros n − 1 números en la lista pues sólo serı́a sumar ese
número con el número que está en la posición n − 1.
Máxima uno: Se supone que la función que suma de los primeros n
números de una lista está bien por lo tanto se puede usar
para sumar los primeros n − 1 números en la lista.
Máximas dos y tres: Sumar los primeros 0 números de la lista es fácil, se
debe retornar 0 (no hay números que sumar).

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Programación recursiva Recursión – 11 –

Introducción
Problema 2.2

Solución (continuación)

sumar parcial : N∗ × N → N
(
Ln−1 + suma parcial(L, n − 1), si n > 0;
(L, n) 7→
0, en otro caso.

sumar lista : Nm → N


(L) 7→ sumar parcial L, m

Por notación, m es la longitud de la lista L.

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Programación recursiva Recursión – 12 –

Introducción
Problema 2.3

El programa quedarı́a:

def sumar_parcial(L,n):
if n > 0:
return L[n-1] + sumar_parcial(L,n-1)
else:
return 0

def sumar_lista(L):
return sumar_parcial(L,len(L))

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Programación recursiva Recursión – 13 –

Introducción
Problema 3.1

Problema
Determinar si un carácter está en una cadena.

Solución
Máximas dos y tres: Supongamos que la cadena tiene n caracteres. El
problema se puede solucionar si se puede determinar si un
carácter está entre los primeros n − 1 caracteres pues es mirar
si es el último o está entre los primeros n − 1 caracteres.
Máxima uno: Se supone que la función que determina si un carácter está
entre los primeros n está bien, por lo tanto se puede usar
para determinar si el carácter está entre los primeros n − 1
caracteres.
Máximas dos y tres: Determinar si está entre los primeros 0 caracteres de
la cadena es fácil, se debe retornar falso, ya que la cadena
vacı́a no contiene caracteres.
J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN
 Programación recursiva Recursión – 14 –

Introducción
Problema 3.2

Solución (continuación)

buscar parcial : ASCII∗ × ASCII × N → B

(
(strn−1 ≡ ch) ∨ buscar parcial(str , ch, n − 1), si n > 0;
(str , ch, n) 7→
F, en otro caso.

buscar : ASCIIm × ASCII → B

(str , ch) 7→ buscar parcial str , ch, m

Por notación, m es la longitud de la cadena str .

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Programación recursiva Recursión – 15 –

Introducción
Problema 3.3

El programa quedarı́a:

def buscar_parcial(str,ch,n):
if n > 0:
return (str[n-1] == ch) or buscar_parcial(str,ch,n-1)
else:
return False

def buscar(str,ch):
return buscar_parcial(str,ch,len(str))

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Ejemplos de funciones recursivas Recursión – 16 –

Agenda

1 Introducción

2 Programación recursiva

3 Ejemplos de funciones recursivas

4 Algunos problemas clásicos de programación recursiva

5 Teorema fundamental de la programación recursiva

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Ejemplos de funciones recursivas Recursión – 17 –

Lectura y traducción I

Ejemplo
Sea f la función definida por:

f :N→B

V ,
 si n = 0;
(n) 7→ F , si n = 1;

f (n − 2), en otro caso.


¿Cuál es el resultado de evaluar la función f con los valores

n = 0, 1, 2, 3, 4, 5, 6, 7, 8?
¿qué función matemática es f ?
¿Cuál es su traducción a Python?

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Ejemplos de funciones recursivas Recursión – 18 –

Lectura y traducción II

Ejemplo (continuación)
La traducción de la función f a Python es

def f(n):
if n == 0:
return True
elif n == 1:
return False
else:
return f(n-2)

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Ejemplos de funciones recursivas Recursión – 19 –

Lectura y traducción III

Ejemplo
Sea g la función definida por:
g :N→N



0, si n = 0;

1, si n = 1;
(n) 7→


2, si n = 2;

g (n − 3), en otro caso.

¿Cuál es el resultado de evaluar la función g con los valores

n = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9?
¿qué función matemática es g ?
¿Cuál es su traducción a Python?

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Ejemplos de funciones recursivas Recursión – 20 –

Lectura y traducción IV

Ejemplo (continuación)
La traducción de la función g a Python es

def g(n):
if n == 0:
return 0
elif n == 1:
return 1
elif n == 2:
return 2
else:
return g(n-3)

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Ejemplos de funciones recursivas Recursión – 21 –

Lectura y traducción V

Ejemplo
Sea h la función definida por:
h :N×N→N
(
n, si m = 0;
(n, m) 7→
h(n + 1, m − 1), en otro caso.
¿Cuál es el resultado de evaluar la función h con los valores
(n, m) = (2, 3), (8, 5), (6, 6)?
¿qué función matemática es h?
¿Cuál es su traducción a Python?

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Ejemplos de funciones recursivas Recursión – 22 –

Lectura y traducción VI

Ejemplo
La traducción de la función h a Python es

def h(n,m):
if m == 0:
return n
else:
return h(n+1,m-1)

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Ejemplos de funciones recursivas Recursión – 23 –

Problema

Problema
Diseñe un modelo matemático que permita calcular la función producto,
es decir, que reciba dos (2) números naturales y retorne la multiplicación
del primer número por el segundo.

No se pueden utilizar los operadores de multiplicación ni de división (ni

entera ni real).

Codifique el modelo matemático utilizando el lenguaje Python.

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 24 –

Agenda

1 Introducción

2 Programación recursiva

3 Ejemplos de funciones recursivas

4 Algunos problemas clásicos de programación recursiva

5 Teorema fundamental de la programación recursiva

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 25 –

Potencia de un número I

Ejemplo
En este ejemplo se definirá una función recursiva que permita hallar un
número real elevado a un número natural. Para expresar una función que
calcule esta operación, en primera instancia se construye la expresión
potencia : R × N → R que define la función que tiene como entrada un
número real que representa la base y un número natural que indica el
exponente, y como salida se obtendrá un número real que será la potencia.
Por facilidad, aquı́ se asumirá que 00 = 1.

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 26 –

Potencia de un número II

Ejemplo (continuación)
Ahora observesé que en general si se tiene una base b y un exponente n,
entonces por definición

bn = b
| ∗ b ∗ b ∗{z· · · ∗ b ∗ b}
n–veces

si se usa la propiedad asociativa del producto de números reales, se tiene

que
bn = b
| ∗ b ∗ b ∗{z· · · ∗ b ∗ b} = |(b ∗ b ∗ ·{z
· · ∗ b ∗ b) ∗ b
}
n–veces n−1–veces

lo que es equivalente a

bn = b · · ∗ b ∗ b) ∗ b = b n−1 ∗ b
| ∗ b ∗ b ∗{z· · · ∗ b ∗ b} = |(b ∗ b ∗ ·{z }
n–veces n−1–veces

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 27 –

Potencia de un número III

A partir de esta observación se puede dar una definición recursiva usando
funciones. La declaración de esta función junto con su cuerpo se hará de
la siguiente manera
potencia(b, n) = p
Si se establecen las variables:

b := Base
n := Exponente
p := Potencia b n

entonces

potencia : R × N → R
(
1, si n = 0;
(b, n) 7→
potencia(b, n − 1) ∗ b, en otro caso.

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 28 –

Potencia de un número IV

La codificación en Python de esta función es

def potencia(b, n):

if n == 0:
return 1
else:
return potencia(b,n-1) * b

Una solicitud por consola de la base y el exponente puede ser

base = float(input("Por favor digite la base: "))

exp = int(input("Por favor digite el exponente: "))
print(base, "^", exp, "=", potencia(base, exp))

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 29 –

Principio del producto para conteo de listas I

Ejemplo
Suponga que se seleccionan cuatro cartas distintas de una baraja de póker,
que se van a representar por los sı́mbolos

¨ © ª «

si con estas cartas se conforma el conjunto cartas = ¨, ©, ª, « . ¿De
cuántas formas distintas se pueden organizar las cartas?.

Solución
Como se van a listar todas las formas posibles en que se pueden organizar
las cartas, el orden si importa.

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 30 –

Principio del producto para conteo de listas II

Solución (continuación)
Una estrategia para encontrar el número de listas puede ser el siguiente:
1 Se selecciona una carta del conjunto cartas de forma arbitraria pero
fija, por ejemplo la carta ©.
2 Ya fijada la carta ©, el resto del trabajo consiste en hallar el número
de formas distintas de organizar
 las
cartas restantes, es decir, el
conjunto cartas r {©} = ¨, ª, « .
3 Ahora por ejemplo se selecciona la carta « de forma arbitraria pero
fija.
4 A continuación, el trabajo se reduce a hallar el número de formas
distintas de organizar
 las cartas restantes, es decir, el conjunto
cartas r {©, «} = ¨, ª .

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 31 –

Principio del producto para conteo de listas III

Solución (continuación)
5 Posteriormente, por ejemplo se puede seleccionar de forma arbitraria
pero fija la carta ª.
6 Para finalizar, el trabajo se reduce a hallar el número de formas
distintas de organizarlas cartas restantes, es decir el conjunto
cartas r {©, «, ª} = ¨ . Como para este conjunto sólo se tiene una
opción, entonces el número de formas distintas de organizar un
conjunto de una carta es 1.
Siguiendo los pasos anteriores, se obtuvo la lista

© « ª ¨

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 32 –

Principio del producto para conteo de listas IV

Solución (continuación)
Del análisis previo se puede concluir que el número de formas de listar los
elementos de un conjunto con cuatro elementos se puede representar de la
siguiente manera
4 3 2 1
↓ ↓ ↓ ↓
Carta 1 Carta 2 Carta 3 Carta 4

de lo anterior y del principio del producto se puede afirmar que el número

de todas la posibles listas que se forman con las cartas ¨, ©, ª, « es
4
Y
i = 1 · 2 · 3 · 4 = 24 = 4!
i=1

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 33 –

Función factorial I

En general, para un conjunto A con cardinal n (|A| = n), se tiene que el

número de formas de listar todos los ordenamientos en que se pueden
organizar los elementos de A es
n
Y
i = n ∗ (n − 1) ∗ (n − 2) ∗ · · · ∗ 3 ∗ 2 ∗ 1
i=1

este valor que depende solamente de n, es una función, se denota por el

sı́mbolo n! y se llama el factorial del número n. Para el caso del conjunto
∅, se puede demostrar que 0! = 1. A partir de la asociatividad de la
multiplicación de los naturales se tiene que

n! = n ∗ (n − 1) ∗ (n − 2) ∗ · · · ∗ 3 ∗ 2 ∗ 1 = n ∗ (n − 1)!
| {z }
n−1–veces

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 34 –

Función factorial II

A partir de lo anterior se puede obtener una función recursiva para el

factorial de n (n!), que nombraremos

fact(n) = f

Si se establecen las variables:

n := Número al cual se le va a calcular el factorial

f := Factorial de n

entonces

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 35 –

Función factorial III

fact : N → N
(
1, si n = 0;
(n) 7→
n ∗ fact(n − 1), en otro caso.

La codificación en Python de esta función es

def fact(n):
if n == 0:
return 1
else:
return n * fact(n-1)

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 36 –

Pago del interés compuesto mes vencido I

Ejemplo
Supónga que usted solicita un préstamo de $ 1’000.000 durante un año, el
prestamista cobra un interés del 5% mensual con la modalidad de interés
compuesto mes vencido. ¿Cuál es el total del dinero que debe pagar
cuando ha transcurrido el año por el cual solicitó el préstamo, resolviendo
el problema recursivamente?.

Solución
Para calcular el valor solicitado hay que observar que para cero (0) meses
hay que pagar
pago(0) = $10 000.000

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 37 –

Pago del interés compuesto mes vencido II

Solución (continuación)
Para calcular la cantidad de dinero que hay que pagar al cabo de los 12
meses, es suficiente con tener en cuenta que en el mes 12 se debe pagar lo
que se debe en el mes 11 más los intereses que se producen en ese mes,
por ejemplo si pago(11) es el valor del pago en el mes 11, entonces la
cantidad de dinero que hay que pagar en el mes 12 es igual a

pago(12) = pago(11) + pago(11) ∗ 0.05

= pago(11)(1 + 0.05)
= pago(11) ∗ 1.05

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 38 –

Pago del interés compuesto mes vencido III

Solución (continuación)
ahora para calcular el valor a pagar en el mes 11 se puede hacer un
razonamiento similar, y para todos los meses anteriores hasta el mes
cero (0) se hace de manera similar, lo que genera un esquema recursivo
como el que se presenta a continuación

pago(12) = pago(11) ∗ 1.05 pago(5) = pago(4) ∗ 1.05

pago(11) = pago(10) ∗ 1.05 pago(4) = pago(3) ∗ 1.05
pago(10) = pago(9) ∗ 1.05 pago(3) = pago(2) ∗ 1.05
pago(9) = pago(8) ∗ 1.05 pago(2) = pago(1) ∗ 1.05
pago(8) = pago(7) ∗ 1.05 pago(1) = pago(0) ∗ 1.05
pago(7) = pago(6) ∗ 1.05 pago(0) = $ 10 000.000
pago(6) = pago(5) ∗ 1.05

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 39 –

Pago del interés compuesto mes vencido IV

Solución (continuación)
Ası́, si m = $10 000.000, i = 0.05 y n = 12, se tiene que el pago al cabo de
los 12 meses será de pago(12) = $ 10 795.856, 326.

A partir de las observaciones anteriores ya se puede construir la regla

recursiva con la que se puede calcular el interés compuesto mes vencido, y
si se quiere una regla general que se pueda utilizar con cualquier monto m,
con un interés i, y al cabo de n periodos se tiene la siguiente función
recursiva de tres (3) parámetros

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 40 –

Pago del interés compuesto mes vencido V

Solución (continuación)

pago(m, i, n) = valor
donde se tienen las variables

m := Cantidad de dinero solicitado como prestamo

i := Interes
n := Número de meses por el cual se solicita el pretamo
valor := Valor total a pagar por el prestamo de la cantidad m
por n meses con un interés i utilizando el método de
interés compuesto mes vencido

entonces

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 41 –

Pago del interés compuesto mes vencido VI

Solución (continuación)
pago : R+ × R+ × N → R+
(
m, n = 0;
(m, i, n) 7→
pago(m, i, n − 1) ∗ (1 + i), en otro caso.

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 42 –

Pago del interés compuesto mes vencido VI

Solución (continuación)
La codificación en Python de esta función es

def pago(m, i, n):

if n == 0:
return m
else:
return pago(m, i, n-1) * (1+i)

print(pago(1E6, 0.05, 12))

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 43 –

Los conejos y los números de Fibonacci I

Ejemplo
Una pareja de conejos recién nacidos (uno de cada sexo) se liberan en una
isla. Los conejos no pueden tener descendencia hasta que cumplen dos
meses. Una vez que cumplen dos meses, cada pareja de conejos tiene
como descendencia otra pareja de conejos cada mesa . ¿Cuál es la cantidad
de parejas de conejos en la isla una vez transcurrido un año, suponiendo
que ningún conejo muere?.

a
Este problema fué propuesto originalmente por el italiano Leonardo Pisano
Bigollo (1170–1250), más conocido como Leonardo de Pisa o Fibonacci (que
significa hijo de Bonacci, filius Bonacci) en su libro Liber abaci publicado en
1202.

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 44 –

Los conejos y los números de Fibonacci II

Solución
Si fn denota la cantidad de parejas de conejos en el mes n, entonces, en el
mes cero, en éste aun no se ha hecho la liberación de la pareja de conejos,
por lo tanto la cantidad de parejas es f0 = 0.

n = 0, f0 = 0

Durante el primer mes, en este se hace la liberación de la primera pareja

de conejos, pero aún no han alcanzado la edad para reproducirse, por lo
tanto, no ha habido descendencia, por lo que f1 = 1.

n = 1, f1 = 1

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 45 –

Los conejos y los números de Fibonacci III

Solución (continuación)
Durante el segundo mes, ya habı́a una pareja de conejos del mes anterior y
éstos aún no han alcanzado la edad para reproducirse, por lo tanto, no
hubo descendencia, de donde f2 es igual a la cantidad de conejos que
habı́an en el mes anterior más la descendencia que produjeron las parejas
de más de dos meses, es decir, f2 = 1.

n = 2, f2 = f1 + f0 = 1 + 0 = 1

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 46 –

Los conejos y los números de Fibonacci IV

Solución (continuación)
Durante el tercer mes, ya habı́a una pareja de conejos del mes anterior y
durante el transcurso de este mismo mes los conejos alcanzaron la
madures para reproducirse, por lo tanto hubo descendencia, de donde f3 es
igual a la cantidad de conejos del mes anterior más la descendencia que se
produjo en este mes, es decir, f3 = 2.

n = 3, f3 = f2 + f1 = 1 + 1 = 2 +

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 47 –

Los conejos y los números de Fibonacci V

Solución (continuación)
Durante el cuarto mes ya habı́an dos parejas de conejos del mes anterior, y
la pareja madura es la que habı́a en el segundo mes, por lo tanto, la
descendencia fue generada sólo por esa pareja, de donde f4 es igual a la
cantidad de parejas del mes anterior más la descendencia que generé la
pareja del segundo mes, es decir, f4 = f3 + f2 = 2 + 1 = 3.

n = 4, f4 = f3 + f2 = 2 + 1 = 3 +

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 48 –

Los conejos y los números de Fibonacci VI

Solución (continuación)
Durante el quinto mes ya habı́an tres parejas de conejos del mes anterior, y
de éstas hay dos parejas maduras, que son las que habı́an en el tercer mes,
por lo tanto, la descendencia fue generada por esas dos parejas, de donde
f5 es igual a la cantidad de parejas del mes anterior más la descendencia
que generen las parejas del tercer mes, es decir, f5 = f4 + f3 = 3 + 2 = 5.

n = 5, f5 = f4 + f3 = 3 + 2 = 5 +

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 49 –

Los conejos y los números de Fibonacci VII

Solución (continuación)
Haciendo análisis similares se obtienen los siguientes resultados:

Para n = 6, se tiene que f6 = f5 + f4 = 5 + 3 = 8

Para n = 7, se tiene que f7 = f6 + f5 = 8 + 5 = 13
Para n = 8, se tiene que f8 = f7 + f6 = 13 + 8 = 21
Para n = 9, se tiene que f9 = f8 + f7 = 21 + 13 = 34
Para n = 10, se tiene que f10 = f9 + f8 = 34 + 21 = 55
Para n = 11, se tiene que f11 = f10 + f9 = 55 + 34 = 89
Para n = 12, se tiene que f12 = f11 + f10 = 89 + 55 = 144

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 50 –

Los conejos y los números de Fibonacci VIII

Solución (continuación)
De aquı́ que, transcurrido el primer año, en la isla habrán 144 parejas de
conejos.

A los números que son generados utilizando esta regla se les conoce como
números de Fibonacci.

A partir del análisis anterior, se puede diseñar una función recursiva que
permite calcular cualquier número de Fibonacci.

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 51 –

Los conejos y los números de Fibonacci IX

Solución (continuación)

fibo(n) = f
donde se tienen las variables

n := Número del cual se desea calcular su número de Fibonacci

f := Número de Fibonacci de n

entonces

fibo : N → N

0,
 si n = 0;
(n) 7→ 1, si n = 1;

fibo(n − 1) + fibo(n − 2), en otro caso.


J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Algunos problemas clásicos de programación recursiva Recursión – 52 –

Los conejos y los números de Fibonacci X

Solución (continuación)
Una codificación en Python de esta función es

def fibo(n):
if n == 0:
return 0
elif n == 1:
return 1
return fibo(n - 1) + fibo(n - 2)

print(fibo(12))

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Teorema fundamental de la programación recursiva Recursión – 53 –

Agenda

1 Introducción

2 Programación recursiva

3 Ejemplos de funciones recursivas

4 Algunos problemas clásicos de programación recursiva

5 Teorema fundamental de la programación recursiva

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Teorema fundamental de la programación recursiva Recursión – 54 –

Teorema fundamental de la programación recursiva

Teorema (Teorema fundamental de la programación recursiva)

Un lenguaje de programación es completo en Turing si tiene valores
enteros no negativos, funciones aritméticas elementales sobre dichos
valores, ası́ como un mecanismo para definir nuevas funciones utilizando
las funciones ya existentes (composición), la selección (if) y la recursión.

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Teorema fundamental de la programación recursiva Recursión – 55 –

Problemas III

Problemas
1 Modele mediante una función matemática y diseñe un programa

recursivo que calculePla suma
de los primeros n cuadrados de los

n 2 .
números naturales i=0 i
2 Modele mediante una función matemática y diseñe un programa sin
cadenas, tuplas o listas que retorne el último dı́gito de un número
natural n (leı́do de izquierda a derecha). Por ejemplo,
ultimo(13579) = 9.
3 Modele mediante una función matemática y diseñe un programa
recursivo sin cadenas, tuplas o listas que dado un número natural n
elimine el último dı́gito del número. Por ejemplo,
elimina ult(654321) = 65432.

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Teorema fundamental de la programación recursiva Recursión – 56 –

Problemas IV

Problemas
4 Modele mediante una función matemática y diseñe un programa

recursivo sin cadenas, tuplas o listas que determine la cantidad de

dı́gitos que componen un número natural n. Por ejemplo,
longitud(1230321) = 7.
5 Modele mediante una función matemática y diseñe un programa
recursivo sin cadenas, tuplas o listas que calcule la suma de los dı́gitos
que componen un número natural n. Por ejemplo,
suma digitos(123456) = 21.

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Teorema fundamental de la programación recursiva Recursión – 57 –

Problemas V

Problemas
6 Modele mediante una función matemática y diseñe un programa

recursivo sin cadenas, tuplas o listas que retorne el primer dı́gito de

un número natural n (leı́do de izquierda a derecha). Por ejemplo,
primero(86420) = 8.
7 Modele mediante una función matemática y diseñe un programa
recursivo sin cadenas, tuplas o listas que dado un número natural n
elimine el primer dı́gito del número. Por ejemplo,
elimina pri(654321) = 54321.
8 Modele mediante una función matemática y diseñe un programa
recursivo sin cadenas, tuplas o listas que dado un número natural n
inserte un dı́gito al comienzo del número. Por ejemplo,
inserta(7, 654321) = 7654321.

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN

 Teorema fundamental de la programación recursiva Recursión – 58 –

Problemas VI

Problemas
9 Modele mediante una función matemática y diseñe un programa

recursivo sin cadenas, tuplas o listas que invierta la cifras de un

número n dado. Por ejemplo, inversa(654321) = 123456.
10 Modele mediante una función matemática y diseñe un programa
recursivo sin cadenas, tuplas o listas que determine si un número es
capicua. Un número se dice palı́ndromo si al leerlo de izquierda a
derecha es lo mismo que leerlo de derecha a izquierda. Por ejemplo,
capicua(1) = V , capicua(1234321) = V , capicua(123421) = F .

J. Gómez, A. Rodrı́guez, C. Cubides & C. Sierra Programación de Computadores – UN