INSTITUTO DE ESTUDIOS SUPERIORES DEL
ESTADO
MATEMATICAS DISCRETAS II
ING. ALICIA ARACELI MENDEZ ROMERO
ALUMNO: ROLANDO VALDIVIA GALICIA
- UNIDAD III
- ALGORITMOS RECURSIVOS
- EJEMPLOS
1
RECURSIVIDAD
La recursividad forma parte del repertorio para resolver problemas en Computacin y es de los
mtodos ms poderosos y usados.
Los algoritmos recursivos ofrecen soluciones estructuradas, modulares y elegantemente simples.
La recursividad es un concepto fundamental en matemticas y en computacin. Una definicin
recursiva dice cmo obtener conceptos nuevos empleando el mismo concepto que intenta describir.
En toda situacin en la cual la respuesta pueda ser expresada como una secuencia de movimientos,
pasos o transformaciones gobernadas por un conjunto de reglas no ambiguas, la frmula recursiva
es un buen candidado para resolver el problema.
Los razonamientos recursivos se encuentran en la base misma de las matemticas porque son
necesarios para describir conceptos centrales como el de nmero:
Ejemplo:
1. Factorial
Definicin:
factorial (n) = n! si n > 0
factorial (n) = n*n-1*n-2* ... * 1 si n > 0
el valor de 0! se define como
factorial (0) = 1
Su definicin recursiva es:
factorial (n) = 1 si n = 0
factorial (n) = n* factorial (n-1) si n > 0
as para calcular el factorial de 4:
factorial (4) = 4 * factorial (3) = 4 * 6 = 24
factorial (3) = 3 * factorial (2) = 3 *2 = 6
factorial (2) = 2 * factorial (1) = 2 * 1 = 2
factorial (1) = 1 * factorial (0) = 1 * 1 = 1
esttica int factorial (int n)
comienza
si n = 0 entonces
2
regresa 1
otro
regresa factorial (n-1) * n
termina
Versin iterativa:
esttica int factorial (int n)
comienza
fact 1
para i 1 hasta n
fact i * fact
regresa fact
termina
Las definiciones recursivas de funciones en matemticas que tienen como argumentos nmeros
enteros, se llaman relaciones de recurrencia.
Forma de una ecuacin de recurrencia:
coar +c1ar-1 + c2ar-2 + ....+ ckar-k = f(r) funcin matemtica discreta
donde ci son constantes, es llamada una ecuacin de recurrencia de coeficientes constantes de
orden k, condicionada a que c0 y ck = 0.
Una definicin recursiva dice cmo obtener conceptos nuevos empleando el mismo concepto que
intenta definir.
El poder de la recursividad es que los procedimientos o conceptos complejos pueden expresarse de
una forma simple.
Un razonamiento recursivo tiene dos partes: la base y la regla recursiva de construccin. La base no
es recursiva y es el punto tanto de partida como de terminacin de la definicin.
Ejemplo:
Base: La secuenciacin, iteracin condicional y seleccin son estructuras vlidas de control
que pueden ser consideradas como enunciados.
Regla recursiva: Las estructuras de control que se pueden formar combinando de manera
vlida la secuenciacin iteracin condicional y seleccin tambin son vlidos.
Un conjunto de objetos est definido recursivamente siempre que:
(B) algunos elementos del conjunto se especifican explcitamente
3
(R) el resto de los elementos del conjunto se definen en trminos de los elementos ya
definidos
donde
(B) se llama base
(R) se llama clusula recursiva
Observaciones:
1. El procedimiento se llama a si mismo
2. El problema se resuelve, resolviendo el mismo problema pero de tamao menor
3. La manera en la cual el tamao del problema disminuye asegura que el caso base eventualmente
se alcanzar
La recursividad es un mtodo poderoso usado en inteligencia artificial, su poder es que algunos
conceptos complejos pueden expresarse en una forma simple. Una definicin recursiva difiere de
una definicin circular en que tiene una forma de escapar de su expansin infinita. Este escape se
encuentra en la definicin o porcin no recursiva o terminal de la definicin.
Las frmulas recursivas pueden aplicarse a situaciones tales como prueba de teoremas, solucin de
problemas combinatorios, algunos acertijos, etc.
Ejemplos:
1. Nmeros de Fibonacci
Los nmeros de Fibonacci se definen como:
FN = FN-1 + FN-2 para N > 2
F0 = F1 = 1
que definen la secuencia:
1,1,2,3,5,8,13,21,34,55,89,144, .....
Por ejemplo, si quisiramos encontrar Fibonacci de 5, entonces:
Fibonacci (5) = Fibonacci (4) + Fibonacci (3)
Fibonacci (4) = Fibonacci (3) + Fibonacci (2)
Fibonacci (3) = Fibonacci (2) + Fibonacci (1)
Fibonacci (2) = Fibonacci (1) + Fibonacci (0)
De manera iterativa el algoritmo podra ser:
esttica int Fibonacci (int n)
// versin iterativa
4
comienza
fibo [0] 1
fibo [1] 1
para i 1 hasta n
fibo [i] fibo [i-1]+ fibo [i-2]
regresa fibo [n]
termina
Resolviendo el mismo problema pero de manera recursiva, obtenemos:
esttica int Fibonacci (int n)
//versin recursiva
comienza
si n < 1 entonces
regresa 1
otro
regresa Fibonacci (n-1) + Fibonacci (n-2)
termina
2. Considere la siguiente ecuacin recurrente:
an = an-1 + 2n
a0 = 1
esttica int a (int n)
comienza
si n = 0 entonces
regresa1
otro
regresa 2^n + a (n-1)
termina
Los valores de los trminos de una sucesin pueden darse de manera explcita mediante frmulas
como:
Sn = n4 - 3n3 - 2n
pero tambin pueden definirse por medio de descripciones que involucren otros trminos que les
anteceden en la sucesin.
por ejemplo:
i n
i 1
i 1
i 5 i 4 i 3 i 2 i 1
i 5 i 5 4 i 5 4 3 i 5 4 3 2 i 5 4 3 2 1 15
i 2 i 2 i 2 i 1 i 1
5
esttica int suma (int i, int n)
comienza
si i = n entonces
regresa i
otro
regresa n + suma (i,n-1)
termina
4. Definicin recursiva para elevar un nmero a una potencia: Un nmero elevado a la potencia cero
produce la unidad; la potencia de un nmero se obtiene multiplicndolo por s mismo elevando a la
potencia menos uno. Por ejemplo:
32 = 3*(31) = 3*(3*30) = 3*(3*1)= 3*(3) = 9
esttica int potencia (int n, int k)
comienza
si k=0 entonces
regresa 1
otro
regresa n * potencia (n,k-1)
termina
5. Nmero de Combinaciones
Recursivamente, podemos definir el nmero de combinaciones de m objetos tomados de n,
denotado (n,m) para n> 1 y 0 < m < n por:
(n,m) = 1 si m = 0 m = n n = 1
(n,m) = (n-1, m) + (n-1,m-1) en otro caso
esttica int combinaciones (int n, int m)
comienza
si m = 0 o m = n o n = 1 entonces
regresa 1
otro
regresa combinaciones (n-1,m) + combinaciones (n-1,m-1)
termina
6. Algoritmo de Euclides
Este algoritmo es considerado el ms viejo no trivial.
El paso esencial que garantiza la validez del algoritmo consiste en mostrar que el mximo comn
divisor (mcd) de a y b, (a > b > 0), es igual a a si b es cero, en otro caso es igual al mcd de b y el
remanente de a dividido por b, si b > 0.
6
esttica int mcd (int a,b)
comienza
si b = 0
regresa a
otro
regresa mcd (b, a mod b)
termina
Ejemplos:
mcd (25, 5) = mcd (5,0) = 5
mcd (18,6) = mcd (6,0) = 6
mcd (57, 23) = mcd (23, 1) = mcd (1,0) = 1
mcd (35, 16) = mcd (16,3) = mcd (3, 1) = mcd (1, 0) = 1
Definicin: Cuando una llamada recursiva es la ltima posicin ejecutada del procedimiento se llama
recursividad de cola, recursividad de extremo final o recursin de extremo de cola.
Definicin: Cuando un procedimiento incluye una llamada a si mismo se conoce como recursin
directa.
Definicin: Cuando un procedimiento llama a otro procedimiento y este causa que el procedimiento
original sea invocado, se conoce como recursin indirecta.
Al principio algunas personas se sienten un poco incmodas con la recursividad, tal vez porque da
la impresin de ser un ciclo infinito, pero en realidad es menos peligrosa una recursin infinita que
un ciclo infinito, ya que una recursividad infinita pronto se queda sin espacio y termina el programa,
mientras que la iteracin infinita puede continuar mientras no se termine en forma manual.
Cuando un procedimiento recursivo se llama recursivamente a si mismo varias veces, para cada
llamada se crean copias independientes de las variables declaradas en el procedimiento.
7
/**
*Factorial.java
* @author Rolando Valdivia Galicia
*/
public class Recursividad {
public static void main(String[] args) {
int fac=5;
int a=Factorial(fac);
// Se hace el llamado a la funcion Factorial con el int fac
System.out.println(a);
}
// A continuacion la funcion recursiva del factorial
public static int Factorial(int n){
if(n==1 || n==0)
return 1;
else
return n*Factorial(n-1);
}
}
