085 112 Capitulo 6 RECURRENCIA

CAPÍTULO 6
RECURSIVIDAD (RECURRENCIA)
“Para entender la recursividad primero hay que

entender la recursividad.”
Tratamos ahora de un concepto de gran utilidad para la programación:

la recursividad. La recursividad es un comportamiento presente en la
misma naturaleza de muchos problemas para los que buscamos
soluciones informáticas. En este capítulo queremos presentar el
concepto de recursividad o de recurrencia, y mostrar luego las etapas
habituales para diseñar algoritmos recursivos. Presentamos también el
concepto de inducción, que trae de la mano al de recurrencia y que
permite en muchos casos llegar a una correcta definición de un
algoritmo recurrente o recursivo.
Para la redacción de este capítulo se ha empleado la siguiente

bibliografía:
 “Diseño y verificación de algoritmos. Programas recursivos.”
Francisco Perales López
Fundamentos de informática. Codificación y Algoritmia.
Edita: Universitat de les Illes Balears. Palma 1998.

Col·lecció Materials Didáctics, n. 56.
Capítulo 3: “Diseño del algoritmos recursivos”.
El concepto de recursividad.
La palabra “recursividad” no aparece en el diccionario de la Real
Academia. Al menos en su 22º edición del año 2001. Tampoco aparece
en el Diccionario de María Moliner.
La palabra castellana que se emplea para tratar de lo que se va a hablar

en este capítulo es la de Recurrencia. El diccionario de la RAE define
así esta palabra: 1. f. Cualidad de recurrente. 2. f. Mat. Propiedad de
aquellas secuencias en las que cualquier término se puede calcular
conociendo los precedentes.
De todas formas se ha mantenido el término “recursividad” en el título

del capítulo porque esta palabra sí se emplea de forma habitual en el
lenguaje informático y aparece en cualquier referencia o manual que
verse sobre algoritmia. Aquí emplearemos ambas palabras de forma
indistinta.
La recursividad está presente en muchos sistemas del mundo real. Y por

eso, porque muchos problemas que queremos afrontar tiene una
esencia recursiva, la recursividad es una herramienta conveniente y muy
útil para diseñar modelos informáticos de la realidad que deseamos
modelizar.
Se dice que un sistema es recursivo cuando está parcial o

completamente definido en términos de sí mismo.
Quizá todos nos hemos planteado alguna vez una imagen recursiva: una
fotografía que muestra a una persona que sostiene entre sus manos esa
fotografía, que muestra a esa persona que sostiene entre sus manos esa
fotografía, que muestra a esa persona que sostiene entre sus manos esa
fotografía, que muestra…
86
Capítulo 6. Recursividad (Recurrencia)
Una imagen recursiva podemos definirla, por ejemplo, de la siguiente

manera. Se toma un cuadrado, se divide en nueve cuadrados y se
elimina el cuadro central. Con cada uno de los ocho cuadrados restantes
se realiza la misma operación: dividir en nueve cuadrados y eliminar el
central. Y con cada uno de ellos de nuevo lo mismo, y lo mismo con
cada uno de los cuadrados que quedan, y así hasta el infinito.
Por ejemplo, en la figura 6.1. se representa este dibujo de definición

recurrente. Este cuadro puede parecer inútil. No se trata ahora de
explicar sus muchas virtudes, sino de presentar el concepto de
recursividad. El cuadro representa el conocido conjunto de Cantor en el
plano. Basta ponerse en Google y buscar “conjunto de Cantor” para
lograr encontrar dibujos y aplicaciones prácticas de este conjunto. Se
pueden seguir buscando representaciones gráficas de curvas cuya
definición es recurrente: la curva de Peano, la de Hilbert, la de Hock,… o
de los fractales. Pero ese es otro asunto.
Figura 6.1.: Conjunto de Cantor
Pero además de poder mostrar con este concepto algunas curiosidades

aparentemente inútiles (sólo “aparentemente”), también podemos
presentar otros ejemplos de recurrencia. Hay muchos problemas
matemáticos que se resuelven mediante técnicas recursivas. Podemos
acudir a muchos de los problemas planteados en los capítulos
anteriores.
87
El algoritmo de Euclides es recurrente. El máximo común divisor de

dos números 𝑚 y 𝑛 (𝑚𝑐𝑑(𝑚, 𝑛)) se puede definir como el máximo común
divisor del segundo (de 𝑛 ) y del resto de dividir el primero con el
segundo: 𝑚𝑐𝑑 𝑚, 𝑛 = 𝑚𝑐𝑑(𝑛, 𝑚 𝑚𝑜𝑑 𝑛). La secuencia se debe parar cuando
se alcanza un valor de segundo entero igual a cero: de lo contrario en la
siguiente vuelta se realizaría una división por cero.
Él cálculo del factorial: podemos definir el factorial de un entero

positivo 𝑛 (𝑛!) como el producto de 𝑛 con el factorial de 𝑛 – 1: 𝑛! = 𝑛 ·
(𝑛 – 1). Y de nuevo esta definición deberá tener un límite: el momento
en el que se llega al valor cero: el factorial de cero es, por definición,
igual a uno.
La búsqueda de un término de la serie de Fibonacci: Podemos definir

la serie de Fibonacci como aquella cuyo término 𝑛 es igual a la suma de
los términos (𝑛 – 1) y (𝑛 – 2): 𝐹𝑖𝑏𝑛 = 𝐹𝑖𝑏𝑛 −1 + 𝐹𝑖𝑏𝑛 −2 . Y de nuevo se tiene
el límite cuando 𝑛 ≤ 2 donde el valor del término es la unidad.
Cálculo de una fila del triángulo de Tartaglia. Es conocida la

propiedad del triángulo de Tartaglia según la cual, si calculamos el valor
de cualquier elemento situado en el primer o último lugar de cada fila, el
valor de ese elemento es igual a uno; y el valor de cualquier otro
elemento del triángulo resulta igual a la suma de los elementos de su
fila anterior que están encima de la posición que deseamos calcular. Es
decir:
𝑡𝑖,0 = 1; 𝑡𝑖,𝑖 = 1; 𝑡𝑖,𝑗 (𝑗 ≠0,𝑗 ≠𝑖) = 𝑡𝑖−1,𝑗 −1 + 𝑡𝑖−1,𝑗 .

𝑖
donde 𝑡𝑖,𝑗 = , donde siempre se verifica que 0 ≤ 𝑗 ≤ 𝑖.
𝑗
Y así tenemos que para calcular una fila del triángulo de Tartaglia no es
necesario acudir al cálculo de binomios ni de factoriales, y basta con
conocer la fila anterior, que se calcula si se conoce la fila anterior, que
se calcula si se conoce la fila anterior… hasta llegar a las dos primeras
filas, que están formadas todo por valores uno. Tenemos, por tanto, y
de nuevo, un camino recurrente hecho a base de simples sumas para
88
encontrar la solución que antes habíamos buscado mediante el cálculo

