Tema 2.

Recursividad
Estructuras de Datos

1
¿Qué es la recursividad?

Es un concepto fundamental en
matemáticas y en computación.

Es una alternativa diferente para

implementar estructuras de
repetición
Se puede usar si la solución
puede ser expresada como una
secuencia de pasos, movimientos
o transformaciones gobernadas
por un conjunto de reglas no
ambiguas.

2
Función recursiva

Las funciones recursivas se componen de:

• Caso base: una solución simple para un

caso particular (puede haber más de un
caso base).
• Caso recursivo: la solución para los
problemas sucesivos de menor complejidad

3
Función recursiva
Caso recursivo: una solución que vuelve a
utilizar la función original, con parámetros que
se acercan más al caso base.
Pasos que sigue el caso recursivo:

• El procedimiento se llama a sí mismo.

• El problema se resuelve, resolviendo un
problema similar de menor tamaño.
• El caso base eventualmente se alcanzará.

4
Recursividad

La secuenciación, iteración condicional y selección son

estructuras válidas de control que pueden ser
consideradas como enunciados.

NOTA: Regla recursiva Las estructuras de control que se pueden

formar combinando de manera válida la secuenciación, iteración
condicional y selección también son válidos.

5
Función
recursiva
6
¿Cómo escribir una función en forma
recursiva?

<tipo_de_regreso><nom_fnc> (<param>){
[declaración de variables]
[condición de salida]
[instrucciones]
[llamada a <nom_fnc> (<param>)]
return <resultado>
}

7
¿Por qué escribir
programas recursivos?
Son más cercanos a la descripción matemática.

Generalmente más fáciles de analizar

Se adaptan mejor a las estructuras de datos recursivas.

Los algoritmos recursivos ofrecen soluciones

estructuradas, modulares y elegantemente simples.

8
Ejemplo: factorial
Escribe un programa que calcule el factorial
(!) de un entero positivo. He aquí algunos
ejemplos de factoriales:

◦ 0! = 1
◦ 1! = 1
◦ 2! = 2 ➔ 2! = 2 * 1!
◦ 3! = 6 ➔ 3! = 3 * 2!
◦ 4! = 24 ➔ 4! = 4 * 3!
◦ 5! = 120 ➔ 5! = 5 * 4!

9
 Razonamiento recursivo
Aquí podemos ver la secuencia del factorial:

1 si N == 0 (base)
N! =

N * (N – 1) ! si N > 0 (recursión)

Un razonamiento recursivo tiene dos partes: la

base y la regla recursiva de construcción. La
base no es recursiva y es el punto tanto de partida
como de terminación de la definición.

10
Solución Recursiva

Dado un entero positivo x, regresar el factorial de x:

Entrada: n entero positivo
Salida: entero. Es importante determinar
un caso base, es decir un
int fact (int n) punto en el cual existe una
{ condición por la cual no se
requiera volver a llamar a
if (n == 0) la misma función.
return 1;
else
return fact(n – 1) * n ;
}

11
Ejemplo: factorial
(iterativo vs recursivo)

public int factorial (int n) {

int fact = 1;
for (int i = 1; i <= n; i++)
fact *= i;
return fact; public int factorial (int n) {
} if n == 0 return 1;
else
return factorial (n-1) * n;
}

12
 Recursión vs. iteración
En ambos casos podemos tener
ciclos infinitos
Repetición Terminación

Recursión: Iteración:
Recursión: se
Iteración: ciclo repetidas el ciclo termina reconoce el
explícito invocaciones a o la condición caso base
método del ciclo falla

13
Ejercicio
Considere la siguiente ecuación recurrente:

an = an-1 + 2n
a0 = 1

Escribe el algoritmo de la solución.

14
Solución del ejercicio anterior

double a (int n) {
if ( n==0)
return 1;
else
return a( n – 1) + Math.pow( 2, n);

15
Elementos de la recursividad
16
Una imagen dice más que mil
palabras…

17
¿Cuándo usar recursividad?
Sí usar: No usar:

• Para simplificar el • Cuando los métodos

código. usen arreglos
• Cuando la estructura grandes.
de datos es recursiva • Cuando el método
ejemplo: árboles. cambia de manera
impredecible de
campos.
• Cuando las
iteraciones sean la
mejor opción.

18
Tipos de recursividad.

● Directa: cuando f1(n) incluye una

llamada a sí misma.

● Indirecta: cuando f1 llama f2 y ésta

causa que f1 sea invocada.

NOTA: para cada llamada recursiva se crean

copias independientes de las variables declaradas
en la función.

19
Tipos de recursividad.

20
Otros ejemplos
●

String invierte (String cadena, int pos){

if (pos == cadena.length( ) )
return “”; // comillas vacías: cadena vacía
else
return invierte(cadena, pos+1)+ cadena.charAt(pos);
}

21
 Prueba de escritorio
cadena=“HOLA”

H O L A
Pos → 0 1 2 3
INVOCACIÓN CADENA POS invierte(cad,pos+1) + Valor de retorno
charAt(pos)

invierte(cad,0) “HOLA” 0 return invierte(cad, 1) + “H” “ALOH”

invierte(cad,1) “HOLA” 1 return invierte(cad, 2) + “O” “ALO”

invierte(cad,2) “HOLA” 2 return invierte(cad, 3) + “L” “AL”

invierte(cad,3) “HOLA” 3 return invierte(cad, 4) + “A” “A”

invierte(cad,4) “HOLA” 4 return null null

22
Otros Ejemplos de recursividad:

boolean misterio (String c, int limIzq, int limDer) {

if (limIzq > limDer)
return true;
else
if (c.charAt(limIzq) == c.charAt(limDer))
return misterio(c, limIzq+1, limDer-1)
else
return false;
}

23
Ejercicio:

Realiza la prueba de escritorio si

invocamos el método con los parámetros
siguientes:

a) misterio(“seres”, 0, 4);

