Estructuras de Datos

Algoritmos Recursivos

Luis Garrido

1
Matrushka
 La Matrushka es una artesanía tradicional
rusa. Es una muñeca de madera que
contiene otra muñeca más pequeña dentro
de sí. Ésta muñeca, también contiene otra
muñeca dentro. Y así, una dentro de otra.

2
 Recursividad: el concepto

 La recursividad es un concepto fundamental en

matemáticas y en computación.
 Es una alternativa diferente para implementar
estructuras de repetición (ciclos). Los módulos
se hacen llamadas recursivas.
 Se puede usar en toda situación en la cual la
solución pueda ser expresada como una
secuencia de movimientos, pasos o
transformaciones gobernadas por un conjunto
de reglas no ambiguas. 3
Introducción
 Un procedimiento o función recursiva es aquella
que se llama a si misma.
 La ejecución del proceso recursivo se repite con valores
(parámetros) diferentes.
 La recursividad es una alternativa a la iteración
muy elegante en la resolución de problemas de
naturaleza recursiva. Permite especificar una
solución simple y natural para resolver
problemas definidos en términos de sí mismos.
 Ejemplo: Los números naturales
 0 es un número Natural
 El siguiente número de un número natural es otro nro natural
4
Algoritmos Recursivos
 La recursividad está relacionada con el principio de
inducción.
 Existe un caso base, en el que no existe ninguna llamada
recursiva.(Condición o criterio base)
 Existe un caso general conocido como caso inductivo, en las
que se realizan llamadas a versiones de la misma función con
parámetros diferentes que conducen al caso base.
 Por lo tanto
 Hay que incluir por lo menos un caso base, que se resuelva sin
necesidad de recursividad.
 Todas las llamadas recursivas deben levar hacia el caso base
 El método debe comprobar si se debe realizar una nueva
llamada recursiva o si ya se ha alcanzado el caso base.
5
Algoritmos Recursivos
 El caso base
 Supone el final de las llamadas recursivas.
 Y la realización de llamadas recursiva que lleva a él lo
que evita se entre en ciclos infinitos.
 Para crear una función recursiva, es necesario
tener una definición recursiva del problema.
 Ejemplo: Suma de los primeros números naturales.
Caso Base: s(1) = 1;
Caso general: s(n) = s(n-1) + n
El problema esta definido en forma recursiva, para conocer la
suma de n números se debe conocer previamente la suma
de los n-1 números anteriores.

6
Suma recursiva de los n primeros
números naturales
int SumaNat(int n)
{
int s;
if (n = = 1)
s = 1; // Caso Base
else
s = SumaNat(n-1) + n; // Caso general
return(s);
}
7
 Funcionamiento de la recursividad
 Nótese que en una función recursiva es
necesaria una condición para distinguir el caso
base del inductivo.
 Para entender como funciona la recursividad
es necesario tener bien claro que en memoria
no existe una sola versión de la función
recursiva.
 Cada vez que se invoque la función recursiva
se crea una nueva versión de la misma.
 La estructura de todas la versiones es la
misma, pero no así los datos que contiene
cada una

8
Ejemplo: factorial

Escribe un programa que calcule el factorial (!) de un entero no negativo.

He aquí algunos ejemplos de factoriales:

 1! = 1
 2! = 2  2*1
 3! = 6  3*2*1
 4! = 24  4*3*2*1
 5! = 120  5*4*3*2*1

9
 Ejemplo: factorial (iterativo -
repetetitivo)

int factorial (int n) public int factorial (int n) {

comienza int fact = 1;

fact  1 for (int i = 1; i <= n; i++)

para i  1 hasta n fact = i * fact;

fact  i * fact return fact;

regresa fact }

termina
10
 Ejemplo: factorial (recursivo)

int factorial (int n) public int factorial (int n) {

comienza if n == 0 return 1;
si n = 0 entonces
else
regresa 1
return factorial (n-1) * n;
otro
regresa factorial (n-1)*n }
termina

