PDF de programación - Recursión - Introducción a la Programación II

Intro

oducción a la Program

mación II

R
Recurs

sión

to
Concep
nición
Defin
C
Casos recursi
Definicion
Estructura
o – Factor
o de ejecu
o de ejecu
o Iteración
para Iterac

Ejemplo
Ejemplo
Ejemplo
Cuando
Reglas p

vos
nes por inducci
as recursivas
rial
ución – Fac
ución – Im
n y cuando
ción y Rec

ión

ctorial(3)
tos de List
mprimir dat
ta
ón
o Recursió
cursión

 

 

Intro

oducción a

la Program

mación II

 

 

C
 Concep
Definición:
:
D

pto de

Recur

rsión

Repetición
R
o
función
d
directa o in

n por autor
se invoca
ndirecta)

un proced
ede ser en

dimiento
n forma

referencia,
a a si mis

, cuando u
smo. (Pue

E
Es la form
en
n su propi
e
sta forma
si
imple que

ma en la cu
ia definici
en algún
e puede res

ual se esp
ión pero c
momento
solverse fá

n proceso
pecifica un
r compleji
con menor
se llega a
a un proce
.
fácilmente

basado
idad, de
eso muy

 

Intro

oducción a

la Program

mación II

 

 

C
 Concep

pto de

Recur

rsión

E
Ejemplos:

- Definici
1

iones por

inducción
n:

E
El cero per
N
Naturales N

rtenece a l
N+1 tamb

los Natura
bién.

ales, y si N

N pertenec

ce a los

2
– Estruct

turas recur

rsivas:

E
El nulo (nil
u
na Lista ta

l) es una L
ambién es

emás un N
Lista y ade
s una Lista
a.

Nodo segu

uido de

 

Intro

oducción a

la Program

mación II

 

 

 

Ejemp

plo - F

Factor

rial

Definición

n por indu

ucción:

F
Factorial
F
Factorial

(0) = 1
(N) = N *

Factorial

l (N-1) p

para todo N > 0

 

Intro

oducción a

la Program

mación II

 

 

 

plo - F

Factor

rial

 Ejemp
Definición
n :
F
Factorial
(0) = 1
F
Factorial
(N) = N *

* Factoria

l (N-1) p

para todo

N > 0

ativa:
ter( N: Int) :Int;
ger;

en begin

1) do begin

c * N;

Solución Itera
function FactIt
Var Fac : Integ
Begin
Fac := 1;
if ( N > 0 ) the
Fac := N;
while (N > 1
N := N – 1
Fac := Fac
end;
end;
FactIter:=Fac
c;
end;

Recursiva:
actorial( N: Int) :

:Int;

Solución R
function Fa
begin
if ( N = 0 )
Factorial
else
Factorial

end;

) then
l := 1

l:=N*Factorial(N

N-1);

 

Intro

oducción a

la Program

mación II

 

 

 

E
Ejemp

plo: Fa

actoria

al(3)

 

al( 2 );

n Factorial( 3 );

0 ) then
orial := 1

orial := 3 * Factori

