Recursividade em Estrutura de Dados

Prévia do material em texto

Estrutura	
  de	
  Dados	
  
Recursividade	
  
Prof.	
  Jorge	
  Luiz	
  Chiara	
  
	
  
Recursividade:	
  	
  Definição:	
  	
  Dizemos	
  que	
  um	
  objeto	
  e	
  	
  recursivo	
  se	
  ele	
  estiver	
  definido	
  em	
  termos	
  de	
  si	
  mesmo.	
  Em	
  termos	
  computacionais,	
  um	
  procedimento	
  ou	
  função	
  é	
  recursiva	
  se	
  faz	
  uma	
  “chamada	
  “	
  de	
  sim	
  mesma.	
  A	
  definição	
  	
  de	
  objetos	
  recursivos	
  	
  é	
  comum	
  na	
  matemática.	
  	
  Um	
  exemplo	
  bastante	
  conhecido	
  é	
  	
  o	
  do	
  fatorial	
  de	
  um	
  número,	
  definido	
  da	
  seguinte	
  forma:	
  	
  
fatorial(n)= 1, sen = 0n* fatorial(n−1), sen > 0
"
#
$
	
  	
  assim,	
  	
  	
   0!	
  =	
  1	
  2!	
  =	
  2*1!	
  5!	
  =	
  5*4!	
  6!	
  =	
  6*5!	
  ................	
  n!	
  =	
  n*(n-­‐1)!	
  	
  Computacionalmente,	
  temos	
  a	
  função	
  recursiva	
  correspondente,	
  escrita	
  em	
  java/C/C++	
  	
  	
  	
  	
  	
  	
  	
  	
  Podemos	
   escrever	
   a	
   mesma	
   função	
   utilizando	
   uma	
   estrutura	
   de	
   repetição	
   que	
   calculará	
   o	
  fatorial	
  de	
  um	
  número	
  de	
  forma	
  iterativa.	
  Por	
  exemplo,	
  5!=1.2.3.4.5,	
  ou	
  seja:	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  Um	
  teste	
  de	
  mesa	
  para	
  ambas	
  as	
  funções,	
  vamos	
  calcular	
  o	
  fatorial	
  de	
  5:	
  	
   faltorial(5)	
  	
  recursivamente	
   Resultados	
   Fatorial(5)	
  iterativamente	
  fatorial(5)=5*fatorial(4)	
  fatorial(4)=4*fatorial(3)	
  fatorial(3)=3*fatorial(2)	
  fatorial(2)=2*fatorial(1)	
  fatorial(1)=1*fatorial(0)	
  fatorial(0)	
  
120	
  24	
  6	
  2	
  1	
  1	
  
i	
  	
  	
  	
  f	
  	
  	
  	
  f=f*i	
  1	
  	
  	
  1	
  	
  	
  	
  	
  1	
  2	
  	
  	
  	
  1	
  	
  	
  	
  	
  2	
  3	
  	
  	
  	
  2	
  	
  	
  	
  	
  6	
  4	
  	
  	
  	
  6	
  	
  	
  	
  	
  24	
  5	
  	
  	
  	
  24	
  	
  	
  120	
  
int	
  fatorial(int	
  n){	
  if(n	
  ==	
  0)	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  return	
  1;	
  else	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  return	
  n	
  *	
  fatorial(n	
  -­‐	
  1);	
  }	
  
int	
  fatorial(int	
  n){	
  	
   int	
  f	
  =	
  1;	
  	
   if(n	
  !=	
  0)	
  	
   	
   for(int	
  i;	
  i	
  <=	
  n;	
  i++)	
  	
   	
   	
   f	
  =	
  f	
  *	
  i;	
  	
   return	
  f;	
  }	
  	
  
Observação:	
  o	
  teste	
  de	
  mesa	
  para	
  uma	
  função	
  ou	
  procedimento	
  recursivo	
  é	
  chamado	
  de	
  pilha	
  de	
  recursão.	
  	
  	
  Exemplo	
   2:	
   A	
   Série	
   d	
   Fibonacci	
   (1,	
   1,	
   2,	
   3,	
   5,	
   8,	
   13,	
   21,	
   34,...)	
   é	
   representada	
   pelo	
   seguinte	
  modelo	
  matemático:	
  	
  
fib(n)= 1, sen ≤2fib(n−1)+ fib(n− 2), sen> 2
#
$
%
	
  Como	
  exercício,	
  construa	
  a	
  função	
  computacional	
  e,	
  em	
  seguida,	
  calcule	
  fib(6).	
  	
  Exercícios:	
  para	
  cada	
  caso,	
  abaixo,	
  construa	
  a	
   função	
  recursiva	
  e	
  o	
  teste	
  de	
  mesa	
  através	
  da	
  pilha	
  de	
  recursão	
  para	
  os	
  seguintes	
  modelos	
  matemáticos:	
  	
  Ex.	
  1:	
  Calcule	
  o	
  mdc(64,14)	
  	
  
f (x, y)=
x, se x = y
f (y, x) se x < y
f (x − y, y) se x > y
"
#
$
%
$
	
  
	
  	
  Ex.	
  2:	
  
s(m,n) = m, sen =ms(m,n−1)+ n, sem < n
"
#
$
	
  	
  Calcule	
  s(10,	
  15)	
  	
  Ex.	
  3:	
  
s2(m,n) m, sen =mm+ s2(m+1,n), se m < n
!
"
#
	
  	
  	
  Calcule	
  s2(10,15)	
  Calcule	
  s2(1,10)	
  	
  Ex.	
  4:	
  	
  
dig(n) = 1, se n ≤ 91+ dig(n /10, se n > 9
"
#
$
%$
	
  	
  Calcule	
  dig(532)	
  Calcule	
  dig(101)	
  
Ex.	
  5:	
  	
  
pot(x,n) =
1, sen = 0
1/ pot(x,abs(n), se n < 0
x* pot(x,n−1), sen ≥ 0
#
$
%
&
% 	
  	
  	
  Calcule	
  pot(2,5)	
  Calcule	
  pot(3,4)