de tres factoriales, dos productos y un cociente para cada elemento.
En todos los casos hemos visto un camino para definir un procedimiento

recurrente que llega a la solución deseada. En los temas anteriores no
hemos llegado a soluciones recurrentes, sino que únicamente hemos
hecho uso de estructuras de control iterativas. Ahora, en todas estas
soluciones, podemos destacar dos características básicas de todo
procedimiento recurrente o recursivo:
1. Lo indicaba el diccionario de la RAE: Propiedad de aquellas

secuencias en las que cualquier término se puede calcular
conociendo los precedentes. La recurrencia se puede usar en
aquellos sistemas donde sepamos llegar a un valor a partir de
algunos valores precedentes. Es la propiedad que implica
recurrencia.
2. Es imprescindible que, además, haya unos valores iniciales

preestablecidos hacia los que se converge: unos valores que no se
definen por recurrencia. En el algoritmo de Euclides se para el
proceso en cuanto se llega a dos valores tales que su módulo es
cero. En el algoritmo del cálculo del factorial siempre se llega a un
valor mínimo establecido en el cero: 0! = 1 . En el algoritmo de
Fibonacci tenemos que los dos primeros elementos de la sucesión
son unos. Y para el triángulo de Tartaglia tenemos que todos los
extremos de todas las filas son también iguales a uno.
La recursividad es una herramienta de diseño de algoritmos aceptada en

la mayoría de los lenguajes de programación. Esos lenguajes permiten
la creación de un procedimiento o función que hace referencia a sí
mismo dentro de la propia definición. Eso supone que al invocar a una
función recursiva, ésta genera a su vez una o varias nuevas llamadas a
ella misma, cada una de las cuales genera a su vez una o varias
llamadas a la misma función, y así sucesivamente. Si la definición está
bien hecha, y los parámetros de entrada son adecuados, la cadena de
89
invocaciones termina felizmente en alguna o varias llamadas que no

generan nuevas invocaciones. Esas llamadas finales terminan su
ejecución y devuelven el control a la llamada anterior, que finaliza su
ejecución y devuelve el control a la llamada anterior, y así retornando el
camino de llamadas emprendido, se llega a la llamada inicial y se
termina el proceso.
Cuando un procedimiento recursivo se invoca por primera vez decimos

que su profundidad de recursión es 1 y el procedimiento se ejecuta a
nivel 1. Si la profundidad de recursión de un procedimiento es 𝑁 y de
nuevo se llama a sí mismo, entonces desciende un nivel de recursión y
pasa al nivel 𝑁 + 1. Cuando el procedimiento regresa a la instrucción de
donde fue llamado asciendo un nivel de recursión.
Si una función o procedimiento 𝑃 contiene una referencia explícita a sí

mismo, entonces decimos que tenemos un procedimiento recursivo
directo. Si 𝑃 contiene una referencia a otro procedimiento 𝑄 el cual
tiene (directa o indirectamente) una referencia a 𝑃, entonces decimos
que 𝑃 es un procedimiento recursivo indirecto.
Veamos el ejemplo de una función recursiva que calcula el factorial de

un entero que recibe como parámetro de entrada:
Función 𝑓𝑎𝑐𝑡𝑜𝑟𝑖𝑎𝑙 (𝑁 Entero)  Entero.
1. Si 𝑁 = 0 Entonces 𝑓𝑎𝑐𝑡𝑜𝑟𝑖𝑎𝑙 ← 1
Sino (es decir, 𝑁 ≠ 0) Entonces 𝑓𝑎𝑐𝑡𝑜𝑟𝑖𝑎𝑙 𝑁 ← 𝑁 · 𝑓𝑎𝑐𝑡𝑜𝑟𝑖𝑎𝑙 𝑁 − 1
2. Fin.
Supongamos que invocamos al procedimiento con el valor 𝑁 = 5 . La

lista de llamadas que se produce queda recogida en la Tabla 6.1. Hay un
total de seis llamadas al procedimiento definido para el cálculo del
factorial, hasta que se le invoca con el parámetro 𝑁 = 0, que es el único
que en lugar de devolver un valor calculado con una nueva llamada, lo
que hace es devolver directamente el valor 1.
90
Nivel de
Recursión 𝑁 devuelve recibe resultado
1 5 5 * Factorial(4) 24 120
2 4 4 * Factorial(3) 6 24
3 3 3 * Factorial(2) 2 6
4 2 2 * Factorial(1) 1 2
5 1 1 * Factorial(0) 1 1
6 0 1 - 1
Tabla 6.1.: Llamadas al procedimiento definido para el

cálculo del Factorial para el caso de N  5 .
La demostración por inducción o recurrencia.

Vamos a ver a continuación del principio de demostración por
recurrencia o inducción sobre los números naturales. Es conveniente
tratar de ello fuera del contexto informático, porque esta forma de
demostración muestra un modo de razonamiento esencial para el
correcto dominio de la programación recursiva.
La demostración por recurrencia se emplea para establecer que una

determinada propiedad 𝑃 es cierta para todo número natural. Existen
distintas formas de plantear la demostración por inducción. Aquí
recogemos la de uso más habitual.
Se demuestra que 𝑃 es cierto para todo natural a partir de los siguientes

dos pasos de razonamiento:
a) Base de la inducción o recurrencia: Demostrar que 𝑃 es cierto para

el entero 0.
b) Recurrencia: se demuestra que la propiedad es hereditaria. Para

ello se establece una hipótesis de inducción: se supone que 𝑃 es
cierto para el natural 𝑛, y con base a eso se debe demostrar que
entonces es cierto para 𝑛 + 1.
Ejemplos de esta forma de demostración hay muchos. Presentamos aquí

uno: supongamos que queremos demostrar que
91
2𝑗 = 2𝑛+1 − 1
𝑗 =0
Podemos demostrarlo con los dos pasos antes indicados:
0 𝑗
a) Es cierto para 𝑛 = 0: 𝑗 =0 2 = 20 = 1 = 21 − 1.
𝑘 𝑗
b) Supongamos que es cierto para un determinado valor 𝑘 : 𝑗 =0 2 =
𝑘+1
2 − 1.
c) Entonces, demostrar que se cumple para 𝑘 + 1:

𝑘+1 𝑘
𝑗
2 = 2𝑗 + 2𝑘+1 = 2𝑘+1 − 1 + 2𝑘+1 = 2 · 2𝑘+1 − 1 = 2𝑘+2 − 1
𝑗 =0 𝑗 =0
cqd.
Definición recurrente de un conjunto.

Así como se pueden demostrar numerosas propiedades de los enteros
mediante la inducción o recurrencia, también se pueden definir
conjuntos.
La noción de conjunto juega un papel importante en la programación y