11
Ejemplo:
 A continuación se puede ver la secuencia de
factoriales.

 0! =1
 1! = 1 =1*1 = 1 * 0!
 2! = 2 =2*1 = 2 * 1!
 3! = 6 =3*2 *1 = 3 * 2!
 4! = 24 = 4 * 3 * 2 * 1 = 4 * 3!
 5! = 120 = 5 * 4 * 3 * 2 * 1 = 5 * 4!
 ...
 N! = = N * (N – 1)!
12
 Solución
Aquí podemos ver la secuencia que toma el 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
13

definición.
Solución Recursiva
Dado un entero no negativo x, regresar el factorial de x fact:
Entrada n entero no negativo,
Salida:entero. Es importante
determinar un caso
int fact (int n) base, es decir un
{ punto en el cual
if (n == 0) existe una
return 1; condición por la
else
cual no se requiera
return fact(n – 1) * n ;
volver a llamar a la
}
misma función.
14
¿Cómo funciona la recursividad?
Llamadas recursivas

Resultados de las llamadas recursivas

15
Funcionamiento de la recursividad

Main
n=3 Devuelve 2*3 = 6 IDA VUELTA
Factorial(2)*3 Llamada n Valor
Factorial
n=2 1ª 3 6
Devuelve 1*2 = 2 2ª 2 2
Factorial Factorial(1)*2 3ª 1 1
4ª caso base 0 1
n=1
Devuelve 1*1 = 1
Factorial Factorial(0)*1
n=0
Devuelve 1
Factorial
16
¿Cómo funciona la
recursividad?

17
Factorial de un número
Caso base: fact(0) = 1
Caso general: fact(n) = fact(n-1)·n
Int fact(int n)
{
if n(= =0)
return(1);
else
return(fact(n-1)*n)
}
18
 Funcionamiento de la recursividad
 En el anterior ejemplo se ilustro cómo las llamadas
recursivas se van produciendo hasta alcanzar el caso base.
 En ese punto se acaban las llamadas y empiezan las
devoluciones de valores hasta llegar al método main.
 Tenemos un movimiento en 2 sentidos
1º Hacia delante hasta alcanzar el caso base.
2º Hacia atrás devolviendo los resultados de cada llamada a la
función.
 Las llamadas realizadas implican una estructura pila.
 En cada llamada se realiza una copia de la función recursiva
(cada llamada implica una nueva copia de las variables de la
función). Esto consume memoria.
19
Correctitud en la recursividad
 ¿Cómo podemos determinar si un Algoritmo Recursivo es o no
correcto?
 Por simple observación es difícil.
 Es posible alcanzar ese objetivo con la ayuda del principio de inducción.
 Verificando 1º el caso base, comprobando si devuelve el resultado correcto para
el valor más pequeño.
 Verificando si el algoritmo funciona correctamente para cualquier valor.

20
Recursividad vs. Iteración

 Características comunes:
1. Ambas implican repetición
– La iteración usa explícitamente una estructura de repetición mientras que la
recursión logra la repetición mediante llamadas sucesivas a una función.

2. Ambas requieren de una condición de fin.

– La iteración termina cuando deja de cumplirse la condición para terminar el
ciclo y la recursión cuando se reconoce un caso base.

21
Recursividad vs. Iteración

3. Ambas se aproximan gradualmente a la terminación.

• La iteración continua modificando un contador, hasta
que éste adquiere un valor que hace que deje de
cumplirse la condición del ciclo.
• La recursividad sigue produciendo versiones más
sencillas del problema original hasta llegar al caso base.

22
Recursividad vs. Iteración

4. Pueden continuar indefinidamente

• En la iteración ocurre un ciclo infinito, si la condición
del ciclo nunca deja de cumplirse.
• Se tiene una recursión infinita si cada llamada recursiva
no simplifica el problema y no se alcanza el caso base o
si aún dirigiéndonos al caso base, lo saltamos.

