Modulo_16_-_0_Recursividade_b

Prévia do material em texto

Computação BásicaComputação Básica
ComputaçãoComputação BásicaBásica
DisciplinaDisciplina 116301116301
Prof. Prof. AlexandreAlexandre ZaghettoZaghettoProf. Prof. AlexandreAlexandre ZaghettoZaghetto
zaghetto@gmail.comzaghetto@gmail.com
UniversidadeUniversidade de Brasíliade Brasília
InstitutoInstituto de de CiênciasCiências ExatasExatas
DepartamentoDepartamento de de CiênciaCiência dada ComputaçãoComputação
Computação BásicaComputação Básica
RecursividadeRecursividade
Computação BásicaComputação Básica
•• IntroduçãoIntrodução::
�� ÉÉ umauma dasdas ferramentasferramentas dede programaçãoprogramação maismais
poderosaspoderosas ee menosmenos entendidasentendidas pelopelo principiantesprincipiantes emem
programaçãoprogramação..
�� ComoComo vocêsvocês jájá nãonão sãosão maismais principiantes,principiantes, suponhosuponho
eu,eu, esseesse capítulocapítulo seráserá mamãomamão comcom açúcaraçúcar..
1. Recursividade1. Recursividade
24/11/201124/11/2011 33
eu,eu, esseesse capítulocapítulo seráserá mamãomamão comcom açúcaraçúcar..
•• ProcessosProcessos ee DefiniçõesDefinições RecursivasRecursivas ::
�� NaNa matemáticasmatemáticas algumasalgumas definiçõesdefinições sãosão
especificadasespecificadas porpor umum processoprocesso.. ExEx.:.: ππ,, definidodefinido comocomo
aa razãorazão entreentre aa circunferênciacircunferência dede umum círculocírculo ee seuseu
diâmetrodiâmetro..
Computação BásicaComputação Básica
•• ApósApós termostermos trabalhandotrabalhando comcom funções,funções, algunsalguns devemdevem
terter sese perguntadoperguntado::
Uma função pode chamar ela mesma?
1. Recursividade1. Recursividade
24/11/201124/11/2011 44
• AA respostaresposta éé sim,sim, ee estaesta técnicatécnica sese chamachama
RECURSIVIDADERECURSIVIDADE..
•• AlgumasAlgumas vezesvezes elaela facilitafacilita aa interpretaçãointerpretação dede certoscertos
problemasproblemas::
Computação BásicaComputação Básica
Quando parar de chamar a função?
• A questão é:
1. Recursividade1. Recursividade
24/11/201124/11/2011 55
• Teoricamente, se você não fizer isto, você entrará num
laço infinito.
Computação BásicaComputação Básica
• Exemplo:
#include <stdio.h>
#include <stdlib.h>
int loop(int);
int main(int argc, char *argv[])
{
int n;
1. Recursividade1. Recursividade
24/11/201124/11/2011 66
n = loop(5);
system("PAUSE");
return 0;
}
int loop(int x){
if(x < 10)
return loop(x);
}
Computação BásicaComputação Básica
1. Recursividade1. Recursividade
Problema: Escreva uma função que recebe como parâmetro um inteiro
positivo N e retorna a soma de todos os números inteiros entre 0 e N.
• Solução iterativa:
int somatorio(int N)
{
24/11/201124/11/2011 77
{
int i, resp = 0;
for( i = 1; i <= N; i++ )
resp += i;
return resp;
}
Computação BásicaComputação Básica
1. Recursividade1. Recursividade
Problema: Escreva uma função que recebe como parâmetro um inteiro
positivo N e retorna a soma de todos os números inteiros entre 0 e N.
• Solução recursiva:
int somatorio(int N)
{
24/11/201124/11/2011 88
{
if( N == 1 )
return 1;
else
return N + somatorio(N – 1);
}
• RequerRequer aa repetiçãorepetição explícitaexplícita dede umum processoprocesso atéaté queque
determinadadeterminada condiçãocondição sejaseja satisfeitasatisfeita..
Computação BásicaComputação Básica
•• AA funçãofunção fatorialfatorial::
�� ÉÉ umum outrooutro exemploexemplo dede umauma definiçãodefinição especificadaespecificada
pelapela repetiçãorepetição dede umum processoprocesso..
1. Recursividade1. Recursividade
1 0
! ( 1) ( 2) ... 1 0
se n
n
n n n se n
=
= 
⋅ − ⋅ − ⋅ ⋅ >
24/11/201124/11/2011 99
�� ExemplosExemplos..
( 1) ( 2) ... 1 0n n n se n ⋅ − ⋅ − ⋅ ⋅ >
0! 1
1! 1
2! 2 1 2
3! 3 2 1 6
=
=
= ⋅ =
= ⋅ ⋅ =
Computação BásicaComputação Básica
• A funçãofunção fatorial:
� De forma iterativa:
� De forma recursiva:
1. Recursividade1. Recursividade
fatorial (n) = 1 * 2 * 3 .... n
24/11/201124/11/2011 1010
� De forma recursiva:
fatorial (n) = n * fatorial (n – 1), 
sendo fatorial (0) = 1
Computação BásicaComputação Básica
• Solução:
� De forma iterativa:
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
1. Recursividade1. Recursividade
24/11/201124/11/2011 1111
{
int n, i, fat = 1;
printf("Digite n:");
scanf("%d", &n);
for(i = 1; i<=n;i++) fat = fat*i;
printf("%d \n", fat);
system("PAUSE");
return 0;
}
Computação BásicaComputação Básica
• Solução:
� De forma recursiva:
#include <stdio.h>
#include <stdlib.h>
int fatorial (int);
1. Recursividade1. Recursividade
24/11/201124/11/2011 1212
int main(int argc, char *argv[])
{
int n, fat;
printf("Digite n:");
scanf("%d", &n);
fat = fatorial(n);
Computação BásicaComputação Básica
• Solução:
� De forma recursiva:
printf("%d \n", fat);
system("PAUSE");
1. Recursividade1. Recursividade
24/11/201124/11/2011 1313
system("PAUSE");
return 0;
}
int fatorial (int n){
if(n==0)
return 1;
else
return n*fatorial(n-1);
}
Computação BásicaComputação Básica
• Exemplo - fatorial(3):
int fatorial (int n){
if(n==0)
return 1;
else
return n*fatorial(n-1);
}
1. Recursividade1. Recursividade
24/11/201124/11/2011 1414
N = fatorial(3);
Computação BásicaComputação Básica
• Exemplo - fatorial(3):
int fatorial (int n){
if(n==0)
return 1;
else
return n*fatorial(n-1);
}
1. Recursividade1. Recursividade
24/11/201124/11/2011 1515
N = fatorial(3);
return 3*fatorial(3-1);
Computação BásicaComputação Básica
• Exemplo - fatorial(3):
int fatorial (int n){
if(n==0)
return 1;
else
return n*fatorial(n-1);
}
1. Recursividade1. Recursividade
24/11/201124/11/2011 1616
N = fatorial(3);
return 3*fatorial(3-1);
[fatorial(2)];
Computação BásicaComputação Básica
• Exemplo - fatorial(3):
int fatorial (int n){
if(n==0)
return 1;
else
return n*fatorial(n-1);
}
1. Recursividade1. Recursividade
24/11/201124/11/2011 1717
N = fatorial(3);
return 3*fatorial(3-1);
[fatorial(2)];
return 2*fatorial(2-1);
Computação BásicaComputação Básica
• Exemplo - fatorial(3):
int fatorial (int n){
if(n==0)
return 1;
else
return n*fatorial(n-1);
}
1. Recursividade1. Recursividade
24/11/201124/11/2011 1818
N = fatorial(3);
return 3*fatorial(3-1);
[fatorial(2)];
return 2*fatorial(2-1);
[fatorial(1)];
Computação BásicaComputação Básica
• Exemplo - fatorial(3):
int fatorial (int n){
if(n==0)
return 1;
else
return n*fatorial(n-1);
}
1. Recursividade1. Recursividade
24/11/201124/11/2011 1919
N = fatorial(3);
return 3*fatorial(3-1);
[fatorial(2)];
return 2*fatorial(2-1);
[fatorial(1)];
return 1*fatorial(1-1);
Computação BásicaComputação Básica
• Exemplo - fatorial(3):
int fatorial (int n){
if(n==0)
return 1;
else
return n*fatorial(n-1);
}
1. Recursividade1. Recursividade
24/11/201124/11/2011 2020
N = fatorial(3);
return 3*fatorial(3-1);
[fatorial(2)];
return 2*fatorial(2-1);
[fatorial(1)];
return 1*fatorial(1-1);
[fatorial(0)]
Computação BásicaComputação Básica
• Exemplo - fatorial(3):
int fatorial (int n){
if(n==0)
return 1;
else
return n*fatorial(n-1);
}
1. Recursividade1. Recursividade
24/11/201124/11/2011 2121
N = fatorial(3);
return 3*fatorial(3-1);
[fatorial(2)];
return 2*fatorial(2-1);
[fatorial(1)];
return 1*fatorial(1-1);
[fatorial(0)]
return 1;
Computação BásicaComputação Básica
• Exemplo - fatorial(3):
int fatorial (int n){
if(n==0)
return1;
else
return n*fatorial(n-1);
}
1. Recursividade1. Recursividade
24/11/201124/11/2011 2222
N = fatorial(3);
return 3*fatorial(3-1);
[fatorial(2)];
return 2*fatorial(2-1);
[fatorial(1)];
return 1*fatorial(1-1);
return 1;
Computação BásicaComputação Básica
• Exemplo - fatorial(3):
int fatorial (int n){
if(n==0)
return 1;
else
return n*fatorial(n-1);
}
1. Recursividade1. Recursividade
24/11/201124/11/2011 2323
N = fatorial(3);
return 3*fatorial(3-1);
[fatorial(2)];
return 2*fatorial(2-1);
[fatorial(1)];
return 1*1;
Computação BásicaComputação Básica
• Exemplo - fatorial(3):
int fatorial (int n){
if(n==0)
return 1;
else
return n*fatorial(n-1);
}
1. Recursividade1. Recursividade
24/11/201124/11/2011 2424
N = fatorial(3);
return 3*fatorial(3-1);
[fatorial(2)];
return 2*fatorial(2-1);
[fatorial(1)];
return 1;
Computação BásicaComputação Básica
• Exemplo - fatorial(3):
int fatorial (int n){
if(n==0)
return 1;
else
return n*fatorial(n-1);
}
1. Recursividade1. Recursividade
24/11/201124/11/2011 2525
N = fatorial(3);
return 3*fatorial(3-1);
[fatorial(2)];
return 2*fatorial(2-1);
return 1;
Computação BásicaComputação Básica
• Exemplo - fatorial(3):
int fatorial (int n){
if(n==0)
return 1;
else
return n*fatorial(n-1);
}
1. Recursividade1. Recursividade
24/11/201124/11/2011 2626
N = fatorial(3);
return 3*fatorial(3-1);
[fatorial(2)];
return 2*1;
Computação BásicaComputação Básica
• Exemplo - fatorial(3):
int fatorial (int n){
if(n==0)
return 1;
else
return n*fatorial(n-1);
}
1. Recursividade1. Recursividade
24/11/201124/11/2011 2727
N = fatorial(3);
return 3*fatorial(3-1);
[fatorial(2)];
return 2;
Computação BásicaComputação Básica
• Exemplo - fatorial(3):
int fatorial (int n){
if(n==0)
return 1;
else
return n*fatorial(n-1);
}
1. Recursividade1. Recursividade
24/11/201124/11/2011 2828
N = fatorial(3);
return 3*fatorial(3-1);
return 2;
Computação BásicaComputação Básica
• Exemplo - fatorial(3):
int fatorial (int n){
if(n==0)
return 1;
else
return n*fatorial(n-1);
}
1. Recursividade1. Recursividade
24/11/201124/11/2011 2929
N = fatorial(3);
return 3*2;
Computação BásicaComputação Básica
• Exemplo - fatorial(3):
int fatorial (int n){
if(n==0)
return 1;
else
return n*fatorial(n-1);
}
1. Recursividade1. Recursividade
24/11/201124/11/2011 3030
N = fatorial(3);
return 6;
Computação BásicaComputação Básica
• Exemplo - fatorial(3):
int fatorial (int n){
if(n==0)
return 1;
else
return n*fatorial(n-1);
}
1. Recursividade1. Recursividade
24/11/201124/11/2011 3131
N = 6;
Computação BásicaComputação Básica
• Exemplo - fatorial(5):
fatorial(N) = N*fatorial(N-1);
fatorial(0) = 1;
fatorial(5) = 5*fatorial(5-1) = 5*fatorial(4); Equ. 1
fatorial(4) = 4*fatorial(4-1) = 4*fatorial(3); Equ. 2 
fatorial(3) = 3*fatorial(3-1) = 3*fatorial(2); Equ. 3
fatorial(2) = 2*fatorial(2-1) = 2*fatorial(1); Equ. 4
1. Recursividade1. Recursividade
24/11/201124/11/2011 3232
fatorial(2) = 2*fatorial(2-1) = 2*fatorial(1); Equ. 4
fatorial(1) = 1*fatorial(1-1) = 1*fatorial(0); Equ. 5
fatorial(0) = 1; Equ. 6
Subst. a Equ. 6 na Equ. 5 temos: fatorial(1) = 1*1
Subst. a Equ. 5 na Equ. 4 temos: fatorial(2) = 2*1
Subst. a Equ. 4 na Equ. 3 temos: fatorial(3) = 3*2
Subst. a Equ. 3 na Equ. 2 temos: fatorial(4) = 4*6
Subst. a Equ. 2 na Equ. 1 temos: fatorial(5) = 5*24
E assim: fatorial(5) = 120.
Computação BásicaComputação Básica
1. Recursividade1. Recursividade
•• EscrevendoEscrevendo programasprogramas recursivosrecursivos::
�� AntesAntes dede tudo,tudo, podemospodemos reconhecerreconhecer umum grandegrande
númeronúmero dede casoscasos aa solucionarsolucionar:: 00!,!, 11!,!, 22!,!, 33!,!, 44!! etcetc..
�� PodemosPodemos tambémtambém identificaridentificar umum casocaso “trivial”,“trivial”, nãonão--
recursivo,recursivo, diretamentediretamente solucionávelsolucionável:: 00!=!=11..
24/11/201124/11/2011 3333
�� EncontramosEncontramos umum métodométodo parapara solucionarsolucionar umum casocaso
“complexo”“complexo” emem termostermos dede umum casocaso “mais“mais simples”simples”::
n!n! == n*(nn*(n--11)!)!
�� AA transformaçãotransformação dodo casocaso maismais complexocomplexo nono casocaso
maismais simplessimples devedeve ocasionalmenteocasionalmente resultarresultar numnum casocaso
“trivial”“trivial”..
Computação BásicaComputação Básica
• Fibonacci e razão áurea:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 
1. Recursividade1. Recursividade
24/11/201124/11/2011 3434
• Razão Áurea:
55/34 ≈ 1,61765
Computação BásicaComputação Básica
• Fibonacci e razão áurea:
1. Recursividade1. Recursividade
24/11/201124/11/2011 3535
Computação BásicaComputação Básica
• Fibonacci e razão áurea:
1. Recursividade1. Recursividade
24/11/201124/11/2011 3636
Computação BásicaComputação Básica
• Fibonacci e razão áurea:
1. Recursividade1. Recursividade
24/11/201124/11/2011 3737
Computação BásicaComputação Básica
• Fibonacci e razão áurea:
1. Recursividade1. Recursividade
24/11/201124/11/2011 3838
Computação BásicaComputação Básica
• Fibonacci e razão áurea:
1. Recursividade1. Recursividade
24/11/201124/11/2011
Computação BásicaComputação Básica
• Fibonacci e razão áurea:
� Mais em “Donald no País da Matemágica”.
1. Recursividade1. Recursividade
24/11/201124/11/2011 4040
http://www.youtube.com/watch?v=hWLAtn3KVw8
Computação BásicaComputação Básica
• Fibonacci:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 
1. Recursividade1. Recursividade
24/11/201124/11/2011 4141
Para casa, implementar
a solução recursiva em C.
Computação BásicaComputação Básica
• MultiplicaçãoMultiplicação dede númerosnúmeros naturaisnaturais::
�� AA multiplicaçãomultiplicação dede a*ba*b podepode serser vistavista aa somasoma dede a,a,
bb vezes,vezes, ouou sejaseja::
1. Recursividade1. Recursividade
 1
( 1) 1
a se b
a b
a b a se b
=
⋅ = 
⋅ − + >
24/11/201124/11/2011 4242
�� 66**33 == 66*(*(33--11)+)+66
== 66**22++66
== 66*(*(22--11)+)+66++66
== 66**11++66++66
== 66++66++66
==1818
( 1) 1a b a b a se b⋅ =  ⋅ − + >
Computação BásicaComputação Básica
• MultiplicaçãoMultiplicação dede númerosnúmeros naturaisnaturais::
�� AA multiplicaçãomultiplicação dede a*ba*b podepode serser vistavista aa somasoma dede a,a,
bb vezes,vezes, ouou sejaseja::
1. Recursividade1. Recursividade
 1
( 1) 1
a se b
a b
a b a se b
=
⋅ = 
⋅ − + >
24/11/201124/11/2011 4343
�� 66**33 == 66*(*(33--11)+)+66
== 66**22++66
== 66*(*(22--11)+)+66++66
== 66**11++66++66
== 66++66++66
==1818
( 1) 1a b a b a se b⋅ =  ⋅ − + >
Para casa, implementar
a solução recursiva em C.
Computação BásicaComputação Básica
1. Recursividade1. Recursividade
Exercício: O quadrado de um número natural n é dado pela soma dos n
primeiros números ímpares consecutivos. Por exemplo, 12=1, 22=1+3,
32=1+3+5, 42=1+3+5+7, etc. Dado um número n, escreva uma função
recursiva que calcula seu quadrado usando a soma de ímpares.
24/11/201124/11/2011 4444
Computação BásicaComputação Básica
1. Recursividade1. Recursividade
Exercício: O quadrado de um número natural n é dado pela soma dos n
primeiros números ímpares consecutivos. Por exemplo, 12=1, 22=1+3,
32=1+3+5, 42=1+3+5+7, etc. Dado um número n, escreva uma função
recursiva que calcula seu quadrado usando a soma de ímpares.
• 52 = 1+3+5+7+9 = 25
24/11/201124/11/20114545
Computação BásicaComputação Básica
1. Recursividade1. Recursividade
Exercício: O quadrado de um número natural n é dado pela soma dos n
primeiros números ímpares consecutivos. Por exemplo, 12=1, 22=1+3,
32=1+3+5, 42=1+3+5+7, etc. Dado um número n, escreva uma função
recursiva que calcula seu quadrado usando a soma de ímpares.
• 52 = 1+3+5+7+9 = 25
24/11/201124/11/2011 4646
• 52 = 1+3+5+7+9
42
Computação BásicaComputação Básica
1. Recursividade1. Recursividade
Exercício: O quadrado de um número natural n é dado pela soma dos n
primeiros números ímpares consecutivos. Por exemplo, 12=1, 22=1+3,
32=1+3+5, 42=1+3+5+7, etc. Dado um número n, escreva uma função
recursiva que calcula seu quadrado usando a soma de ímpares.
• 52 = 1+3+5+7+9 = 25
24/11/201124/11/2011 4747
• 52 = 1+3+5+7+9
42
• 42 = 1+3+5+7
32
Computação BásicaComputação Básica
1. Recursividade1. Recursividade
Exercício: O quadrado de um número natural n é dado pela soma dos n
primeiros números ímpares consecutivos. Por exemplo, 12=1, 22=1+3,
32=1+3+5, 42=1+3+5+7, etc. Dado um número n, escreva uma função
recursiva que calcula seu quadrado usando a soma de ímpares.
• 52 = 1+3+5+7+9 = 25
24/11/201124/11/2011 4848
• 52 = 1+3+5+7+9
42
• 42 = 1+3+5+7
32
• 32 = 1+3+5
22
Computação BásicaComputação Básica
1. Recursividade1. Recursividade
Exercício: O quadrado de um número natural n é dado pela soma dos n
primeiros números ímpares consecutivos. Por exemplo, 12=1, 22=1+3,
32=1+3+5, 42=1+3+5+7, etc. Dado um número n, escreva uma função
recursiva que calcula seu quadrado usando a soma de ímpares.
• 52 = 1+3+5+7+9 = 25
24/11/201124/11/2011 4949
• 52 = 1+3+5+7+9
42
• 42 = 1+3+5+7
32
• 32 = 1+3+5
22
• 22 = 1+3
12
Computação BásicaComputação Básica
1. Recursividade1. Recursividade
Exercício: O quadrado de um número natural n é dado pela soma dos n
primeiros números ímpares consecutivos. Por exemplo, 12=1, 22=1+3,
32=1+3+5, 42=1+3+5+7, etc. Dado um número n, escreva uma função
recursiva que calcula seu quadrado usando a soma de ímpares.
• 52 = 1+3+5+7+9 = 25
24/11/201124/11/2011 5050
• 52 = 1+3+5+7+9
42
• 42 = 1+3+5+7
32
• 32 = 1+3+5
22
• 22 = 1+3
12
• 12 = 1
Computação BásicaComputação Básica
1. Recursividade1. Recursividade
Exercício: O quadrado de um número natural n é dado pela soma dos n
primeiros números ímpares consecutivos. Por exemplo, 12=1, 22=1+3,
32=1+3+5, 42=1+3+5+7, etc. Dado um número n, escreva uma função
recursiva que calcula seu quadrado usando a soma de ímpares.
• 52 = 1+3+5+7+9 = 25
24/11/201124/11/2011 5151
• 52 = 1+3+5+7+9
42
• 42 = 1+3+5+7 n2 = (2*n-1) + (n-1)2
32
• 32 = 1+3+5
22
• 22 = 1+3
12
• 12 = 1
Computação BásicaComputação Básica
• Solução:
#include <stdio.h>
#include <stdlib.h>
int quadrado (int);
int main (int argc, char *argv[])
{
int n = 6, result;
1. Recursividade1. Recursividade
24/11/201124/11/2011 5252
result = quadrado(n);
printf("%d \n", result);
system("PAUSE");
return 0;
}
int quadrado (int n){
if (n==1)
return 1;
else
return (2*n-1) + quadrado(n-1);
}
Computação BásicaComputação Básica
1. Recursividade1. Recursividade
i j k m
3 2 1 0
4 2 1 0
4 3 1 0
4 3 2 0
Exercício: Escrever um programa recursivo que dados n e k, mostra na tela
do computador todas as cominações de n, k a k. Por exemplo, se n = 6 e k
= 4:
24/11/201124/11/2011 5353
4 3 2 0
4 3 2 1
5 2 1 0
5 3 1 0
5 3 2 0
5 3 2 1
5 4 1 0
5 4 2 0
5 4 2 1
5 4 3 0
5 4 3 1
5 4 3 2
Computação BásicaComputação Básica
1. Recursividade1. Recursividade
Exercício: Escrever um programa recursivo que dados n e k, mostra na tela
do computador todas as cominações de n, k a k. Por exemplo, se n = 6 e k
= 4:
i j k m
3 2 1 0
4 2 1 0
4 3 1 0
4 3 2 0
24/11/201124/11/2011 5454
4 3 2 0
4 3 2 1
5 2 1 0
5 3 1 0
5 3 2 0
5 3 2 1
5 4 1 0
5 4 2 0
5 4 2 1
5 4 3 0
5 4 3 1
5 4 3 2
for(i = 3; i<6; i++)
for(j = 2; j<i; j++)
for(k = 1; k<j; k++)
for(m = 0; m<k; m++)
printf(“%d%d%d%d”,i,j,k,m);
Computação BásicaComputação Básica
1. Recursividade1. Recursividade
•• OO problemaproblema dasdas TorresTorres dede HanoiHanoi::
24/11/201124/11/2011 5555
�� OO objetivoobjetivo éé deslocardeslocar osos cincocinco discosdiscos parapara aa estacaestaca
C,C, usandousando BB comocomo auxiliarauxiliar..
�� SomenteSomente oo primeiroprimeiro discodisco podepode serser deslocadodeslocado..
�� UmUm discodisco maiormaior nãonão podepode serser posicionadoposicionado sobresobre umum
menormenor..
Computação BásicaComputação Básica
1. Recursividade1. Recursividade
•• OO problemaproblema dasdas TorresTorres dede HanoiHanoi::
�� ConsiderandoConsiderando oo casocaso geral,geral, parapara nn discosdiscos::
�� SuponhaSuponha queque tivéssemostivéssemos umauma soluçãosolução parapara nn--11
discosdiscos ee pudéssemospudéssemos dardar aa soluçãosolução parapara nn,, emem
funçãofunção dada soluçãosolução parapara nn--11 discosdiscos..
24/11/201124/11/2011 5656
�� NoNo casocaso trivial,trivial, nono qualqual temostemos apenasapenas umum únicoúnico
disco,disco, bastabasta deslocádeslocá--lolo dede AA parapara CC..
Computação BásicaComputação Básica
1. Recursividade1. Recursividade
•• OO problemaproblema dasdas TorresTorres dede HanoiHanoi::
�� SeSe nn == 55::
�� VamosVamos suporsupor queque eueu pudessepudesse movimentarmovimentar osos
quatroquatro primeirosprimeiros discosdiscos dada estacaestaca AA parapara aa estacaestaca
B,B, usandousando CC comocomo auxiliarauxiliar..
24/11/201124/11/2011 5757
Computação BásicaComputação Básica
1. Recursividade1. Recursividade
•• OO problemaproblema dasdas TorresTorres dede HanoiHanoi::
�� SeSe nn == 55::
�� VamosVamos suporsupor queque eueu pudessepudesse movimentarmovimentar osos
quatroquatro primeirosprimeiros discosdiscos dada estacaestaca AA parapara aa estacaestaca
B,B, usandousando CC comocomo auxiliarauxiliar..
24/11/201124/11/2011 5858
Computação BásicaComputação Básica
1. Recursividade1. Recursividade
•• OO problemaproblema dasdas TorresTorres dede HanoiHanoi::
�� SeSe nn == 55::
�� PoderíamosPoderíamos deslocardeslocar oo maiormaior discodisco dede AA parapara CC..
24/11/201124/11/2011 5959
Computação BásicaComputação Básica
1. Recursividade1. Recursividade
•• OO problemaproblema dasdas TorresTorres dede HanoiHanoi::
�� SeSe nn == 55::
�� E,E, porpor último,último, aplicaraplicar novamentenovamente aa soluçãosolução aosaos
quatroquatro discos,discos, movendomovendo--osos dede BB parapara C,C, usandousando AA
comocomo auxiliarauxiliar..
24/11/201124/11/2011 6060
Computação BásicaComputação Básica
1. Recursividade1. Recursividade
•• OO problemaproblema dasdas TorresTorres dede HanoiHanoi::
�� ParaPara movermover nn discosdiscos dede AA parapara C,C, usandousando BB comocomo
auxiliarauxiliar::
1.1. SeSe n=n=11,, desloquedesloque oo únicoúnico discodisco dede AA parapara CC ee
parepare..
24/11/201124/11/2011 6161
2.2. DesloqueDesloque osos nn--11 primeirosprimeiros discosdiscos dede AA parapara B,B,
usandousando CC comocomo auxiliarauxiliar..
3.3. DesloqueDesloque oo últimoúltimo discodisco dede AA parapara CC..
4.4. MovaMova osos nn--11 discosdiscos dede BB parapara C,C, usandousando AA
comocomo auxiliarauxiliar..
Computação BásicaComputação Básica
1. Recursividade1. Recursividade
•• AlgoritmoAlgoritmo dede EuclidesEuclides parapara determinaçãodeterminação dodo MDCMDC::
1.1. SejamSejam aa ee bb doisdois númerosnúmeros inteirosinteiros,, comcom aa>>bb..
22.. DividaDivida aa porpor bb,, encontrandoencontrando umum quocientequociente qq ee umum
restoresto rr (isto(isto é,é, aa== q*b+rq*b+r))..
33.. DefinaDefina aa == bb ee bb == rr..
24/11/201124/11/2011 6262
33.. DefinaDefina aa == bb ee bb == rr..
44.. RepitaRepita osos passospassos 22 ee 33,, atéaté queque bb sejaseja igualigual aa 00..
55.. OO MDCMDC éé igualigual aoao valorvalor armazenadoarmazenado emem aa..
Computação BásicaComputação Básica
•• MDC(MDC(19761976,, 10321032))::
1.1. aa == 19761976 ee bb == 10321032..
22.. DividaDivida aa porpor bb,, encontrandoencontrando umum quocientequociente qq ee umum
restoresto rr (isto(isto é,é, aa == q*b+rq*b+r))..
33.. DefinaDefina aa == bb ee bb == rr..
1. Recursividade1. Recursividade
Passo a b q r
1 1976 1032
2 1976 1032 1 944
3 1032 944
4 e 2 1032 944 1 88
3 944 88
4 e 2 944 88 10 64
3 88 64
24/11/201124/11/2011 6363
33.. DefinaDefina aa == bb ee bb == rr..
44.. RepitaRepita osos passospassos 22 ee 33,, atéaté queque bb sejaseja igualigual aa 00..
55.. MDC(MDC(19761976,, 10321032)) == aa..
3 88 64
4 e 2 88 64 1 24
3 64 24
4 e 2 64 24 2 16
3 24 16
4 e 2 24 16 1 8
3 16 8
4 e 2 16 8 2 0
3 8 0
5 MDC = 8
Computação BásicaComputação Básica
•• MDC(MDC(19761976,, 10321032))::
1.1. aa == 19761976 ee bb == 10321032..
22.. DividaDivida aa porpor bb,, encontrandoencontrando umum quocientequociente qq
ee umum restoresto rr (isto(isto é,é, aa == q*b+rq*b+r))..
33.. DefinaDefina aa == bb ee bb == rr..
1. Recursividade1. Recursividade
Passo a b q r
1 1976 1032
2 1976 1032 1 944
3 1032 944
4 e 2 1032 944 1 88
3 944 88
4 e 2 944 88 10 64
3 88 64
24/11/201124/11/2011 6464
33.. DefinaDefina aa == bb ee bb == rr..
44.. RepitaRepita osos passospassos 22 ee 33,, atéaté queque bb sejaseja igualigual aa 00..
55.. MDC(MDC(19761976,, 10321032)) == aa..
3 88 64
4 e 2 88 64 1 24
3 64 24
4 e 2 64 24 2 16
3 24 16
4 e 2 24 16 1 8
3 16 8
4 e 2 16 8 2 0
3 8 0
5 MDC = 8
Computação BásicaComputação Básica
•• MDC(MDC(19761976,, 10321032))::
1.1. aa == 19761976 ee bb == 10321032..
22.. DividaDivida aa porpor bb,, encontrandoencontrando umum quocientequociente qq ee umum
restoresto rr (isto(isto é,é, aa == q*b+rq*b+r))..
33.. DefinaDefina aa == bb ee bb == rr..
1. Recursividade1. Recursividade
Passo a B q r
1 1976 1032
2 1976 1032 1 944
3 1032 944
4 e 2 1032 944 1 88
3 944 88
4 e 2 944 88 10 64
3 88 64
24/11/201124/11/2011 6565
33.. DefinaDefina aa == bb ee bb == rr..
44.. RepitaRepita osos passospassos 22 ee 33,, atéaté queque bb sejaseja igualigual aa 00..
55.. MDC(MDC(19761976,, 10321032)) == aa..
3 88 64
4 e 2 88 64 1 24
3 64 24
4 e 2 64 24 2 16
3 24 16
4 e 2 24 16 1 8
3 16 8
4 e 2 16 8 2 0
3 8 0
5 MDC = 8
Computação BásicaComputação Básica
•• MDC(MDC(19761976,, 10321032))::
1.1. aa == 19761976 ee bb == 10321032..
22.. DividaDivida aa porpor bb,, encontrandoencontrando umum quocientequociente qq
ee umum restoresto rr (isto(isto é,é, aa == q*b+rq*b+r))..
33.. DefinaDefina aa == bb ee bb == rr..
1. Recursividade1. Recursividade
Passo a b q r
1 1976 1032
2 1976 1032 1 944
3 1032 944
4 e 2 1032 944 1 88
3 944 88
4 e 2 944 88 10 64
3 88 64
24/11/201124/11/2011 6666
33.. DefinaDefina aa == bb ee bb == rr..
44.. RepitaRepita osos passospassos 22 ee 33,, atéaté queque bb sejaseja igualigual aa
00..
55.. MDC(MDC(19761976,, 10321032)) == aa..
3 88 64
4 e 2 88 64 1 24
3 64 24
4 e 2 64 24 2 16
3 24 16
4 e 2 24 16 1 8
3 16 8
4 e 2 16 8 2 0
3 8 0
5 MDC = 8
Computação BásicaComputação Básica
•• MDC(MDC(19761976,, 10321032))::
1.1. aa == 19761976 ee bb == 10321032..
22.. DividaDivida aa porpor bb,, encontrandoencontrando umum quocientequociente qq ee umum
restoresto rr (isto(isto é,é, aa == q*b+rq*b+r))..
33.. DefinaDefina aa == bb ee bb == rr..
1. Recursividade1. Recursividade
Passo a b q r
1 1976 1032
2 1976 1032 1 944
3 1032 944
4 e 2 1032 944 1 88
3 944 88
4 e 2 944 88 10 64
3 88 64
24/11/201124/11/2011 6767
33.. DefinaDefina aa == bb ee bb == rr..
44.. RepitaRepita osos passospassos 22 ee 33,, atéaté queque bb sejaseja igualigual aa 00..
55.. MDC(MDC(19761976,, 10321032)) == aa..
3 88 64
4 e 2 88 64 1 24
3 64 24
4 e 2 64 24 2 16
3 24 16
4 e 2 24 16 1 8
3 16 8
4 e 2 16 8 2 0
3 8 0
5 MDC = 8
Computação BásicaComputação Básica
•• MDC(MDC(19761976,, 10321032))::
1.1. aa == 19761976 ee bb == 10321032..
22.. DividaDivida aa porpor bb,, encontrandoencontrando umum quocientequociente qq
ee umum restoresto rr (isto(isto é,é, aa == q*b+rq*b+r))..
33.. DefinaDefina aa == bb ee bb == rr..
1. Recursividade1. Recursividade
Passo a b q r
1 1976 1032
2 1976 1032 1 944
3 1032 944
4 e 2 1032 944 1 88
3 944 88
4 e 2 944 88 10 64
3 88 64
24/11/201124/11/2011 6868
33.. DefinaDefina aa == bb ee bb == rr..
44.. RepitaRepita osos passospassos 22 ee 33,, atéaté queque bb sejaseja igualigual aa
00..
55.. MDC(MDC(19761976,, 10321032)) == aa..
3 88 64
4 e 2 88 64 1 24
3 64 24
4 e 2 64 24 2 16
3 24 16
4 e 2 24 16 1 8
3 16 8
4 e 2 16 8 2 0
3 8 0
5 MDC = 8
Computação BásicaComputação Básica
•• MDC(MDC(19761976,, 10321032))::
1.1. aa == 19761976 ee bb == 10321032..
22.. DividaDivida aa porpor bb,, encontrandoencontrando umum quocientequociente qq ee umum
restoresto rr (isto(isto é,é, aa == q*b+rq*b+r))..
33.. DefinaDefina aa == bb ee bb == rr..
1. Recursividade1. Recursividade
Passo a b q r
1 1976 1032
2 1976 1032 1 944
3 1032 944
4 e 2 1032 944 1 88
3 944 88
4 e 2 944 88 10 64
3 88 64
24/11/201124/11/2011 6969
33.. DefinaDefina aa == bb ee bb == rr..
44.. RepitaRepita osos passospassos 22 ee 33,, atéaté queque bb sejaseja igualigual aa 00..
55.. MDC(MDC(19761976,, 10321032)) == aa..
3 88 64
4 e 2 88 64 1 24
3 64 24
4 e 2 64 24 2 16
3 24 16
4 e 2 24 16 1 8
3 16 8
4 e 2 16 8 2 0
3 8 0
5 MDC = 8
Computação BásicaComputação Básica
•• MDC(MDC(19761976,, 10321032))::
1.1. aa == 19761976 ee bb == 10321032..
22.. DividaDivida aa porpor bb,, encontrandoencontrando umum quocientequociente qq
ee umum restoresto rr (isto(isto é,é, aa == q*b+rq*b+r))..
33.. DefinaDefina aa == bb ee bb == rr..
1. Recursividade1. Recursividade
Passo a b q r
1 1976 1032
2 1976 1032 1 944
3 1032 944
4 e 2 1032 944 1 88
3 944 88
4 e 2 944 88 10 64
3 88 64
24/11/201124/11/2011 7070
33.. DefinaDefina aa == bb ee bb == rr..
44.. RepitaRepita osos passospassos 22 ee 33,, atéaté queque bb sejaseja igualigual aa
00..
55.. MDC(MDC(19761976,, 10321032)) == aa..
3 88 64
4 e 2 88 64 1 24
3 64 24
4 e 2 64 24 2 16
3 24 16
4 e 2 24 16 1 8
3 16 8
4 e 2 16 8 2 0
3 8 0
5 MDC = 8
Computação BásicaComputação Básica
•• MDC(MDC(19761976,, 10321032))::
1.1. aa == 19761976 ee bb == 10321032..
22.. DividaDivida aa porpor bb,, encontrandoencontrando umum quocientequociente qq ee umum
restoresto rr (isto(isto é,é, aa == q*b+rq*b+r))..
33.. DefinaDefina aa == bb ee bb == rr..
1. Recursividade1. Recursividade
Passo a b q r
1 1976 1032
2 1976 1032 1 944
3 1032 944
4 e 2 1032 944 1 88
3 944 88
4 e 2 944 88 10 64
3 88 64
24/11/201124/11/2011 7171
33.. DefinaDefina aa == bb ee bb == rr..
44.. RepitaRepita osos passospassos 22 ee 33,, atéaté queque bb sejaseja igualigual aa
00..
55.. MDC(MDC(19761976,, 10321032)) == aa..
3 88 64
4 e 2 88 64 1 24
3 64 24
4 e 2 64 24 2 16
3 24 16
4 e 2 24 16 1 8
3 16 8
4 e 2 16 8 2 0
3 8 0
5 MDC = 8
Computação BásicaComputação Básica
•• MDC(MDC(19761976,, 10321032))::
1.1. aa == 19761976 ee bb == 10321032..
22.. DividaDivida aa porpor bb,,encontrandoencontrando umum quocientequociente qq ee umum
restoresto rr (isto(isto é,é, aa == q*b+rq*b+r))..
33.. DefinaDefina aa == bb ee bb == rr..
1. Recursividade1. Recursividade
Passo a b q r
1 1976 1032
2 1976 1032 1 944
3 1032 944
4 e 2 1032 944 1 88
3 944 88
4 e 2 944 88 10 64
3 88 64
24/11/201124/11/2011 7272
33.. DefinaDefina aa == bb ee bb == rr..
44.. RepitaRepita osos passospassos 22 ee 33,, atéaté queque bb sejaseja igualigual aa 00..
55.. MDC(MDC(19761976,, 10321032)) == aa..
3 88 64
4 e 2 88 64 1 24
3 64 24
4 e 2 64 24 2 16
3 24 16
4 e 2 24 16 1 8
3 16 8
4 e 2 16 8 2 0
3 8 0
5 MDC = 8
Computação BásicaComputação Básica
•• MDC(MDC(19761976,, 10321032))::
1.1. aa == 19761976 ee bb == 10321032..
22.. DividaDivida aa porpor bb,, encontrandoencontrando umum quocientequociente qq ee umum
restoresto rr (isto(isto é,é, aa == q*b+rq*b+r))..
33.. DefinaDefina aa == bb ee bb == rr..
1. Recursividade1. Recursividade
Passo a b q r
1 1976 1032
2 1976 1032 1 944
3 1032 944
4 e 2 1032 944 1 88
3 944 88
4 e 2 944 88 10 64
3 88 64
24/11/201124/11/2011 7373
33.. DefinaDefina aa == bb ee bb == rr..
44.. RepitaRepita osos passospassos 22 ee 33,, atéaté queque bb sejaseja igualigual aa 00..
55.. MDC(MDC(19761976,, 10321032)) == aa..
3 88 64
4 e 2 88 64 1 24
3 64 24
4 e 2 64 24 2 16
3 24 16
4 e 2 24 16 1 8
3 16 8
4 e 2 16 8 2 0
3 8 0
5 MDC = 8
Para casa, implementar
a solução recursiva em C.
Computação BásicaComputação Básica
• Em termos gerais, não há por que procurar uma solução
recursiva para um problema.
• A maioria dos problemas pode ser solucionada usando métodos
não-recursivos.
• Uma solução recursiva ocupa mais memória e é mais lenta que
a solução iterativa para um mesmo problema.
1. Recursividade1. Recursividade
24/11/201124/11/2011 7474
� Em cada instância, todos os parâmetros e variáveis locais
são criados novamente, independentemente dos que já
existiam antes.
• Nem sempre é fácil reconhecer situações apropriadas para a
utilização de recursividade.
• Porém, há certos problemas cuja natureza permite uma solução
recursiva bem mais elegante e intuitiva do que a solução
iterativa.