es, por tanto, esencial saber definir conjuntos. La inducción o
recurrencia aporta un método para definir muy interesante, pues
permite establecer reglas de construcción de los conjuntos: permite por
tanto dar una definición de conjuntos infinitos de forma inequívoca, no
por extensión, ni por descripción de sus propiedades, sino explicitando
un modo de construir ese conjunto.
La definición recurrente de un conjunto muestra el modo de construir

cualquier elemento del mismo a partir de ciertos elementos (ya
construidos y llamados elementos base), y de ciertas reglas específicas
de construcción.
La definición recurrente de conjuntos contiene dos partes:
92
a) Base: se describen (por comprensión o por extensión) los elementos

del conjunto que servirán para crear los otros con la ayuda de las
reglas de recurrencia señaladas.
b) Recurrencia: se ofrece una formulación recurrente de las reglas

que permiten crear un elemento a partir de elementos ya creados.
Por ejemplo, para definir el conjunto de los naturales, basta decir:
a) Base: 1 es un número natural.
b) Recurrencia: El siguiente de un número natural es un natural. Es

decir, si 𝑛 es natural, entonces 𝑛 + 1 es natural.
Otro ejemplo: si queremos definir el conjunto de los enteros impares,

bastará la siguiente definición:
a) Base: el entero 1 es impar.
b) Recurrencia: Sea 𝑥 impar. Entonces 𝑥 + 2 también es impar.
Demostración recurrente de propiedades sobre

conjuntos definidos recurrentemente.
Por último, una vez tenemos visto como definir un conjunto mediante
recurrencia, y una vez tenemos visto el método de demostración
recurrente, es fácil ofrecer ahora cómo establecer y demostrar distintas
propiedades sobre esos conjuntos de definición recurrente:
a) Base: demostrar que la propiedad 𝑃 es cierta para todos los

elementos de la base de definición del conjunto.
b) Recurrencia: La hipótesis de recurrencia consiste en suponer que

los elementos que sirven para la creación de un elemento 𝑒 del
conjunto verifican la propiedad 𝑃 . La demostración de herencia
consiste en demostrar que 𝑒 también verifica 𝑃 , a partir de la
hipótesis de inducción y de las propiedades de los elementos.
93
Por ejemplo, supongamos que queremos demostrar que el 𝑖 –ésimo

impar mayor que cero (lo llamaremos 𝑥𝑖 ) tiene el valor 2 · 𝑖 – 1.
Para demostrarlo, primero verificamos que efectivamente se cumple así

en los elementos de la base: el número 1. Efectivamente 𝑥1 = 1 y
también 2 · 1 − 1 = 1.
Y acudimos ahora a la recurrencia: Suponiendo que 𝑥𝑖 = 2 · 𝑖 − 1 , ¿es

cierto que 𝑥𝑖+1 = 2 · (𝑖 + 1) − 1? Teniendo en cuenta que 𝑥𝑖+1 = 𝑥𝑖 + 2 (así
hemos descrito, por construcción de recurrencia, el conjunto de los
impares), es inmediata la demostración, sin más que sustituir el valor de
𝑥𝑖 : 𝑥𝑖+1 = 𝑥𝑖 + 2 = 2 · 𝑖 − 1 + 2 = 2 · 𝑖 + 1 − 1 ; sin más que sacando factor
común al dos que multiplica a 𝑖 y a 1.
Todo lo visto en este apartado del capítulo nos permitirá tener unas
pautas para la construcción de algoritmos o programas recursivos o
recurrentes.
Etapas en la construcción de algoritmos recursivos.

Un algoritmo recursivo requiere, como primera providencia, una
definición más o menos matemática del problema que se está
abordando. Y además esta especificación matemática del problema debe
ofrecer las ecuaciones de recurrencia. Para llegar a esa descripción nos
basamos en la definición recurrente del dominio.
Una vez tenemos las relaciones de recurrencia, hay que transcribir esas
relaciones a notación algorítmica.
Veamos con un ejemplo cómo podemos estudiar un problema de forma

recursiva y pasar por distintas etapas hasta llegar a la construcción de la
correspondiente función recursiva. El ejemplo es el de la calle
adoquinada y la rayuela:
Se considera una calle adoquinada. Cada adoquín está numerado a

partir de 0:
94
0 1 2 … n-1 n n+1 …
Figura 6.2.: Adoquines de la rayuela.
En esa calle hay niños jugando a la rayuela: se desplazan de un adoquín

al siguiente, pero también pueden saltar un adoquín. El juego está,
pues, basado en estos dos desplazamientos elementales (ver figura
6.3.)
Al principio del juego, los niños se encuentran en el adoquín 0. El

problema consiste en calcular el número de caminos posibles hasta
Figura 6.3.: Movimientos de la rayuela.
alcanzar un adoquín n prefijado como objetivo.
Para poder realizar una definición recurrente de nuestro problema,

debemos seguir los siguientes pasos:
a) En primer lugar debemos establecer cuál es el perfil matemático

de la función que estamos buscando. A esta función la llamaremos
“Caminos”, cuyo parámetro de entrada es un natural n, y la
salida en otro natural que indica el número de caminos posibles.
b) En segundo lugar, necesitamos saber cuál será el enunciado de la

función (enunciado en comprensión): “𝐶𝑎𝑚𝑖𝑛𝑜𝑠(𝑛) es el número de
caminos posibles que permiten llegar al adoquín 𝑛 a partir del
adoquín 0, pasando de un adoquín al siguiente, o saltando uno.”
c) El siguiente paso es determinar cuáles son los casos más simples

en los que podemos llamar a nuestra función Caminos:
Al adoquín 1 se llega de una sola manera: 𝐶𝑎𝑚𝑖𝑛𝑜𝑠(1) = 1.
95
Al adoquín 2 se llega de dos maneras: 𝐶𝑎𝑚𝑖𝑛𝑜𝑠(2) = 2.
El caso del adoquín 3 ya supone un estudio más complicado.
d) Una vez visto como se describe la función y cuáles son los casos más
elementales, queda descubrir cómo describir el caso general. Para
ello debemos basarnos en los desplazamientos elementales.
Estudiamos tres adoquines consecutivos: para alcanzar el adoquín 𝑛
se puede provenir del adoquín 𝑛 – 1, o bien del adoquín 𝑛 – 2.
Se divide el conjunto de caminos que llevan al adoquín 𝑛 en dos

subconjuntos disjuntos:
 Los caminos que pasan por el adoquín 𝑛 – 1.
 Los caminos que NO pasan por el adoquín 𝑛 – 1.
n2 n 1 n
Figura 6.4.: Movimientos de la rayuela

para alcanzar el adoquín n .
Todo camino a 𝑛 que pasa por 𝑛 – 1 está creado a partir de un

