Definición Un algoritmo es recursivo cuando se define en
términos de una versión más simple de si
mismo. Características 1. Debe existir una salida en la
que no se haga la llamada recursiva 2. La llamada recursiva debe
ser versión más simple que la llamada que la
invocó.
Multiplicación entera El producto de dos números
enteros a y b se puede definir recursivamente como sigue: a * b =
a si b == 1 a * b = a * (b – 1) + a si b>1 Ejemplo: 3*4
= 3*3+3 = 3*2+3+3=3*1+3+3+3 = 3+3+3+3 = 12
Definición recursiva del Factorial Definición n! =
1, si n = 0 n! = n (n – 1)!, si n > 0 5! = 5*4! = 5*4*3!
= 5*4*3*2! = 5*4*3*2*1! = 5*4*3*2*1*0! = 5*4*3*2*1*1 = 5*4*3*2*1
= 5*4*3*2 = 5*4*6 = 5*24 = 120
Algoritmo Algoritmo para evaluar el factorial de un
número. FUNCIÓN FACTORIAL(N:ENTERO) REGRESA ENTERO
1. SI N = 0 ENTONCES a. REGRESAR 1 2. SINO a. X = N – 1 b.
Y = N * FACTORIAL(X) c. REGRESAR Y
SIMULACIÓN DEL FACTORIAL DE 4
Factorial en C float fact(int n){ if(n == 0) return 1; else
return n*fact(n-1); }
Números de Fibinacci La secuencia de Fibonacci se define
de la siguiente manera. Los dos primeros elementos de la
secuencia son 0 y 1. Cualquier otro número de Fibonacci se
obtiene sumando los dos anteriores. 0, 1, 1, 2, 3, 5, 8, 13, 21,
34, 55, 89, …
DEFINICIÓN RECURSIVA DE LOS NÚMEROS DE FIBONACCI
Algoritmo para calcular el n-ésimo número de
Fibonacci. FUNCION FIB(N:ENTERO) REGRESA ENTERO 1. SI N = 0 OR N
= 1 ENTONCES a. REGRESA N 2. SINO a. X ¬ FIB(N-1) b. Y ¬
FIB(N-2) c. REGRESA X + Y fib(n) = n , si n = 0 o n = 1 fib(n) =
fib(n – 1) +fib(n – 2) , si n > 1
SIMULACIÓN DE FIB DE 5
Número de Fibonacci en C int fib(int n){ if(n == 0 || n ==
1) return n; else return fib(n-1)+fib(n-2); }
Máximo Común Divisor Un algoritmo recursivo es el
siguiente. El MCD de dos números x e y es y si y < x y
x es divisible entre y. El MCD de dos números x e y es
igual al MCD de y y x si x < y El MCD de dos números x
e y es igual al MCD de y y el residuo de la división
x/y.
Actividad Escriba el algoritmo para mcd en forma simbólica
y defina una función que calcule el mcd en C.
VERSIONES NO RECURSIVAS Algoritmo no recursivo para evaluar el
factorial FUNCION FACTORIAL(N: ENTERO) REGRESA ENTERO 1. SI N = 0
ENTONCES a. REGRESAR 1 2. SINO a. F ¬ 1 b. PARA I ¬ 1
HASTA N HACER 1. F ¬ F * I c. REGRESAR F Algoritmo no
recursivo para calcular el n-ésimo número de
Fibonacci. FUNCION FIB(N:ENTERO) REGRESA ENTERO 1. SI N = 0 OR N
= 1 ENTONCES a. REGRESA N 2. SINO a. X ¬ 0 b. Y ¬ 1 c.
PARA I ¬ 2 HASTA N HACER 1. F ¬ X + Y 2. X ¬ Y 3. Y
¬ F d. REGRESA F
Tarea 1. La función de Ackerman A está definida
para todos los enteros positivos m y n como sigue: A(0, n) = n +
1 A(m, 0) = A(m – 1, 1) A(m, n)= A(m – 1, A(m, n
– 1)) Escriba una función en C para calcular el
valor de la función de Ackerman. Pruebe evaluando algunos
valores de A(1, n), A(2, n) y A(3, n). Defina expresiones simples
para estas funciones. La función tiene un crecimiento
extremadamente grande para valores de m mayores que 3, por
ejemplo A(4,2) = 265536 – 3, evalúe A(4,1). 2.
Desarrolle la expansión de la función de Ackerman
del problema anterior para los siguientes parámetros:
A(1,2), A(1,3), A(2,1), A(2,2).
DEFINICIÓN RECURSIVA DE EXPRESIONES 1. Una
expresión es un término seguido por un signo
más seguido por un término, o un solo
término. 2. Un término es un factor seguido por un
asterisco seguido por un factor, o un factor solo. 3. Un factor
es una letra o una expresión encerrada entre
paréntesis.
FUNCIONES EXPR FUNCION EXPR REGRESA BOOLEANO 1. SI NOT TERM
ENTONCES a. REGRESA FALSO 2. SINO a. C ¬ SIGUIENTE
SÍMBOLO b. SI C<>'+' ENTONCES 1. P ¬ P – 1 2.
REGRESA VERDADERO c. SINO 1. REGRESA TERM Si no es un
término, termina Encontró un término, ve que
hay más adelante Se encontró un solo
término, p señala hasta donde es correcta la
expresión. Encontró dos términos separados
por +, verifica el segundo término. Encontró dos
términos separados por +, verifica el segundo
término.
FUNCION TERM REGRESA BOOLEANO 1. SI NOT FACT ENTONCES a. REGRESA
FALSO 2. SINO a. C ¬ SIGUIENTE SÍMBOLO b. SI
C<>'*' ENTONCES 1. P ¬ P – 1 2. REGRESA VERDADERO c.
SINO 1. REGRESA FACT Encontró dos factores separados por
*, verifica el segundo factor. Si no es un factor, termina
Encontró un factor, ve que hay más adelante Se
encontró un solo factor, p señala hasta donde es
correcto el término.
FUNCIÓN FACT FUNCION FACT REGRESA BOOLEANO 1. C ¬
SIGUIENTE SÍMBOLO 2. SI C<>'(' ENTONCES a. IF C ES
LETRA ENTONCES 1. REGRESA VERDADERO b. SINO 1. REGRESA FALSO 3.
SINO a. SI NOT EXPR ENTONCES 1. REGRESA FALSO b. SINO 1. C ¬
SIGUIENTE SÍMBOLO a. SI C=')' ENTONCES 1. REGRESA
VERDADERO b. SINO 1. REGRESA FALSO Es el factor una letra? Es el
factor una expresión entre paréntesis? Si es una
expresión entre paréntesis, términa con
“)”?
DEFINICIÓN RECURSIVA DEL DETERMINANTE Si a es una matriz
de 1 x 1, entonces det(a) = x. Si a es de orden mayor que 1,
calcule el determinante de a como sigue: Escoja cualquier fila o
columna. para cada elemento a[i, j] en esa fila o columna, forme
el producto (-1)(i+ j)*a[i, j]*det(menor(a[i, j])) Donde
det(menor(a[i, j])) es el determinante del menor de a[i, j].
det(a) = suma de todos los productos para la columna o fila
seleccionada.
ALGORITMO RECURSIVO PARA CALCULAR EL DETERMINANTE Algoritmo
recursivo para calcular el determinante de una matriz de orden n.
FUNCION DET(N:ENTERO; A:MATRIZ) REGRESA REAL 1. SI N=1 ENTONCES
a. REGRESA A[1,1] 2. SINO a. S ¬ 0 b. PARA I = 1 HASTA N
HACER 1. MENOR(A,N,I,J,B) 2. S ¬ S + SIGNO(I,J) *
A[I,J]*DET(N-1,B) c. REGRESA S
Calculadora recursiva Esta calculadora procesa expresiones
algebraicas normales como: 3+4+5, 3*(6-2)*sin(3*atan(0.25)^7)
Para esto definimos las siguientes funciones Expr –
expresión algebraica Smplexpr – procesa una
expresión simple: 3, 4*5, 8/6, 5/sin(2) Term –
procesa términos: 3, 4^5. Sfact – factor simple: 4,
-6 Fct – factor: (7+4.5), (sin(2)*8)
función expr (expresión) regresa real 1. e =
smplexpr 2. mientras el simbolo siguiente sea + o – 3. operador =
simbolo siguiente 4. obtener siguiente símbolo 5. si
operador es + 6 e = e+smplexpr 7. si operador es – 8. e =
e-smplexpr 9. regresa e función smplexpr (expresión
simple) regresa real 1. e = term 2. mientras el simbolo siguiente
sea * o / 3. operador = simbolo siguiente 4. obtener siguiente
símbolo 5. si operador es * 6 e = e*smplexpr 7. si
operador es / 8. e = e/smplexpr 9. regresa e
función term (término) regresa real 1. t = sfact
//término es un factor simple 2. mientras siguiente
símbolo=^ 3. obtener siguiente símbolo 4. t =
t^sfact 5. regresar t función fct (factor) 1. if simbolo
es un número 2. leer número y guardar en f 3. sino
4. si simbolo='(' 5. procesar nueva expresión y guardar en
f 6. sino 7. procesar función estandar y guardar en f 8.
regresar f función sfact (factor simple) 1. si simb='-' 2.
obtener siguiente símbolo 3. regresar -fct //factor 4.
sino 5. regresar fct
procesar nueva expresión 1. obtener siguiente
símbolo 2. f = expr 3. si simbolo=')' 4. obtener siguiente
símbolo 5. sino 6. error procesar función estandar
codigo para cada función 1. si se lee 'sin' 2. avansar 3
símbolos 3. f = sin(fct) Asi para cada
función
Lectura de un real en C void processAsNumber(){ char t[80]; t[0]
= ch; int i=0; nextp(); while(ch>='0'&&ch<='9'){
t[++i] = ch; nextp(); } if(ch=='.') do{ t[++i] = ch; nextp();
}while(ch>='0'&&ch<='9');
Cont. if(ch=='E'){ t[++i] = ch; nextp(); do{ t[++i] = ch;
nextp(); }while(ch>='0'&&ch<='9'); } t[++i] = '';
f = atof(t); }
ALGORITMO PARA CONVERTIR UNA CADENA EN PREFIJO A POSFIJO 1. Si la
hilera de prefijo es una sola variable, esta es equivalente a su
expresión de posfijo. 2. Considere op el primer operador
de la hilera de prefijo. 3. Encuentre el primer operando opnd1 de
la hilera. Conviértalo a posfijo y llámelo post1.
4. Encuentre el segundo operando opnd2 de la hilera.
Conviértalo a posfijo y llámelo post2. 5. Concatene
post1, post2, y op.
ALGORITMO DE CONVERSIÓN SUBRUTINA CONVERT(PREFIX:CADENA;
POSFIX:CADENA) 1 SI LONGIUD(PREFIX)=1 ENTONCES a. SI PREFIX[1] EN
['a'..'z','0'..'9','A'..'Z'] ENTONCES 1. POSFIX ¬ PREFIX
b.SINO 1. ERROR('hilera de prefijo invalida') 2. SINO a. OP ¬
PREFIX[1] b. M ¬ FIND(PREFIX,2) c. N ¬ FIND(PREFIX,M+2)
d. SI NOT(OP IN ['-', '+', '*', '/', '^']) OR (M=0) OR (N=0) OR
(M+N+1<>LONGITUD(PREFIX)) ENTONCES 1. ERROR('hilera de
prefijo invalida') e. SINO 1. OP1 ¬ COPY(PREFIX,2,M) 2. OP2
¬ COPY(PREFIX,M+2,N) 3. CONVERT(OP1,P1) 4. CONVERT(OP2,P2) 5.
POSFIX ¬ P1+P2+OP
ALGORITMO PARA ENCONTRAR CADENA DE PREFIJO Algoritmo para
encontrar la cadena de prefijo más larga a partir de la
posición P. FUNCION FIND(S:CADENA, P:ENTERO) REGRESA
ENTERO 1. SI P>LONGITUD(S) ENTONCES a. REGRESA 0 2. SINO a.
FIRST ¬ S[P] b. SI FIRST EN ['a'..'z','0'..'9','A'..'Z']
ENTONCES 1. REGRESA 1 c. SINO 1. M ¬ FIND(S,P+1) 2. N ¬
FIND(S,P+M+1) 3. SI (M=0)OR(N=0) ENTONCES a. REGRESA 0 4. SINO a.
REGRESA M+N+1
PROBLEMA DEL RECORRIDO DEL CABALLO Se trata de recorrer un
tablero de n x n utilizando un caballo de ajedrez visitando todas
las casillas una sola vez.
ALGORITMO DE VUELTA ATRÁSbacktraking Procedimiento Ensayar
nuevo movimiento 1. Iniciar el conjunto de movimientos posibles
2. REPETIR a. seleccionar el nuevo candidato de la lista de
futuros movimientos b. SI aceptable ENTONCES 1. Anotar movimiento
2. SI tablero no lleno ENTONCES a. Ensayar nuevo movimiento b. SI
no acertado ENTONCES 1. borrar la anotación anterior 3.
HASTA (movimiento acertado) or (no hay mas posibilidades)
Representación Arreglo bidimensional h[][] de enteros de n
x n para representar el tablero, h[x][y] = 0, la casilla no ha
sido visitada, h[x][y] = m, la casilla fue visitada en el
movimiento m. A partir de la posición x,y se selecciona u
y v como las coordenadas de un posible movimiento, según
las reglas del ajedrez. Anotar movimiento: h[u][v] = j Borrar
movimiento: h[u][v] = 0 Movimiento aceptable: h[u][v] == 0
Tablero no lleno: j < n^2
Pseudo código void ensayar(i, x, y, *q) bool q1=false;
Iniciar el conjunto de movimientos posibles do{ seleccionar el
nuevo candidato de la lista de futuros movimientos if(coord u y v
aceptables y h[u][v] == 0) h[u][v] = i; if(i < n*n)
ensayar(i+1, u. v, &q1) if(!q1) h[u][v] = 0; else q1 = true;
while((!q1 || hay mas posibilidades); *q = q1;
Estrategia de recorrido 6 7 5 8 4 1 3 2 Dado x ,y la primera
coordenada puede ser x+2, y+1, luego x+1, y+2, x–1, y+2,
etc. x–2 x–1 x x+1 x+2 y – 2 y +2 y +1 y y
– 1
Tarea Agregue las siguientes funciones a la calculadora
recursiva. constantes p, e. variables a, b, c y d Escriba un
programa para convertir de prefijo a posfijo utilizando el
algoritmo recursivo estudiado. Escriba un programa para resolver
el Sudoku utilizando el algoritmo de vuelta atrás.
Las torres de Hanoi Las torres de Hanoi constan de 3 postes A, B,
C. Inicialmente se colocan un cierto número de discos en
el poste A. El juego consiste en trasladar todos los discos al
poste C utilizando el poste B como auxiliar. Las reglas son: Solo
mover un disco a la vez. Nunca poner un disco mayor sobre otro
menor. Posición inicial Posición final
Algoritmo Torres Algoritmo para mover n discos del poste A al
poste C usando el poste B como auxiliar. 1. Si n == 1 mover el
disco de A a C y parar 2. Mover n-1 discos de A a B usando C como
auxiliar 3. Mover el disco restante de A a C 4. Mover n-1 discos
de B a C usando A como auxiliar
Algoritmo en C void moverDisco(int n, int desde, int hasta, int
auxiliar){ if(n == 1) printf("Mover disco 1 de %d a %dn“,
desde, hasta); else{ moverDisco(n-1, desde, auxiliar, hasta);
printf("Mover disco %d de %d a %dn“, n, desde, hasta);
moverDisco(n-1, auxiliar, hasta, desde); }} A C B C C A B B
A
Posible proyecto Modificar la calculadora para hacer operaciones
con números complejos. Ayuda: utilice la biblioteca
complex de c++, en ella se define una plantilla para definir
complejos, ponga double como tipo base. Se definen todos los
operadores y algunas funciones matemáticas.