AED1 02 Recursividade

Prévia do material em texto

Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Aula 02: Recursividade
Wanderley de Souza Alencar
wanderley@inf.ufg.br
Universidade Federal de Goia´s - UFG
Instituto de Informa´tica - INF
March 21, 2018
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Suma´rio
1 Introduc¸a˜o
2 Tipos de Recursividade
3 Escrevendo Func¸o˜es Recursivas
4 Vantagens e Desvantagens
5 Saiba Mais...
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Introduc¸a˜o
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Introduc¸a˜o
Recursividade
Propriedade daquilo que se pode repetir um nu´mero indefinido de
vezes.
Um certo ente (concreto ou abstrato) e´ chamado de recursivo se
ele e´ definido em termos de si mesmo, auto-referenciando-se,
pore´m numa instaˆncia de menor dimensa˜o.
A grande ideia subjacente e´ possibilitar uma definic¸a˜o finita para
algo que pode ser, por esseˆncia, infinito.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Introduc¸a˜o
Axioma de Peano
“O primeiro nu´mero natural e´ o 0 (zero).
O sucessor de um nu´mero natural e´ tambe´m um nu´mero natural.”
Giuseppe Peano (1858 – 1932)
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Introduc¸a˜o
Recursividade
O uso do conceito de recursividade e´ extremamente conveniente
para a soluc¸a˜o de algumas classes de problemas...
...em especial na descric¸a˜o de soluc¸o˜es a serem executadas por
computadores – algoritmos computacionais.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Introduc¸a˜o
Recursividade
Em Computac¸a˜o, a recursividade e´ o mecanismo de programac¸a˜o
pelo qual e´ poss´ıvel definir uma rotina (procedimento ou func¸a˜o)
em termos de si mesma, o que implica que em seu corpo de co´digo
ha´ uma chamada (ou invocac¸a˜o) para ela mesma.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Introduc¸a˜o
Recursividade
Sa˜o termos sinoˆnimos:
recursa˜o;
recursividade;
autorefereˆncia;
recorreˆncia.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Introduc¸a˜o
Exemplo 01
O fatorial de um nu´mero natural n, n ∈ N, pode ser escrito na˜o
recursivamente assim:
0! = 1
n! = n · (n − 1) · (n − 2) · · · 2 · 1
Usando-se a recursividade, pode-se definir:
n! =
{
1, se n = 0
n · (n − 1)!, se n > 0
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Introduc¸a˜o
1 //
2 // Fatorial (iterativo)
3 //
4 unsigned long int fatorial (unsigned long int num) {
5 unsigned long int fat=1, i;
6
7 for (i=num; (i > 1); i−−) {
8 fat = fat ∗ i;
9 }
10 return(fat);
11 }
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Introduc¸a˜o
1 //
2 // Fatorial (recursivo)
3 //
4 unsigned long int fatorial (unsigned long int num) {
5 if (num == 0) {
6 return (1);
7 }
8 else {
9 return (num ∗ fatorial(num−1));
10 }
11 }
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Introduc¸a˜o
Comenta´rios
E´ fundamental que toda func¸a˜o recursiva preveja,
cuidadosamente, como o processo de recursa˜o sera´
interrompido;
Na func¸a˜o fatorial o processo e´ interrompido quando o
valor do nu´mero passado como paraˆmetro e´ igual a ZERO;
E´ importante notar que recursa˜o na˜o traz, obrigatoriamente,
economia de memo´ria, isto porque os valores sendo
processados sa˜o mantidos em pilhas;
Nem sera´ mais ra´pida que a versa˜o iterativa, e, a`s vezes, pode
ser ate´ (muito) mais lenta, porque tem-se o custo de chamada
das func¸o˜es.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Introduc¸a˜o
Exemplo 02
A poteˆncia natural de um nu´mero real x , x ∈ <, pode ser escrita
recursivamente assim:
1 //
2 // Elevar: xˆn
3 //
4 float elevar(float x, int n) {
5 if (n == 0) {
6 return (1);
7 }
8 if (n == 1) {
9 return (x);
10 }
11 else {
12 return (x ∗ elevar(x, n−1));
13 }
14 }
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Tipos de Recursividade
“Iterar e´ humano, fazer recursa˜o e´ divino.”
Laurence Peter Deutsch(1946 - . . . )
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Tipos de Recursividade
Computacionalmente ha´, em verdade, dois poss´ıveis tipos de
recursividade:
1 direta;
2 indireta.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Tipos de Reursividade
Direta
Na recursividade direta, uma rotina A possui em seu corpo uma
chamada para si mesma, como ja´ visto:
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Tipos de Recursividade
Direta
1 A rotina A inicia sua execuc¸a˜o e, em alguma linha de
seu co´digo, chama a si mesma. Assim...;
2 a presente execuc¸a˜o e´ interrompida, todo seu
contexto e´ salvo e...
3 Uma nova execuc¸a˜o de A e´ iniciada...
4 os passos [2] e [3] podem ser repetidos diversas
vezes, ...
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Tipos de Recursividade
Direta
5 ate´ que A atingira´ um caso ba´sico, onde nenhuma
chamada recursiva e´ realizada e aquela instaˆncia do
problema e´ resolvida diretamente. Em seguida, ...
6 as chamadas ja´ realizadas para A sa˜o, uma a uma,
resolvidas e retornam ate´ atingir...
7 a primeira chamada a A que, finalmente, e´ conclu´ıda.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Tipos de Recursividade
Direta
As func¸o˜es recursivas anteriores, fatorial e elevar, empregam a
recursa˜o direta.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...Tipos de Recursividade
Indireta
Na recursividade indireta, a rotina A possui em seu corpo uma
chamada para outra rotina, B, que, por sua vez, possui em seu
copro uma chamada para a rotina A.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Tipos de Recursividade
Indireta
Note que, dessa forma, cria-se um c´ırculo de chamadas:
A→ B → A→ B → · · · .
Este c´ırculo, evidentemente, tera´ que ser finito para que possa ser
utilizado de maneira pra´tica:
A→ B → A→ B → · · ·A
ou
A→ B → A→ B → · · ·B.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Tipos de Recursividade
Exemplo 03
Considere duas func¸o˜es, f e g , gene´ricas, e definidas sobre os
nu´meros naturais:
f (x) =
{
2, se x ≤ 1
2 · g (x + 1) , se x > 1
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Tipos de Recursividade
Exemplo 03
Considere duas func¸o˜es, f e g , gene´ricas, e definidas sobre os
nu´meros naturais:
g (y) =
{
3, se y ≥ 5
2 · f (y − 2) , se y < 5
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Tipos de Recursividade
Indireta
Note que o par de func¸o˜es f e g sa˜o recursivas indiretamente, pois:
no corpo de f ha´ uma chamada para a func¸a˜o g , e;
no corpo de g ha´ uma chamada para a func¸a˜o f .
Como consequeˆncia, pode-se ter um looping infinito de chamadas?
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Tipos de Recursividade
Exemplo 03
Qual a sequeˆncia de chamadas ao executarmos f (2)?
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Tipos de Recursividade
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Tipos de Recursividade
Exemplo 03
Ou seja, teremos a seguinte sequeˆncia de chamadas:
1 f (2) = 2× g (2 + 1);
2 g (3) = 2× f (3− 2);
3 f (1) = 2.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Tipos de Recursividade
Exemplo 03
Ao atingir a u´ltima chamada, que determina que f (1) = 2, havera´
a sequeˆncia de retornos das func¸o˜es f e g recursivamente
invocadas...
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Tipos de Recursividade
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Tipos de Recursividade
Exemplo 03
Ou seja, o retorno de cada uma das chamadas gera a sequeˆncia:
4 g (3) = 2× 2 = 4;
5 f (2) = 2× 4 = 8;
6 f (2) = 8.
Conclu´ıda com f (2) = 8.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Tipos de Recursividade
Exemplo 03
E´ fa´cil concluir que func¸o˜es indiretamente recursivas devem ser
elaboradas – e implementadas – com extrema atenc¸a˜o, pois e´ fa´cil
obter func¸o˜es que podem gerar loopings infinitos.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Tipos de Recursividade
Indireta
Outra observac¸a˜o importante e´:
A recursa˜o indireta pode envolver mais de duas func¸o˜es, como em:
A→ B → C → A→ B → C · · ·A.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Tipos de Recursividade
Extensa˜o da Classificac¸a˜o
A classificac¸a˜o das rotinas recursivas pode ainda ser extendida
para:
Direta em cauda – a recursa˜o ocorre na u´ltima
declarac¸a˜o da rotina recursiva A;
na˜o cauda – a recursa˜o ocorre numa declarac¸a˜o
que na˜o e´ a u´ltima de A;
linear – quando nenhuma das declarac¸o˜es
remanescentes de A exige chamadas recursivas;
em a´rvore – quando alguma das declarac¸o˜es
remanescentes de A exige chamadas recursivas.
Indireta
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Tipos de Recursividade
Exemplo 04
O somato´rio dos elementos de um vetor de nu´meros inteiros V
(V1×n), pode ser escrita como uma func¸a˜o recursiva linear:
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Tipos de Recursividade
1 //
2 // Somatorio dos elementos do vetor (recursivo): posicoes de 0 a (n−1)
3 //
4 unsigned long int somatorio (unsigned long int vetor[], unsigned int n) {
5 if (n == 1) {
6 return vetor[n−1];
7 }
8 else {
9 return (vetor[n−1] + somatorio(vetor,(n−1)));
10 }
11 }
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Sequeˆncia de Passos
Para escrever uma func¸a˜o recursiva, siga os seguintes passos:
1 Escreva um proto´tipo para a func¸a˜o recursiva;
2 Escreva um comenta´rio que descreva (o melhor
poss´ıvel) o que a func¸a˜o deve fazer;
3 Determine o caso ba´sico (lembre-se: pode haver mais
de um) e a soluc¸a˜o direta deste caso;
4 Determine qual e´ o problema imediatamente menor
que o atual a ser resolvido;
5 Use a soluc¸a˜o do problema imediatamente menor
para resolver o problema maior.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Exemplo 04
Considere que devemos resolver o seguinte problema por meio do
uso de recursa˜o:
Somar todos os n elementos de um vetor de nu´meros naturais
(n ∈ N∗).
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Exemplo 04
1 Escreva um proto´tipo da func¸a˜o recursiva:
unsigned long int somatorio(unsigned long
int vetor[], unsigned int n);.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Exemplo 04
2 Escreva um comenta´rio que descreva (o melhor
poss´ıvel) o que a func¸a˜o deve fazer:
‘‘A func¸~ao deve somar os n elementos de um
vetor de nu´meros naturais.’’.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es RecursivasVantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Exemplo 04
3 Determine o caso ba´sico (lembre-se: pode haver mais
de um) e a soluc¸a˜o direta deste caso:
O menor problema a ser resolvido e´
somatorio(vetor, 1).
Observac¸a˜o: lembre-se que em C o primeiro
elemento esta´ na posic¸a˜o 0, o segundo na posic¸a˜o 1
e, finalmente, n-e´simo elemento esta´ na posic¸a˜o
n − 1.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Exemplo 04
4 Determine qual e´ o problema imediatamente menor
que o atual a ser resolvido:
O problema imediatamente menor que o de tamanho
n e´ o de tamanho n − 1:
somatorio(vetor, n-1)
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Exemplo 04
5 Use a soluc¸a˜o do problema imediatamente menor
para resolver o problema maior:
vetor[n-1] + somatorio(vetor, n-1)
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Exemplo 04
1 //
2 // Somatorio dos elementos do vetor (recursivo): posicoes de 0 a (n−1)
3 //
4 unsigned long int somatorio (unsigned long int vetor[], unsigned int n) {
5 if (n == 1) {
6 return vetor[n−1];
7 }
8 else {
9 return (vetor[n−1] + somatorio(vetor,(n−1)));
10 }
11 }
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Exemplo 05
Torres de Hano´i
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Exemplo 05
Algoritmo Recursivo:
1 Se n = 1, enta˜o mova este disco de A para B e pare;
2 Mova os (n − 1) discos superiores de A para C usando B
como auxiliar;
3 Mova o disco restante de A para B;
4 Mova os (n − 1) discos de C para B, usando A como auxiliar.
5 MA´GICA: NA˜O PRECISA SABER COMO MOVER...
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Exemplo 05 – com TREˆS discos
Torres de Hano´i
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Exemplo 05 – com QUATRO discos
Torres de Hano´i
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
1 //
2 // Torres de Hanoi (recursivo)
3 //
4 #include <stdio.h>
5 void towers(int nDiscos, char dePino, char paraPino, char auxPino) {
6 /∗ Se um disco somente, mova−o e retorne ∗/
7 if(nDiscos==1) {
8 printf(”Move disco 1 do pino %c para pino %c\n”, dePino, paraPino);
9 return;
10 }
11 /∗ Move n−1 discos superiores de A para C, usando B ∗/
12 towers(nDiscos−1, dePino, auxPino, paraPino);
13
14 /∗ Move discos restantes de A para B ∗/
15 printf(”Move disco %d do pino %c para pino %c\n”, nDiscos, dePino,
paraPino);
16
17 /∗ Move n−1 discos de C para B usando A como auxiliar ∗/
18 towers(nDiscos−1, auxPino, paraPino, dePino);
19 }
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Exemplo 06
Calcular o mdc (ma´ximo divisor comum) entre dois nu´meros
naturais, a, b ∈ N.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Exemplo 06
Algoritmo Recursivo:
1 Se b = 0, enta˜o retorne o valor a e pare;
2 Retorne o valor do mdc(b, a % b).
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
1 //
2 // mdc (recursivo)
3 //
4 unsigned long int mdc(unsigned long int a, unsigned long int b) {
5 if (b == 0) {
6 return(a);
7 }
8 else {
9 return (mdc(b, (a %b));
10 }
11 }
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Exemplo 07
Nu´meros Binomiais
Sir Isaac Newton (1642 - 1727).
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Exemplo 07
O nu´mero binomial Cnk , e´ definido por:
Cnk =
n!
k!×(n−k)!
com n, k ∈ N e n ≥ k .
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Exemplo 07
Algoritmo Recursivo:
1 Se (n = k) ou (k = 0), enta˜o retorne o valor UM e pare;
2 Retorne o valor da soma dos binomais Cn−1k e C
n−1
k−1 .
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
1 //
2 // numero binomial (recursivo)
3 //
4 unsigned long int binomial(unsigned long int n, unsigned long int k){
5 if ((n == 0) || (k == n)) {
6 return (1);
7 }
8 return (binomial(n−1,k) + binomial(n−1,k−1));
9 }
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Exemplo 08
Leonardo Bonacci (1175-1240/50) ou Leonardo de Pisa:
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Exemplo 08
Espiral de Fibonacci:
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Exemplo 08
Calcular o n-e´simo nu´mero da sequeˆncia de Fibonacci, com n ∈ N∗.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Exemplo 08
Algoritmo Recursivo:
1 Se n = 1 ou n = 2, enta˜o retorne o valor 1 e pare;
2 Retorne o valor da soma dos elementos nas posic¸o˜es (n − 1) e
(n − 2).
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
1 //
2 // Numero de Fibonacci (recursivo)
3 //
4 unsigned long int fibonacci(unsignedlong int n) {
5 if ((n == 1) || (n == 2)) {
6 return (1);
7 }
8 else {
9 return (fibonacci(n − 1) + fibonacci(n − 2));
10 }
11 }
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Programa principal:
1 //
2 // Numero de Fibonacci (recursivo) − Programa principal
3 //
4 int main() {
5 int n;
6
7 printf(”Entre a ordem do elemento desejado: ”);
8 scanf(”%d”,&n);
9 printf(”O numero de Fibonacci e %d:\n”, fibonacci(n));
10 return 0;
11 }
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Exemplo 09
Problema do Cavalo:
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Exemplo 09
O Problema do Cavalo (ou Passeio do Cavalo) e´ um problema
matema´tico envolvendo o movimento da pec¸a do cavalo no
tabuleiro de xadrez. Um cavalo e´ colocado no tabuleiro vazio e,
seguindo as regras do jogo, precisa passar por todas as casas
exatamente uma vez em movimentos consecutivos.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Exemplo 09
Apo´s ser colocado numa posic¸a˜o qualquer (i , j), com 1 ≤ i , j ≤ 8,
de tabuleiro de xadrez inicialmente vazio, o cavalo devera´ percorrer
todas as demais casas, exatamente uma vez, em movimentos
consecutivos.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Exemplo 09
Pesquise sobre os poss´ıveis algoritmos – iterativos e recursivos –
para resolver o Problema do Cavalo e implemente pelo menos um
deles.
Pense na seguinte generalizac¸a˜o: e se o tabuleiro puder ter
qualquer tamanho n × n, com n ∈ N∗?
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Exemplo 10
Problema da Rainha:
Elizabeth II (1926 - . . . ), Rainha do Reino Unido.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Exemplo 10
O Problema da Rainha e´ um problema matema´tico envolvendo a
colocac¸a˜o de OITO rainhas no tabuleiro de xadrez. Todas as
rainhas devem ser colocadas de maneira tal que nenhuma delas
seja capaz de capturar outra.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Escrevendo Func¸o˜es Recursivas
Exemplo 10
Pesquise sobre os poss´ıveis algoritmos – iterativos e recursivos –
para resolver o Problema da Rainha e implemente pelo menos um
deles.
Pense na seguinte generalizac¸a˜o:
e se o tabuleiro puder ter qualquer tamanho n × n, com n ∈ N∗,
devendo-se, portanto, serem inseridas n rainhas?
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Vantagens e Desvantagens
Como e´ comum em Computac¸a˜o, nada e´ perfeito:
O uso de recursividade apresenta vantagens e desvantagens de
acordo com o vie´s que se analise.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Vantagens e Desvantagens
Vantagens
Em geral, o co´digo recursivo e´ mais fa´cil de escrever/ler que o
iterativo correspondente;
Algumas situac¸o˜es sa˜o naturalmente recursivas e, portanto,
expressa´-las recursivamente e´ mais simples.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Vantagens e Desvantagens
Vantagens
Algumas estruturas sa˜o naturalmente recursivas:
Listas encadeadas;
A´rvores bina´rias.
Problemas naturalmente recursivos:
Deslocamento em listas encadeadas;
Caminhamento em a´rvores bina´rias;
Avaliac¸a˜o de expresso˜es.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Vantagens e Desvantagens
Desvantagens
As func¸o˜es recursivas sa˜o geralmente mais lentas que as
func¸o˜es iterativas correspondentes;
Recursa˜o excessiva pode fazer com que haja um estouro da
pilha de execuc¸a˜o;
A`s vezes, cada chamada de func¸a˜o gera duas ou mais
chamadas recursivas nesse n´ıvel.
E´ preciso ter muito cuidado ao escrever func¸o˜es recursivas,
pois elas podem ser complicadas.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Saiba Mais...
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Saiba Mais...
Livros
1 CORMEN, Thomas H. et al., Algoritmos (Traduc¸a˜o da 2a
edic¸a˜o norte-americana – SOUZA, Vandenberg D. de), Rio de
Janeiro:Elsevier, 2002, 934pp.
2 SZWARCFITER, Jayme L. e MARKEZON, Lilian. Estruturas
de dados e seus algoritmos, Rio de Janeiro:LTC, 1994, 326pp;
3 TANENBAUM, Aaron A. et al., Estruturas de dados usando C
(Traduc¸a˜o – SOUZA, Tereza Cristina F. de), Sa˜o
Paulo:Makron Books, 1995, 904pp.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
Introduc¸a˜o
Tipos de Recursividade
Escrevendo Func¸o˜es Recursivas
Vantagens e Desvantagens
Saiba Mais...
Saiba Mais...
Outros
1 websites que tratam sobre o tema;
2 lista de exerc´ıcios publicada na a´rea da disciplina na
Plataforma EaD-INF/UFG e/ou Sharif Judge System do
INF/UFG.
Wanderley de Souza Alencar wanderley@inf.ufg.br AED1: Aula 02
	Introdução
	Tipos de Recursividade
	Escrevendo Funções Recursivas
	Vantagens e Desvantagens
	Saiba Mais...