UTN FRLP
Ing. en Sistemas de informacin
Concurso docenteSintaxis y Semntica del Lenguaje2014
Ing. Julin Perelli
TEMARIO
Tcnicas de recursin
Introduccion Ejemplos de usoDefinicinEjemplos de programacinBacktrackingRecursin vs iteracinUtilidad de la recursin
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
Problemas de naturaleza recursiva
Parsing matemtico: calculadora con parntesis2 (a 1) + (3 b)
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
Problemas de naturaleza recursiva
Ordenamiento: Quicksort / Merge sort
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
Problemas de naturaleza recursiva
Camino mas corto (dijkstra)
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
Problemas de naturaleza recursiva
Fractales
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
Problemas de naturaleza recursiva
Fractales
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
Algoritmo
Estructura condicional (if)
Funcin
Pila de ejecucin (Stack)
CONOCIMIENTOS REQUERIDOS
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
Qu es la recursin?
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
Frase popular
Para saber qu es la recursinprimero hay que saber
QU ES LA RECURSIN?
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
Frase popular
Para saber qu es la recursinprimero hay que saberqu es la recursin.
QU ES LA RECURSIN?
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
Algoritmo recursivo:un algoritmo que depende de la ejecucin repetida de s mismo.
QU ES LA RECURSIN, REALMENTE?
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
Algoritmo recursivo:un algoritmo que depende de la ejecucin repetida de s mismo.
QU ES LA RECURSIN, REALMENTE?
?
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
Algoritmo recursivo:
Function recursionInfinita();
Begin
recursionInfinita()
end
QU ES LA RECURSIN, REALMENTE?
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
Algoritmo recursivo:un algoritmo que depende de la ejecucin repetida de s mismo.
Function recursionInfinita()
Begin
recursionInfinita();
end
recursionInfinita()
QU ES LA RECURSIN, REALMENTE?
Function recursionInfinita()BeginrecursionInfinita();
endFunction recursionInfinita()BeginrecursionInfinita();
endFunction recursionInfinita()BeginrecursionInfinita();
end
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
Hacer un procedimiento recursivo que muestre por pantalla un nmero dado n.
EJERCICIO 1
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
Hacer un procedimiento recursivo que muestre por pantalla un
nmero dado n.Procedure contar(n: Integer);
Begin
WriteLn(n);
contar(n);
End
EJERCICIO 1
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
Hacer un procedimiento recursivo que muestre por pantalla un
nmero dado n.Procedure contar(n: Integer);
Begin
WriteLn(n);
contar(n);
End
EJERCICIO 1
Llamada recursiva
contar(5)
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
Hacer un procedimiento recursivo que muestre por pantalla un
nmero dado n.Procedure contar(n: Integer);
Begin
WriteLn(n);
contar(n);
End
EJERCICIO 1
Llamada recursiva
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
Function contar(n = 5)BeginWriteLn(n = 5);contar(n = 5)
end
contar(5)
Function contar(n = 5)BeginWriteLn(n = 5);contar(n = 5)
endcontar(5)
Function contar(n = 5)BeginWriteLn(n = 5);contar(n = 5)
endcontar(5)
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
Cada llamada ocupa memoria que nunca se libera, porque ningn procedimiento termina.
Computacin limitada por tamao de memoria.
Se genera un desbordamiento de pila.
ESTO NO SIRVE!
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
1. Llamada recursiva (por definicin).
2. Condicin de corte.
3. Cada llamada recursiva converge (se acerca) paso a paso a la condicin de corte.
ALGORITMO RECURSIVO TIL
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
Hacer un procedimiento recursivo que muestre por pantalla todos los nmeros naturales que existen desde un nmero dado n hasta 100.
EJERCICIO 2
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
Hacer un procedimiento recursivo que muestre por pantalla todos
los nmeros naturales que existen desde un nmero dado n hasta
100.procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
EJERCICIO 2
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2
1. Llamada recursiva
3. Acercamiento a la condicin de corte
2. Condicin de corte
Hacer un procedimiento recursivo que muestre por pantalla todos
los nmeros naturales que existen entre un nmero dado n hasta
100.procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2
procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
contar(98)
Impresin(registro de activacin)
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2
procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
contar(98)
98
Impresin
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2
contar(98)
procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
98
Impresin98
procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2
contar(98)
98 < 100 (true)
Impresin98
procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2
contar(98)
contar(98 +1)
Impresin98
99
procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2
contar(98)
contar(99)
procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
98
Impresin98
procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2
contar(98)
contar(99)
procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
98
99
Impresin9899
procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2
contar(98)
contar(99)
procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
98
99 < 100 (true)
Impresin9899
procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2
contar(98)
contar(99)
procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
98
contar(99 +1)
Impresin9899
procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2
contar(98)
contar(99)
procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
98
contar(100)
procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
100
99
Impresin9899100
procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2
contar(98)
contar(99)
procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
98
contar(100)
procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
99
100 < 100 (false)
Impresin9899100
procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2
contar(98)
contar(99)
procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
98
contar(100)
procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
99
100 < 100 (false)
Impresin9899100
procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2
contar(98)
contar(99)
procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
98
99
Impresin9899100
procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2
contar(98)
contar(99)
procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
98
99
Impresin9899100
procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2
contar(98)
98
Impresin9899100
procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2
contar(98)
98
Impresin9899100
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2
contar(98)
Impresin9899100
Hacer un procedimiento recursivo que muestre por pantalla todos
los nmeros naturales que existen entre un nmero dado n hasta 100 en
orden inverso.procedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
begin
contar(n+1);
end
end
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2b
2 recursin
1 impresin, proceso, accin
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2b
1 recursin
2 impresin, proceso, accin
Hacer un procedimiento recursivo que muestre por pantalla todos
los nmeros naturales que existen entre un nmero dado n hasta 100 en
orden inverso.procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2b
1 recursin
2 impresin, proceso, accin
Hacer un procedimiento recursivo que muestre por pantalla todos
los nmeros naturales que existen entre un nmero dado n hasta 100 en
orden inverso.procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
Backtracking
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2b
procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
contar(98)
Impresin(registro de activacin)
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2b
procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
contar(98)
Impresin98
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2b
procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
contar(98)
Impresin98 < 100 (true)
98
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2b
contar(98)
Impresin
procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
contar(98 +1)
98
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2b
contar(98)
Impresin
procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
contar(99)
procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
98
99
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2b
contar(98)
Impresin
procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
contar(99)
procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
98
99
99 < 100 (true)
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2b
contar(98)
Impresin
procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
contar(99)
procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
98
99
contar(99+1)
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2b
contar(98)
Impresin
procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
contar(99)
procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
98
99
procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
contar(100)
100
100 < 100 (false)
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2b
contar(98)
Impresin100
procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
contar(99)
procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
98
99
procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
contar(100)
100
100
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2b
contar(98)
Impresin100
procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
contar(99)
procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
98
99
procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
contar(100)
100
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2b
contar(98)
Impresin100
procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
contar(99)
procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
98
99
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2b
contar(98)
Impresin10099
procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
contar(99)
procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
98
99
99
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2b
contar(98)
Impresin10099
procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
contar(99)
procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
98
99
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2b
contar(98)
Impresin10099
procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
98
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2b
contar(98)
Impresin1009998
procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
98
98
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2b
contar(98)
Impresin1009998
procedure contar(n: integer);
begin
if n < 100 then
begin
contar(n+1);
end
WriteLn(n);
end
98
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
EJERCICIO 2b
contar(98)
Impresin1009998
AlgoritmosRecursivos
Vs
AlgoritmosIterativos
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
Hacer un procedimiento iterativo equivalente al ejercicio 2.
EJERCICIO 3
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
Hacer un procedimiento iterativo equivalente al ejercicio 2.
EJERCICIO 3
Recursivoprocedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
contar(n+1);
end
Iterativoprocedure contar(n: integer);
begin
do
WriteLn(n); n := n + 1;
until n >= 100
end
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
Hacer un procedimiento iterativo equivalente al ejercicio 2.
EJERCICIO 3
Iterativoprocedure contar(n: integer);
begin
do
WriteLn(n); n := n + 1;
until n >= 100
end
1. Llamada recursiva / bucle
3. Acercamiento a la condicin de corte
2. Condicin de corte
Recursivoprocedure contar(n: integer);
begin
WriteLn(n);
if n < 100 then
contar(n+1);
end
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
OBSERVACIONES
Recursin lineal
- Una sola llamada recursiva.
- Puede ser reemplazada por un bucle while fcilmente. - Sirve para recorrer estructuras lineales como arrays o listas.
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
OBSERVACIONES: Utilidad de la recursin
Recursin binaria
- 2 llamadas recursivas dentro de cada bloque.
No se puede reemplazar porun bucle while fcilmente
Sirve para recorrer estructuras derboles y grafos
Problemas de naturalezarecursiva
UTN FRLP Concurso Sistemas Operativos 2014 - Ing. Julin Perelli
/
Recapitulacin
Recursin:Usos comunesDefinicinDefinicin + utilidadBacktrackingRecursin vs whileObservaciones finales: utilidad
Top Related