camino que llega a 𝑛 – 1 al que se la añade el trayecto (𝑛 – 1, 𝑛). Todo
camino que no pasa por 𝑛 – 1 está creado a partir de uno que llega
hasta el adoquín 𝑛 – 2 al que se le añade el trayecto (𝑛 – 2, 𝑛).
Podemos, por tanto, afirmar que los caminos que llegan desde 0
hasta 𝑛 son: 𝐶𝑎𝑚𝑖𝑛𝑜𝑠 𝑛 = 𝐶𝑎𝑚𝑖𝑛𝑜𝑠 𝑛 − 1 + 𝐶𝑎𝑚𝑖𝑛𝑜𝑠(𝑛 − 2).
e) Ya tenemos un enunciado recursivo:
𝐶𝑎𝑚𝑖𝑛𝑜𝑠 1 = 1.
𝐶𝑎𝑚𝑖𝑛𝑜𝑠(2) = 2.
𝐶𝑎𝑚𝑖𝑛𝑜𝑠 𝑛 = 𝐶𝑎𝑚𝑖𝑛𝑜𝑠 𝑛 − 1 + 𝐶𝑎𝑚𝑖𝑛𝑜𝑠(𝑛 − 2), ∀𝑛 ≥ 3.
96
Es evidente, por exigencias del mismo enunciado del problema, que

el valor de 𝑛 debe ser siempre mayor que cero y que no se debe
invocar a la función Caminos con parámetros negativos. Y así lo
respeta nuestra definición recursiva, que toma una valor base no
calculado para 𝑛 = 1 y 𝑛 = 2 , y solamente acude a la definición
recursiva a partir de 𝑛 = 3, donde se invoca a la función 𝐶𝑎𝑚𝑖𝑛𝑜𝑠()
para los valores 𝑛 − 1 = 2 y 𝑛 − 2 = 1, ambos mayores que cero.
Además podemos comprobar que la recurrencia termina: todo

valor del dominio inicial provoca un cálculo finito. Vamos a
demostrarlo por inducción:
Base: 𝐶𝑎𝑚𝑖𝑛𝑜𝑠(1) y 𝐶𝑎𝑚𝑖𝑛𝑜𝑠(2) terminan ya que no generan ninguna

nueva llamada recursiva.
Recurrencia: Supongamos que 𝐶𝑎𝑚𝑖𝑛𝑜𝑠(𝑛) (para valores de 𝑛 ≥ 3)

termina (hipótesis de recurrencia). Eso implica que 𝐶𝑎𝑚𝑖𝑛𝑜𝑠(𝑛 – 1) y
𝐶𝑎𝑚𝑖𝑛𝑜𝑠(𝑛 – 2) también terminan. Entonces, la llamada 𝐶𝑎𝑚𝑖𝑛𝑜𝑠(𝑛 +
1) genera el cálculo de 𝐶𝑎𝑚𝑖𝑛𝑜𝑠(𝑛) y de 𝐶𝑎𝑚𝑖𝑛𝑜𝑠(𝑛 – 1), que ambos
terminan, por la hipótesis de recurrencia.
Conclusión: 𝐶𝑎𝑚𝑖𝑛𝑜𝑠(𝑛) termina para 𝑛 ≥ 3.
Con todo lo hecho, hemos llegado a una correcta definición de la

función o método diseñado parar calcular de forma recurrente el
número de caminos posibles para llegar del adoquín cero al adoquín
𝑛.
Así, la definición de la función 𝐶𝑎𝑚𝑖𝑛𝑜𝑠() podría tener el siguiente

aspecto:
Función 𝐶𝑎𝑚𝑖𝑛𝑜𝑠 (𝑛 Entero)  Entero
Constantes
∅
Variables
∅
Acciones:
1. Si 𝑛 < 3 Entonces 𝐶𝑎𝑚𝑖𝑛𝑜𝑠(𝑛) ← 𝑛.
Sino 𝐶𝑎𝑚𝑖𝑛𝑜𝑠 𝑛 ← 𝐶𝑎𝑚𝑖𝑛𝑜𝑠 𝑛 − 1 + 𝐶𝑎𝑚𝑖𝑛𝑜𝑠(𝑛 − 2).
2. FIN.
97
Recapitulamos: las etapas seguidas para la elaboración de la función

sustentada por un algoritmo recursivo pueden quedar resumidas en las
siguientes:
a) Especificación matemática. Estudio del perfil de la función.
b) Enunciado en comprensión de la función. Un enunciado intuitivo

que permita seguir el razonamiento.
c) Examen de los casos particulares simples. Entendemos por casos

simples aquellos para los cuales el cálculo se formula de manera
analítica. Son los casos que constituirán la base de la recurrencia.
d) Puesta de relieve de un caso general por descubrimiento de una

fórmula que lo relaciona con el mismo problema basado en
una información más pequeña, más próxima al caso de las
bases. Este paso es el encargado de buscar la recurrencia: hay que
expresar el valor de la función en un punto del dominio a partir de
uno o varios puntos del dominio.
e) Demostración de la recurrencia. Ese paso último requiere a su

vez de tres subpasos:
e.1. Comprobación de que el valor de la función puede ser calculado

correctamente en cualquier punto o valor del dominio únicamente
mediante la aplicación de las relaciones facilitadas.
e.2. Comprobación de la coherencia de las llamadas de la función

recursiva.
e.3. Comprobación de la terminación de la función.
Árbol de recursión.
Un árbol de recursión sirve para representar las sucesivas llamadas
recursivas que un programa recursivo puede generar. Es un concepto
98
simple, pero de gran utilidad práctica para analizar el comportamiento

de los algoritmos recursivos diseñados.
Para construir un árbol, se representa cada llamada a la función como

un nodo (que dibujaremos en forma de un círculo). Arriba se dibuja el
nodo inicial con el que es invocada por primera vez la función
recurrente. Más allá (hacia abajo) se van insertando las llamadas que
recibe la función recursivamente. En cada nodo del árbol (que se
corresponde con una llamada) se le adjunta una etiqueta con el valor o
valores de los parámetros de entrada.
Por ejemplo, el árbol de recursión de la función Factorial tiene el aspecto

como el recogido en la figura 6.5.
𝑁−1
𝑁−2
Figura 6.5.: Árbol de recursión de la

0
función Factorial.
Para la rayuela, el árbol queda recogido en la Figura 6.6. Hemos tomado

el caso en que 𝑁 = 5.
99
4 3
3 2 2 1
Figura 6.6.: Árbol de recursión de la

2 1 Rayuela para 𝑁 = 5.
Recursión e iteración.
El concepto de iteración ya quedó visto en el capítulo 4, al hablar de los
algoritmos y de sus modos de representación. Y al inicio de éste capítulo
hemos visto que todos los algoritmos que en el capítulo 4 resolvimos
mediante la iteración, también pueden ser solventados mediante la
recursividad o recurrencia.
La cuestión a plantear es entonces: ¿qué es mejor: recursividad, o