23
 Recursividad vs. Iteración

 Diferencias.
 La recursividad presenta una desventaja frente a la iteración:
la invocación repetida de la función.Cada llamada hace que
se cree otra copia de la función esto puede consumir una
cantidad excesiva de memoria.
 La iteración ocurre en la misma función, con lo que se omite
el gasto extra de llamadas a la función.
 Toda tarea que pueda realizarse con recursividad puede
también realizarse con una solución iterativa.
 Se elige la solución recursiva cuando este enfoque
refleja de forma más natural la solución del problema y
produce un programa más fácil de entender y depurar.
 Existen problemas cuya solución iterativa no es viable
por lo tanto la recursión es una solución.
24
Simulación de la recursividad

 Es posible simular la recursividad a

través del uso de una estructura pila
y así emular llamadas recursivas.
 Los parámetros de las llamadas a la
función se van almacenado en una
pila hasta alcanzar el caso base.
 La vuelta atrás se consigue, sacando
de la pila las los elementos
almacenados y procesándolos uno a
uno hasta que la pila quede vacía.
25
Ejemplo de Recursividad Poco
eficiente

Codigo Recursivo Codigo Iteractivo

def fib(n):
def fib(n): """ Precondición: n debe ser >= 0.
""" Precondición: n debe Devuelve: el número de fibonacci número n. """
ser >= 0. Devuelve: if n == 0 or n == 1: return n
el número de fibonacci ant2 = 0 ant1 = 1
número n. ""“ for i in xrange(2, n+1):
if n == 0 or n == 1: fibn = ant1 + ant2
return n ant2 = ant1
ant1 = fibn
return fib(n-1) + fib(n-2) return fibn

26
Pasos para convertir un ciclo
en un programa recursivo
1. Reemplazar el ciclo for por sus instrucciones
elementales
A. Asignar valor inicial a la variable controladora del ciclo
B. Escribir una instrucción if que compare el valor de la
variable controladora del ciclo con el valor final
C. Rotular el if escrito en B
D. Escribir las instrucciones propias del ciclo
E. Incremenetar la variable controladora del ciclo
F. Tansferir el control (GOTO) al label definido en C
G. Cerrar el if definido en B

27
Pasos para convertir un ciclo
en un programa recursivo
2. El subprograma recursivo lo conformarán todas las
instrucciones del ciclo y su parámetro es la variable
controladora del ciclo.
3. En el programa que lo llama se suprimen todas las
instrucciones del ciclo y se reemplaza el valor de
asignación del valor inicial de la variable controladora
del ciclo por un llamada recursiva. El valor del
parámetro en esta llamada es el valor inicial de la
variable controladora del ciclo.
4. En el subprograma se reemplazan las instrucciones de
incrementos de la variable controladora del ciclo y de
transferencia de control (goto) por una llamada
recursiva teniendo como parámetro la variable
controladora del ciclo modificada 28
Ejemplo para convertir un ciclo
en un programa recursivo

 Sea el programa:
 Read(n,x)
 For (i = 1 to n ) haga
 X=X+1

 Endfor
 Write x

 x y n son variables globales

Recursividad - Lic. Rosemary Torrico B. 29

Resolviendo Paso 2 : Programa
recursivo lo conforman

 I=1
 Lb : If (i <= n ) Then
 X=X+1
 i=i+1
 Goto Lb

 Endif

Recursividad - Lic. Rosemary Torrico B. 30

Resolviendo Paso 3
: Programa Principal quedaría asi

 Read(x,n)
 SR(1)
 Write(x)

Recursividad - Lic. Rosemary Torrico B. 31

Resolviendo Paso 3 : Programa
Recursivo quedaría así

 Subprograma SR(i)
 If i<=n then
 x= x+1
 SR(i+1)
 Endif

Recursividad - Lic. Rosemary Torrico B. 32