b) misterio (“vivos”, 0, 4);

24
Ejercicio:
a) misterio(“seres”, 0, 4); // true

C=“seres” limIzq=0 limDer=4

return misterio(“seres”, 1, 3)
C=“seres” limIzq=1 limDer=3
return misterio(“seres”, 2, 2)
C=“seres” limIzq=2 limDer=2
return misterio(“seres”, 3, 1)
C=“seres” limIzq=3 limDer=1
return true;
25
Ejercicio:

b) misterio (“vivos”, 0, 4);

C=“vivos” limIzq=0 limDer=4

Else //’v’ == ‘s’

if (c.charAt(limIzq) == c.charAt(limDer))
return misterio(c, limIzq+1, limDer-1)
else
return false;

26
Ejemplo: Serie de Fibonacci

Valores: 0, 1, 1, 2, 3, 5, 8...
Cada término de la serie suma los 2 anteriores. Fórmula recursiva
fib(n) = fib (n - 1) + fib (n - 2)
Caso base: Fib (0)=0;
Fib (1)=1
Caso recursivo: |Fib (i) = Fib (i -1) + Fib(i -2)
public static int fib(int n){
if (n <= 1) return n; //condición base
else
return fib(n-1)+fib(n-2); //condición recursiva
}
27
Ejemplo: Serie de Fibonacci
Traza del cálculo recursivo
Fib(3)

return Fib(2) + Fib(1)

return Fib(1) + Fib(0) return 1

return 1 return 0

28
Trampas sutiles: Código
ineficiente.

public int fib (int n) public int fib (int n)

{ {
if (n < 2) int f1 = 1, f2 = 1, nuevo;
return n; while (n > 2)
else {
return fib (n-2) + nuevo = f1 + f2;
fib (n-1); f1 = f2; f2 = nuevo;
} n--;
}
return f2;
}
fib (100) toma demasiado fib (100) toma tan sólo
tiempo en dar el unos nanosegundos en
resultado dar el resultado.

29
Serie fibonacci
Iteración vs recursión

30
Ejercicio
●Escribir el método correspondiente a la siguiente
función:
Función de Ackerman

ACK(0, n) = n+1; n> 0

ACK(m, 0) = ACK(m-1, 1); m>0

ACK(m, n) = ACK(m-1, ACK(m, n-1)); m>0, n>0

31
El siguiente es el modelo matemático de la función de Ackerman.
En el método que construyas, señala los elementos de la recursividad.

n+1 m=0, n> 0

Ack(m,n) = Ack(m-1, 1) m>0; n=0

Ack(m-1, Ack(m, n-1)) m>0; n>0

32
Potencia de un número
potencia(n, exponente) =

1, si exponente = 0

n * potencia(n, exponente - 1)
En cualquier otro caso.

33
 Numero exponente

Numero exponente es Nexp

Potencia(numero, exponente) = Cuando…

1 si exponente = 0

numero * potencia(numero, exponente – 1) Si exponente !=0

34
“Dividir para vencer”

● Muchas veces es posible dividir un problema

en subproblemas más pequeños,
generalmente del mismo tamaño, resolver los
subproblemas y entonces combinar sus
soluciones para obtener la solución del
problema original.

35
“Dividir para vencer”

● Dividir para vencer es una técnica natural

para las estructuras de datos, ya que por
definición están compuestas por piezas.
Cuando una estructura de tamaño finito se
divide, las últimas piezas ya no podrán ser
divididas.

36
Ejemplo: Encontrar el número mayor de un
arreglo de enteros:

static int mayor (int[ ] A, int limIzq, int limDer)

Si limIzq = limDer entonces ;
regresa A[limIzq]
sino
m = (limIzq + limDer) / 2
mayorIzq = mayor (A, limIzq, m)
mayorDer = mayor (A, m +1, limDer)
si mayorIzq > mayorDer entonces
regresa mayorIzq
sino regresa mayorDer
finsi
finsi

37
Un ejercicio más...

Diseñar e implementar en un
programa el Algoritmo de Euclides
para calcular el máximo común
divisor (mcd) de dos enteros
positivos.
¿Qué es el mcd?

38
Un ejercicio más...
El mcd es el valor mayor que permite
dividir a los dos valores originales sin
que quede ningún resto (o residuo).

¿Cuáles son los casos que pueden

presentarse? ¿Cuál es el caso más
simple en este problema?

39
Un ejercicio más...
Definimos la función:
mcd(n1, n2) = n2, si n2 <= n1 y
n1 % n2 = 0
mcd(n1, n2) = mcd(n2, n1), si n1
< n2
en los otros casos:
mcd(n1, n2) = mcd(n2, n1%n2)

40
Un ejercicio más...

Ahora que hemos analizado la función

mcd(n1, n2), escribe el método
correspondiente en Java.

41
Autoevaluación recursiva OO
Identifica en el siguiente método los elementos de la recursividad:

void aprenderRecursividad(Competencias misCompetencias){

if (misCompetencias.séUsarRecursividad())
return;
else
aprenderRecursividad(misCompetencias.practicarRecursividad());

Noemí Lara Acono ✿

42
43
Referencias
https://www.utm.mx/~dtorres/cursos/estructuradedatos/tema3Recursi
vidad.pdf

44