estructuras iterativas? Para responder a esta cuestión, un factor
importante que cabe plantearse es cuál de las dos formas requiere
menor espacio de almacenamiento en memoria. Y otro, cuál de las dos
formas resuelve el problema con menor tiempo.
Veamos el algoritmo del cálculo del factorial, expresado como función

recurrente (Función FactorialR()) y expresado como función con
estructura iterativa (Función FactorialI())
Función 𝐹𝑎𝑐𝑡𝑜𝑟𝑖𝑎𝑙𝑅 (𝑁 Entero)  Entero
Constantes
∅
Variables
∅
100
Acciones:
1. Si 𝑁 = 0 Entonces 𝐹𝑎𝑐𝑡𝑜𝑟𝑖𝑎𝑙𝑅 0 ← 1.
2. Sino, Entonces 𝐹𝑎𝑐𝑡𝑜𝑟𝑖𝑎𝑙𝑅 𝑁 ← 𝑁 · 𝐹𝑎𝑐𝑡𝑜𝑟𝑖𝑎𝑙𝑅(𝑁 − 1).
3. FIN.
Función 𝐹𝑎𝑐𝑜𝑟𝑖𝑎𝑙𝐼 (𝑁 Entero)  Entero.

Constantes
∅
Variables
𝐴𝑢𝑥, 𝐼, Enteros
Acciones:
1. Si 𝑁 = 0, Entonces 𝐹𝑎𝑐𝑡𝑜𝑟𝑖𝑎𝑙𝐼 0 = 1.
Sino, Entonces:
1.1. 𝑎𝑢𝑥 ← 1.
1.2. Para 𝐼 ← 1 Hasta 𝑁 Repetir: 𝑎𝑢𝑥 ← 𝑎𝑢𝑥 × 𝐼.
1.3. 𝐹𝑎𝑐𝑡𝑜𝑟𝑖𝑎𝑙𝐼 ← 𝑎𝑢𝑥.
2. Fin.
Aparentemente, parece que la función recursiva exige menos memoria,

pues de hecho no requiere el uso de ninguna variable local (es decir,
variable propia de la función) mientras que la función iterativa requiere
de dos variables.
Pero en realidad el programa recursivo va almacenando en una pila de

memoria los 𝑁 números: 𝑁, 𝑁 – 1 , 𝑁 – 2 , … 2, 1, que son los parámetros
de llamada antes de cada recursión. A medida que vaya saliendo de las
sucesivas llamadas, multiplicará esos números en el mismo orden en
que lo hace el programa iterativo. Así pues, el programa recurrente
requiere de mayor almacenamiento. Además, también tardará más
tiempo en ejecutarse, porque debe almacenar en memoria y recuperar
luego de ella todos los números, realizar todas las multiplicaciones, y
realizar las distintas llamadas a la función.
Otro ejemplo para estudiar el comportamiento de una función definida

de forma recursiva o de forma iterativa lo tenemos con los números de
Fibonacci. Mostramos de nuevo la definición recursiva (Función
FibonacciR()) y la definición iterativa (Función FibonacciI()).
Función 𝐹𝑖𝑏𝑜𝑛𝑎𝑐𝑐𝑖𝑅 (𝑁 Entero)  Entero
Constantes
∅
Variables
101
∅
Acciones:
1. Si 𝑁 ≤ 2 Entonces 𝐹𝑖𝑏𝑜𝑛𝑎𝑐𝑐𝑖𝑅(𝑁) ← 1.
Si no, Entonces,
𝐹𝑖𝑏𝑜𝑛𝑎𝑐𝑐𝑖𝑅 𝑁 ← 𝐹𝑖𝑏𝑜𝑛𝑎𝑐𝑐𝑖𝑅 𝑁 − 1 + 𝐹𝑖𝑏𝑜𝑛𝑎𝑐𝑐𝑖𝑅(𝑁 − 2).
2. Fin.
Función 𝐹𝑖𝑏𝑜𝑛𝑎𝑐𝑐𝑖𝐼 (𝑁 Entero)  Entero

Constantes
∅
Variables
𝐴, 𝐵, 𝐶 e 𝐼, Enteros.
Acciones:
1. Si 𝑁 ≤ 2 Entonces 𝐹𝑖𝑏𝑜𝑛𝑎𝑐𝑐𝑖𝑅(𝑁) ← 1.
2. Si no, Entonces,
2.1. 𝐴 ← 1.
2.2. 𝐵 ← 1
2.3. Para 𝐼 ← 3 Hasta 𝑁, Hacer:
2.3.1. 𝐶 ← 𝐴+𝐵
2.3.2. 𝐴←𝐵
2.3.3. 𝐵←𝐶
2.4. 𝐹𝑖𝑏𝑜𝑛𝑎𝑐𝑐𝑖𝐼 ← 𝐶
3. FIN.
El árbol de recursividad para la función 𝐹𝑖𝑏𝑜𝑛𝑎𝑐𝑐𝑖𝑅(), para 𝑁 = 5 queda

de forma idéntica al árbol antes presentado en la Figura 6.6. para el
problema de la Rayuela. Y así observamos que para el cálculo del valor
de 𝐹𝑖𝑏𝑜𝑛𝑎𝑐𝑐𝑖𝑅(5) hemos calculado una vez el valor de 𝐹𝑖𝑏𝑜𝑛𝑎𝑐𝑐𝑖𝑅(4), dos
veces el valor de 𝐹𝑖𝑏𝑜𝑛𝑎𝑐𝑐𝑖𝑅(3), tres veces el de 𝐹𝑖𝑏𝑜𝑛𝑎𝑐𝑐𝑖𝑅(2) y dos veces
el de 𝐹𝑖𝑏𝑜𝑛𝑎𝑐𝑐𝑖𝑅(1). Así pues, con el árbol de recursión vemos que el
programa recursivo repite innecesariamente los mismos cálculos una y
otra vez. Y el tiempo que tarda la función recursiva en calcular
𝐹𝑖𝑏𝑜𝑛𝑎𝑐𝑐𝑖𝑅(𝑁) aumenta de forma exponencial a medida que aumenta 𝑁.
En cambio, la función iterativa usa un tiempo de orden lineal (aumenta

linealmente con el incremento del valor de 𝑁 ), de forma que la
diferencia de tiempos entre una y otra forma de implementación es
notable.
La recursión siempre puede reemplazarse con la iteración y las pilas de

almacenamiento de datos. La pregunta es, entonces: ¿Cuándo usamos
recursión, y cuándo usamos iteración?
102
Si el árbol de recursión tiene muchas ramas, con poca duplicación de

tareas, entonces el método más adecuado es la recursión, siempre que
además el programa resultante sea más claro, sencillo y fácil de
obtener.
Los algoritmos recursivos son muy apropiados cuando el problema a