function
begin
if ( 3 =
Facto
else
Facto

end;

ion Factorial( 2 );
functi
n
begin
2 = 0 ) then
if ( 2
Fac
ctorial := 1
e
else
Fac
ctorial := 2 * Facto

end;

orial( 1 );

funct
tion Factorial(
n
begin
if (
N = 0 ) then
Fa
actorial := 1
else
e
Fa
actorial:=N*Fa
end;

( N: Int) :Int;

actorial(N-1);

);

ction Factorial( 1
fun
beg
gin
( 1 = 0 ) then
if
F
Factorial := 1
els
se
F
Factorial := 1 * Fa
end
d;

ctorial( 0 );

0 );

fu
unction Factorial(
b
begin
if ( 0 = 0 ) then
Factorial := 1
else
Factorial := 0 * F

e
end;

Factorial( -1 );

E
Ejemp

plo: Fa

actoria

al(3)

tion Factorial(
funct
n
begin
N = 0 ) then
if (
Fa
actorial := 1
else
e
Fa
actorial:=N*Fa
end;

( N: Int) :Int;

actorial(N-1);

n Factorial( 3 );

0 ) then
orial := 1

orial := 3 * Factori

function
begin
if ( 3 =
Facto
else
Facto

end;

6

al( 2 );

functi
ion Factorial( 2 );
n
begin
2 = 0 ) then
if ( 2
Fac
ctorial := 1
else
e
ctorial := 2 * Facto
Fac

end;

orial( 1 );

2

);

ction Factorial( 1
fun
beg
gin
( 1 = 0 ) then
if
F
Factorial := 1
els
se
F
Factorial := 1 * Fa
end
d;

ctorial( 0 );

1
1

0 );

fu
unction Factorial(
b
begin
if ( 0 = 0 ) then
Factorial := 1
else
Factorial := 0 * F

e
end;

Factorial( -1 );

1

 

Intro

oducción a la Program

mación II

 

 

E
 Ejemp

plo: Fa

actoria

al(3)

Factorial( N: I

Int) :Int;

0 ) then
ial := 1

function F
begin
if ( N = 0
Factori
else
Factori

end;

ial:=N*Factor

rial(N-1);

Facto

orial(3

3) 6
6

 

Intro

oducción a

la Program

mación II

 

 

 : Reco

orrer l

ista co

on recu

ursión
n

Eje

emplo

Memoria

ListaSimple

7

18

N
Nil

13

atos Orden
nados
sta);
Lista(P:PuntLis

M
Mostrar Da
Pr
rocedure ImpL
egin
be
if (P <> nil) th
writeln(P^.D
ImpLista(P

hen begin
Dato);
P^.Sig);

end;
en
nd;

M
Mostrar D
P
Procedure Imp
b
begin

Datos Inve
pListaInv(P:Pun

ertidos
ntLista);

if (P <> nil)
ImpListaI
writeln(P^

then begin
Inv(P^.Sig);
^.Dato);

end;

end;

 

Intro

oducción a

la Program

mación II

Ej
jempl

 lo: Re

ecorre

er lista

a inve

ertida

Memoria

os Invertid
(P:PLista);

dos

Lis

staSimple

7

18

Nil

13

18
13
7

 

 

Mos
strar Dato
edure ImpInv(
Proce
n
begin
if (
(P <> nil) then
Procedu
ImpInv(P^.Sig
I
begin
writeln(P^.Da
w
if (P <
end
d;
Imp
wri
end;

end;

end;

:PLista);

n begin
ure ImpInv(P:
g);
ato);
egin
<> nil) then be
Procedure
pInv(P^.Sig);
ImpInv(P:PL
begin
iteln(P^.Dato)
);
if (P <>
n
nil) then begin
Procedure Im
mpInv(P:PList
nv(P^.Sig);
ImpIn
begin
writel
ln(P^.Dato);

Lista);

ta);

end;

end;

if (P <> nil
ImpInv(
writeln(P

l) then begin
(P^.Sig);
P^.Dato);

end;

end;

 

Intro

oducción a

la Program

mación II

 

 

C
 Cuándo

o usar

Recur

rsión

Usa

ar Recurs

sión cuan

ndo:

L
La estruct
r
resulta má
La estruct
L

tura de la f
función es
o.
ás sencillo
atos es recu
tura de da

ursiva.

s recurren

nte y el alg

goritmo

NO

O Usar Re

ecursión c

cuando:

Hay dificu
H
Produce d
P
e
ejecución.

ultad en la
demandas

a compren
excesivas

sión del a
s de memo

algoritmo.
oria o tiem

mpo de

 

Intro

oducción a

la Program

mación II

1.

2.

 

 

C
Caract
Hay una
(Por este
Si no se
(Por este

terístic
a condición
e camino N
da el cort
e camino S

cas a t
n de corte
NO se inv
te, la próx
SI se invo

tener e
e con asign
voca a la m
xima vez e
ca a la fun

en cue
nación de
misma fun
staré más
nción)

enta
resultado
nción)
cerca.

.

Iteración:

Recursión
n:

ter( N: Int) :Int;
ger;

en begin

1) do begin

c * N;

function FactIt
Var Fac : Integ
Begin
Fac := 1;
if ( N > 0 ) the
Fac := N;
while (N > 1
N := N – 1
Fac := Fac
end;
end;
FactIter:=Fac
c;
end;

Factorial( N: In

t) :Int;

function F
begin
if ( N = 0
Factoria
else
Factoria

end;

) then
al := 1

al:=N*Factoria

l(N-1);