resolver, la función a calcular o la estructura de datos a procesar están
definidos en términos recursivos. La recursión debe tenerse en cuenta
como una técnica que nos permite diseñar algoritmos de una forma
sencilla, clara y elegante. No se debe utilizar por tanto cuando dificulte
la comprensión el algoritmo.
Ejercicio: las torres de Hanoi.

Dice la leyenda que, al crear el mundo, Dios situó sobre la Tierra tres
varillas de diamante y sesenta y cuatro discos de oro. Los discos eran
todos de diferente tamaño, e inicialmente fueron colocados en orden
decreciente de diámetros sobre la primera de las varillas. También creó
Dios un monasterio cuyos monjes tenían la tarea de trasladar todos los
discos desde la primera varilla a la tercera. La única operación permitida
a los monjes para llevar a cabo su tarea era mover un único disco cada
vez, de una varilla a otra cualquiera, con la condición de que no se podía
situar encima de un disco otro de diámetro mayor. La leyenda decía
también que cuando los monjes terminasen su tarea, el mundo llegaría
a su fin.
La leyenda no es cierta: es fruto de la imaginación de un matemático del

siglo XVIII, que inventó el juego de las Torres de Hanoi (así se llama) y
que diseñó así su propia campaña de publicidad y marketing que le
permitiera lanzar su invento al mercado. La invención resultó, sin
embargo, efectiva: ha perdurado hasta nuestros días, el juego es
conocido en todo el mundo,… y nos ha dejado una pregunta: si la
leyenda fuera cierta… ¿cuándo sería el fin del mundo?
103
El mínimo número de movimientos que se necesitan para resolver este

problema es de 264 − 1 . Si los monjes hicieran un movimiento por
segundo, y no parasen en ningún instante hasta completar la total
ejecución de la tarea de traslado, los discos estarían en la tercera varilla
en poco menos de 585 mil millones de años. Teniendo en cuenta que la
tierra tiene sólo unos cinco mil millones, o que el universo está entre
quince y veinte mil millones de años, está claro que o los monjes se dan
un poco más de prisa, o tenemos universo y mundo para rato.
Se puede generalizar el problema de Hanoi variando el número de

discos: desde un mínimo de 3 hasta el máximo que se quiera.
El problema de Hanoi es curioso, y su formulación elegante. Y su

solución es muy rápida de calcular. La pega no está en la complicación
del procedimiento (que no es complicado), sino en que a medida que
aumenta el número de discos crece exponencialmente el número de
pasos.
Existe una versión recursiva eficiente para hallar el problema de las

torres de Hanoi para pocos discos; pero el coste de tiempo y de
memoria se incrementa excesivamente al aumentar el número de
discos.
104
La solución recursiva es llamativamente sencilla de implementar y de

construir. Y de una notable belleza, creo yo.
Si numeramos los discos desde 1 hasta 𝑁 , y si llamamos 𝑋 al poste

donde quedan inicialmente colocado los discos, 𝑍 al poste de destino de
los discos, e 𝑌 el tercer poste intermedio, el algoritmo recurrente que
resuelve el problema de las torres de Hanoi quedaría de la siguiente
manera:
1. Si N = 1, Entonces Trasladar disco de X a Z.
Sino
1.1. Trasladar 1 .. N – 1 de X z Y, (auxiliar: Z).
1.2. Trasladar N de X a Z.
1.3. Trasladar 1 .. N de Y a Z (auxiliar: X)
2. Fin.
Podemos definir una función que muestre por pantalla los movimientos
necesarios para hacer el traslado de la torre de un poste a otro. A esa
función la llamaremos 𝐻𝑎𝑛𝑜𝑖, y recibe como parámetros los siguientes
valores:
a) una variable entera que indica el disco más pequeño de la pila que
se quiere trasladar.
b) una variable entera que indica el disco más grande de la pila que se
desea trasladar. (Hay que tener en cuenta que con el algoritmo que
hemos definido siempre se trasladan discos de tamaños
consecutivos.)
c) Una variable que indique el poste donde están los discos que
trasladamos.
d) Una variable que indica el poste a donde se dirigen los discos.
Un modo de identificar los postes y de tener en todo momento

identificado el poste auxiliar con variables enteras es el siguiente:
Llamaremos al poste origen poste 𝑖 , y al poste destino poste 𝑗 . Y
exigimos a las dos variables 𝑖, 𝑗 las siguientes restricciones: 𝑖, 𝑗 ∈ 1. .3 , e
𝑖 ≠ 𝑗.
105
Y entonces siempre tendremos que el poste auxiliar vendrá siempre

definido con la expresión 6 – 𝑖 – 𝑗, como puede verse en la Tabla 6.2.
𝑖 𝑗 6– 𝑖– 𝑗
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
Tabla 6.2.: Postes de las torres de Hanoi.
La función 𝐻𝑎𝑛𝑜𝑖 queda entonces de la siguiente forma:

Función 𝐻𝑎𝑛𝑜𝑖 (𝐷1, 𝐷2, 𝑖, 𝑗, Enteros)
Constantes
∅
Variables
∅
Acciones:
1. Si 𝐷1 = 𝐷2, Entonces [Mostrar] Mover disco D1 de 𝑖 a 𝑗.
2. Sino
2.1. 𝐻𝑎𝑛𝑜𝑖(𝐷1, 𝐷2 − 1 , 𝑖 , 6 − 𝑖 − 𝑗) .
2.2. 𝐻𝑎𝑛𝑜𝑖(𝐷2, 𝐷2, 𝑖, 𝑗).
2.3. 𝐻𝑎𝑛𝑜𝑖(𝐷1, 𝐷2 − 1 , 6 − 𝑖 − 𝑗 , 𝑗).
3. FIN.
La forma que adquiere esta función implementada en C es tan sencilla

como lo que se muestra a continuación:
typedef unsigned short int usi;
void Hanoi(usi D1, usi D2, usi i, usi j)
{
if(D1 == D2)
printf("Disco %hu de %hu a %hu\n",D1, i, j);
else
{
Hanoi(D1, D2 - 1, i, 6 - i - j);
Hanoi(D2, D2, i, j);
Hanoi(D1, D2 - 1, 6 - i - j, j);
}
}
Y si se invoca esta función inicialmente con la sentencia
Hanoi(1, discos, 1, 3);
106
donde discos es el número de discos que tiene la torre de Hanoi, la

ejecución de esta función muestra todos los movimientos que debe
hacerse con los anillos para pasarlos desde el poste 1 al poste 3.
Por ejemplo, si tomamos el valor discos = 4 tendremos la siguiente

salida:
Disco 1 de 1 a 2
Disco 2 de 1 a 3
Disco 1 de 2 a 3
Disco 3 de 1 a 2
Disco 1 de 3 a 1
Disco 2 de 3 a 2
Disco 1 de 1 a 2
Disco 4 de 1 a 3
Disco 1 de 2 a 3
Disco 2 de 2 a 1
Disco 1 de 3 a 1
Disco 3 de 2 a 3
Disco 1 de 1 a 2
Disco 2 de 1 a 3
Disco 1 de 2 a 3
En lenguaje Java, una aplicación que desarrolla completamente este

algoritmo podría tener la siguiente forma:
public class TorresHanoi {
public static void Hanoi(int D1, int D2, int i, int j)

{
if(D1 == D2)
{
System.out.print("Disco " + D1 + " de ");
System.out.println(i + " a "+ j);
}
else
{
Hanoi(D1 , D2 - 1 , i , 6 - i - j);
Hanoi(D2 , D2 , i , j);
Hanoi(D1 , D2 - 1 , 6 - i - j , j);
}
}
public static void main(String[] args) {

int discos;
System.out.println("número de discos ... ");
discos = Teclado.readInt();
107
Hanoi(1, discos, 1, 3);

}
}
Donde la clase Teclado está definida para dar entrada valores desde el
teclado.
Para terminar esta presentación de las torres de Hanoi queda pendiente

una cosa: demostrar que, efectivamente, el número de movimientos
para desplazar todos los discos de un poste a otro con las condiciones
impuestas en el juego es igual a dos elevado al número de discos,
menos uno.
Eso se demuestra fácilmente por inducción (como no):
Base: Se verifica para 𝑁 = 1 : 𝑀 1 = 2𝑁−1 − 1 = 1 : efectivamente, el

mínimo número de movimientos es uno.
Recurrencia: Supongamos que se cumple para 𝑁 : 𝑀 𝑁 = 2𝑁 − 1 .

Entonces si tenemos 𝑁 + 1 discos, lo que hacemos es desplazar dos
veces los 𝑁 primeros discos y entre medias una vez el disco 𝑁 + 1, es
decir, tenemos 𝑀 𝑁 + 1 = 2 · 𝑀 𝑁 + 1 = 2 · 2𝑁 − 1 + 1 = 2𝑁+1 − 1
(c.q.d.)
Recapitulación.
Hemos visto el modelo recursivo para plantear y solventar problemas.
Esta forma de trabajo es especialmente útil cuando pretendemos
solventar cuestiones basadas en propiedades definidas sobre el conjunto
de enteros o un conjunto numerable donde se pueda establecer una
correspondencia entre los enteros y los elementos de ese conjunto.
Hemos visto el modo en que se definen por recurrencia una serie de

conjuntos, cómo se demuestran propiedades para estos conjuntos
basándonos en la demostración por inducción, y cómo se llega así a
replantear muchos problemas, alcanzando una formulación muy
elegante y sencilla: la forma recursiva.
108
La recursividad ofrece habitualmente algoritmos muy sencillos de

implementar y de interpretar. La principal limitación que presenta esta
forma de resolver problemas es que habitualmente supone un elevado
coste de tiempo de computación y de capacidad de almacenamiento de
memoria.
Hemos descrito el camino a seguir para alcanzar una solución recurrente

ante un problema que nos planteamos. Los ejercicios que planteamos a
continuación pueden servir para seguir profundizando en ese itinerario
por el que se llega a las definiciones recurrentes.
Ejercicios.
 Definir la operación potencia de forma recursiva. Escribir el
pseudocódigo de una función que pudiera realizar ese cálculo.
 Definir la operación suma de enteros de forma recursiva.

Téngase en cuenta, por ejemplo, que si pretendemos sumar dos
enteros 𝒂 y 𝒃, podemos tomar: 𝒔𝒖𝒎𝒂(𝒂, 𝒃) = 𝒂 si 𝒃 es igual a cero;
y 𝒔𝒖𝒎𝒂(𝒂, 𝒃) es 𝟏 + 𝒔𝒖𝒎𝒂(𝒂, 𝒃 − 𝟏) en otro caso. Escribir el
pseudocódigo de una función que pudiera realizar esa operación.
Definir la operación producto de forma recursiva. Téngase en

cuenta, por ejemplo, que si pretendemos multiplicar dos enteros
a y b, podemos tomar: 𝒑𝒓𝒐𝒅𝒖𝒄𝒕𝒐(𝒂, 𝒃) = 𝟎 si 𝒃 es igual a cero; y
𝒑𝒓𝒐𝒅𝒖𝒄𝒕𝒐(𝒂, 𝒃) es 𝒂 + 𝒑𝒓𝒐𝒅𝒖𝒄𝒕𝒐(𝒂, 𝒃 − 𝟏) en otro caso. Escribir el
pseudocódigo de una función que pudiera realizar ese cálculo.
 Definir una función que devuelva el mayor de una lista de

números. El algoritmo no puede comparar en ningún momento
más de dos números para decidir el mayor de entre todos los de
la lista.
Vamos a definir una función, que llamaremos sencillamente 𝑀, y que

recibe como parámetros una lista de enteros y un valor entero que
109
indica la cantidad de elementos de esa lista. La función devuelve un

entero: el mayor de entre todos los valores de la lista.
La limitación impuesta en el enunciado nos indica la base de nuestro

algoritmo de recurrencia: Si la lista tiene un solo elemento, ese
elemento es el que devuelve la función; si la lista tiene dos elementos,
la función devuelve el mayor de ellos. Si la lista tiene más de dos
elementos, entonces la función no puede contestar a la cuestión, porque
en ningún momento podemos comparar más de dos elementos.
Supongamos que tenemos 𝑛 elementos en la lista. Entonces está claro

que el mayor de entre ellos es igual al mayor entre el mayor de los 𝑛 2
primeros y el mayor entre los 𝑛 2 segundos. Esta es la base para definir
nuestro proceso de recurrencia:
Podemos entonces plantear el algoritmo de la siguiente manera:

Función M (𝑥1 , … , 𝑥𝑛 Enteros, 𝑛 Entero)  Entero
Constantes
∅
Variables
𝑀, 𝑥 e 𝑦, Enteros.
Acciones:
1. Si n = 1 Entonces 𝑀 ← 𝑥1 .
Si no, Entonces
1.1. 𝑚 = 𝑛 2 .
1.2. 𝑥 ← 𝑀(𝑥1 , … , 𝑥𝑚 , 𝑚).
1.3. 𝑦 ← 𝑀(𝑥𝑚 +1 , … , 𝑥𝑛 , 𝑛 − 𝑚).
1.4. Si 𝑥 > 𝑦 Entonces 𝑀 ← 𝑥.
Si no [es decir, 𝑥 ≤ 𝑦] Entonces 𝑀 ← 𝑦.
2. Fin.
Que en código C (o en Java: tiene el mismo aspecto) queda una función

como la que sigue:
short M(short *v, short n)
{
short m;
short x, y;
if(n == 1) return *v;

m = n / 2;
x = M(v , m);
y = M(v + m , n - m);
110
return x > y ? x: y;
}
Y la llamada a esta función o al método es de la forma M(v, dim); donde

v es una variable de tipo vector o array de enteros y donde dim es el
número de elementos del vector v. En Java no sería necesario el paso de
este segundo parámetro, que es igual a v.length. (Como ya se ha dicho
en capítulos anteriores, el código aquí recogido no es parte sustancial
del contenido de este manual: no es menester en estos momentos
comprender todo lo referente al código en Java o en C: se presenta aquí
para mostrar la forma que tiene un programa que implementa nuestros
algoritmos.)
 Definir una función que muestre, mediante un proceso

recurrente, el código binario de un entero dado. Convendrá
recordar lo explicado en capítulos anteriores sobre codificación
binaria.
Para encontrar este proceso es sencillo buscar los casos más sencillos,
que forman la Base de la recurrencia: El código binario de 0 10 es 0; el
código binario de 1 10 es 1.
Para el proceso de recurrencia baste con decir que si el número es

mayor que 1, entonces ya necesita de al menos dos dígitos binarios; y si
el número es mayor que 3 entonces requiere ya de al menos tres
dígitos. Y, en general, si el número es mayor que 2𝑛 − 1 entonces el
número requiere, para su codificación binaria, de al menos 𝑛 dígitos.
Y, por lo indicado en los capítulos sobre codificación numérica y sobre

codificación interna de la información, sabemos que podemos
concatenar dígitos a fuerza de dividir por dos sucesivas veces hasta
llegar al valor 0 ó 1.
Podemos entonces definir el siguiente algoritmo recursivo para obtener

el código binario de un entero:
Función 𝐵𝑖𝑛𝑎𝑟𝑖𝑜 (𝑛 > 0 Entero en base 10)  Muestra Código binario
Constantes
∅
111
Variables
∅
Acciones:
1. Si 𝑛 = 1 Entonces [Mostrar dígito] Mostrar 𝑛.
Si no [Es decir, 𝑛 > 1] Entonces
1.1. 𝐵𝑖𝑛𝑎𝑟𝑖𝑜(𝑛 2).
1.2. [Mostrar digito] Mostrar 𝑛 𝑚𝑜𝑑 2.
2. Fin.
Cuyo código en C tiene el siguiente aspecto:

void Binario(unsigned long n)
{
if(n == 1)
printf("%ld",n); // Java: System.out.print(n);
else
{
Binario(n/2);
printf("%ld",n % 2); // Java: System.out.print(n%2);
}
}
112

085 112 Capitulo 6 RECURRENCIA

Cargado por

Copyright:

Formatos disponibles

085 112 Capitulo 6 RECURRENCIA

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

085 112 Capitulo 6 RECURRENCIA

Cargado por

Copyright:

Formatos disponibles

CAPÍTULO 6

“Para entender la recursividad primero hay que

Tratamos ahora de un concepto de gran utilidad para la programación:

Para la redacción de este capítulo se ha empleado la siguiente

Edita: Universitat de les Illes Balears. Palma 1998.

La palabra castellana que se emplea para tratar de lo que se va a hablar

De todas formas se ha mantenido el término “recursividad” en el título

La recursividad está presente en muchos sistemas del mundo real. Y por

Se dice que un sistema es recursivo cuando está parcial o

Una imagen recursiva podemos definirla, por ejemplo, de la siguiente

Por ejemplo, en la figura 6.1. se representa este dibujo de definición

Figura 6.1.: Conjunto de Cantor

Pero además de poder mostrar con este concepto algunas curiosidades

El algoritmo de Euclides es recurrente. El máximo común divisor de

Él cálculo del factorial: podemos definir el factorial de un entero

La búsqueda de un término de la serie de Fibonacci: Podemos definir

Cálculo de una fila del triángulo de Tartaglia. Es conocida la

𝑡𝑖,0 = 1; 𝑡𝑖,𝑖 = 1; 𝑡𝑖,𝑗 (𝑗 ≠0,𝑗 ≠𝑖) = 𝑡𝑖−1,𝑗 −1 + 𝑡𝑖−1,𝑗 .

encontrar la solución que antes habíamos buscado mediante el cálculo

En todos los casos hemos visto un camino para definir un procedimiento

1. Lo indicaba el diccionario de la RAE: Propiedad de aquellas

2. Es imprescindible que, además, haya unos valores iniciales

La recursividad es una herramienta de diseño de algoritmos aceptada en

invocaciones termina felizmente en alguna o varias llamadas que no

Cuando un procedimiento recursivo se invoca por primera vez decimos

Si una función o procedimiento 𝑃 contiene una referencia explícita a sí

Veamos el ejemplo de una función recursiva que calcula el factorial de

Supongamos que invocamos al procedimiento con el valor 𝑁 = 5 . La

Tabla 6.1.: Llamadas al procedimiento definido para el

La demostración por inducción o recurrencia.

La demostración por recurrencia se emplea para establecer que una

Se demuestra que 𝑃 es cierto para todo natural a partir de los siguientes

a) Base de la inducción o recurrencia: Demostrar que 𝑃 es cierto para

b) Recurrencia: se demuestra que la propiedad es hereditaria. Para

Ejemplos de esta forma de demostración hay muchos. Presentamos aquí

Podemos demostrarlo con los dos pasos antes indicados:

c) Entonces, demostrar que se cumple para 𝑘 + 1:

Definición recurrente de un conjunto.

La noción de conjunto juega un papel importante en la programación y

La definición recurrente de un conjunto muestra el modo de construir

La definición recurrente de conjuntos contiene dos partes:

a) Base: se describen (por comprensión o por extensión) los elementos

b) Recurrencia: se ofrece una formulación recurrente de las reglas

Por ejemplo, para definir el conjunto de los naturales, basta decir:

a) Base: 1 es un número natural.

b) Recurrencia: El siguiente de un número natural es un natural. Es

Otro ejemplo: si queremos definir el conjunto de los enteros impares,

a) Base: el entero 1 es impar.

b) Recurrencia: Sea 𝑥 impar. Entonces 𝑥 + 2 también es impar.

Demostración recurrente de propiedades sobre

a) Base: demostrar que la propiedad 𝑃 es cierta para todos los

b) Recurrencia: La hipótesis de recurrencia consiste en suponer que

Por ejemplo, supongamos que queremos demostrar que el 𝑖 –ésimo

Para demostrarlo, primero verificamos que efectivamente se cumple así

Y acudimos ahora a la recurrencia: Suponiendo que 𝑥𝑖 = 2 · 𝑖 − 1 , ¿es

Etapas en la construcción de algoritmos recursivos.

Veamos con un ejemplo cómo podemos estudiar un problema de forma

Se considera una calle adoquinada. Cada adoquín está numerado a

Figura 6.2.: Adoquines de la rayuela.