Aula01-P O T A

Prévia do material em texto

Escola de Exatas
Ciência da Computação
Pesquisa, Ordenação e Técnicas de Armazenamento
Professor Israel Costa
Roteiro
❑ Relembrando
❑ Definição de Recursividade
❑ Exemplos de Recursividade
❑ Estrutura da Recursividade
❑ Vantagens e desvantagens da Recursividade
2
Relembrando em Estrutura de 
Dados
• Lista Linear.
• Lista Duplamente Encadeada.
• Lista Circular.
• Pilha.
• Fila.
• Árvore Binária.
• Árvore Binária de Busca.
• Percursos em Árvore
• Árvore AVL. 
• Rotação simples à direita.
• Rotação simples à esquerda.
• Rotação dupla à direita.
• Rotação dupla à esquerda
Introdução
• Fonte: https://encrypted-
tbn0.gstatic.com/images?q=tbn:ANd9GcQCGE
sUlhPaY2NDRLZNROd5jgklzMjdQUfqsN8hoGXe
GHQPZTNxPA
https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcQCGEsUlhPaY2NDRLZNROd5jgklzMjdQUfqsN8hoGXeGHQPZTNxPA
Introdução
• Fonte: https://encrypted-
tbn0.gstatic.com/images?q=tbn:ANd9Gc
QCGEsUlhPaY2NDRLZNROd5jgklzMjdQUf
qsN8hoGXeGHQPZTNxPA
https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcQCGEsUlhPaY2NDRLZNROd5jgklzMjdQUfqsN8hoGXeGHQPZTNxPA
Introdução
❑ “O número natural é o 0
(Zero).
❑ O sucessor de um
número natural é
também o número
natural”.
❑ Giuseppe Peano (1858-
1932)
Figura 3: Giuseppe Peano
Introdução
❑ Em computação, a recursividade é
quando definimos uma rotina
(procedimento ou função) que chama
a si mesma.
❑ Em seu corpo de código há uma
chamada (ou invocação) para ela
mesma.
Recursividade e termos 
Sinônimos:
❑ Recursão;
❑ Recursividade;
❑ Autoreferência;
❑ Recorrência 
Recursão
em C++
A recursão é uma técnica
que define um problema
em termos de uma ou mais
versões menores deste
mesmo problema.
Esta ferramenta pode ser
utilizada sempre que for possível
expressar a solução de um
problema em função do próprio
problema.
4
Recursão em C
Uma função é dita recursiva quando dentro do 
seu código existe uma chamada para si mesma.
Ex: cálculo do fatorial de um número:
n! = n * (n -1)!
Exemplos de Recursividade
▪ O exemplo a seguir define o
ancestral de uma pessoa:
▪ Os pais de uma pessoa são seus ancestrais (caso
base);
▪ Os pais de qualquer ancestral são também ancestrais
da pessoa inicialmente considerada (passo
recursivo).
▪ Componente para uma
equipamento eletrônico:
▪ Um componente eletrônico é formado por outros
componentes (caso base);
▪ Cada componente integrante do componente
eletrônico também é formado por outros
componentes (passo recursivo).
Vantagens
▪ CÓDIGO MAIS LEGÍVEL
▪ MAIS ENXUTO
▪ MAIS FÁCIL DE MANTER
Recursividade – Exercícios
1. Construa um algoritmo que imprima os números
pares no intervalo de 0 a 30.
2. Construa um algoritmo que imprima os números
ímpares no intervalo de 0 a 50.
3. Construa um algoritmo que imprima os números
múltiplos de 5 no intervalo de 0 a 100.
4. Altere o código da questão 1 para mesma solução dos
números pares imprimindo-os de forma recursiva.
5. Altere o código da questão 2 para mesma solução dos
números ímpares imprimindo-os de forma recursiva.
6. Altere o código da questão 3 para mesma solução dos
múltiplos de 5 imprimindo-os de forma recursiva.
Exemplos de Recursividade
❑ O fatorial de um número N é o produto de todos os
números inteiros entre 1 e N. Por exemplo, . fatorial (ou
3!) é 1 * 2 *3 = 6.
❑ Mas multiplicar n pelo produto de todos os inteiros a
partir de n-1 até 1 resulta no produto de todos os inteiros
de n a 1. Portanto, é possível dizer que fatorial:
0! = 1
1! = 1 * 0!
2! = 2 * 1!
3! = 3 * 2!
4! = 4 * 3!
Exemplos de Recursividade
❑ Logo o fatorial de um número também
pode ser definido recursivamente (ou por
recorrência) através das seguintes regras:
n! = 1, se n = 0 ou n=1
n! = fatorial(n-1)*n! , se n > 0
Exercício
1. Construa um algoritmo que calcule o fatorial
de um determinado numero de forma
iterativa.
2. Altere o código para a mesma solução do
cálculo do fatorial de forma recursiva a partir
da relação de recorrência abaixo:
N! = 1, se n = 0 ou n=1 (caso base)N!
N! = fatorial(n-1)*n! , se n > 1
Exercício última aula (manhã)
3. Escreva uma função recursiva para calcular
conforme a estrutura de recorrência abaixo:
4. Calcule o somatório dos N primeiros números
a partir da relação de recorrência abaixo:
P2 = 1, se N = 1 (solução trivial)
P2 = S(N-1) + N, se N > 1
P1=1, se y=0 | P1= x, se y=1
P1
P2
P1=x*pot(x, y-1), se y>1
Exercício
5. Analise o código abaixo, teste-o e monte a relação
de recorrência com base na solução do problema
em questão:
#include <stdio.h>
int Rec(int x, int y){
if (y == 0)
return 0;
else
return x + Rec(x, y-1);
}
main(){
int num1, num2;
printf("Resultado: %d", Rec(num1,num2));
}
Exercício
6. Faça uma função recursiva que resolva a
seguinte equação:
r(0) = 2 //caso base
r(x) = 2 * r (x –1) –4 //passo recursivo
DESAFIO
5. Construa um algoritmo que calcule e imprima 
a sequência de Fibonacci abaixo:
0 1 1 2 3 5 8 13 21.
O Custo de memória e o esforço 
computacional para tudo isso
❑ Quando uma função chama a si mesma, novos
parâmetros e variáveis locais são alocados na
pilha, sendo criado um novo contexto de
execução para as variáveis e o código da função
é executado com essas novas variáveis.
❑ Uma chamada recursiva não faz uma nova cópia
da função; apenas os argumentos são novos.
❑ Quando cada função recursiva retorna, as
variáveis locais e os parâmetros são removidos
da pilha e a execução recomeça do ponto da
chamada à função dentro da função.
EXEMPLO FATORIAL
#include <stdio.h>
int fatorial (int n)
{
if (n == 1 || n == 0) /* condição de parada da recursão*/
return 1;
else if (n < 0) {
printf ("Erro: fatorial de número negativo!\n"); 
exit(0);
}
return n*fatorial(n-1);
}
5
EXEMPLO FATORIAL
fatorial(5)
=> (5 ° 0)
return 5 • fatorial(4)
=> (4 ° 0)
return 4 • fatorial(3)
=> (3 ° 0)
return 3 • fatorial(2)
=> (2 ° 0)
return 2 • fatorial(1)
=> (1 ° 0)
return 1 • fatorial(0)
=> (0 == 0)
<= return 1
<= return 1 • 1 (1)
<= return 2 • 1 (2)
<= return 3 • 2 (6)
<= return 4 • 6 (24)
<= return 5 • 24 (120)
120
6
/* Faça um programa que calcula e mostra o fatorial de um 
número inteiro positivo n. (Ex: 0! = 1; 3! = 3*2*1 = 6)
*/
#include <stdio.h> 
#include <conio.h>
int fatorial (int n)
{
if (n == 
0) 
return
1;
else if (n<0){
printf("\nErro: fatorial de numero 
negativo!\n"); getch();
exit(0);
}
return n*fatorial(n-1);
}
7
int main(void)
{
int n, fat=1;
printf("Digite um numero inteiro:"); 
scanf("%d", &n);
fat=fatorial(n);
printf("\n\nO fatorial de %d eh: %d", n, 
fat);
getch();
}
8
EX: SOMA N PRIMEIROS NÚMEROS 
INTEIROS
Supondo N = 5;
S(5) = 1+2+3+4+5 = 15
-> S(5) = S(4) + 5 -> 10 + 5 = 15
S(4) = 1+2+3+4 =10
-> S(4) = S(3) + 4 -> 6 + 4 = 10
S(3) = 1+2+3 = 6
-> S(3) = S(2) + 3 -> 3 + 3 = 6
S(2) = 1+2 = 3
-> S(2) = S(1) + 2 -> 1 + 2 = 3
S(1) = 1 =1
-> S(1) = 1 --------------->solução trivial 9
Recursão
❑ Em procedimentos recursivos pode ocorrer um
problema de terminação do programa, como um
“looping interminável ou infinito”.
❑ Portanto, para determinar a terminação das
repetições, deve-se:
❑ Definir uma função que implica em uma
condição de terminação (solução trivial), e
❑ Provar que a função decresce a cada
passo de repetição, permitindo que,
eventualmente, esta solução trivial
seja atingida.
10
ESTRUTURA DE UMA RECURSÃO
 uma recursão obedece a uma estrutura que 
deve conter os seguintes elementos:
função (par)






teste de término de recursão utilizando par
se teste ok, retorna aqui
processamento
aqui a função processa as informações em par
chamada recursiva em par’
par deve ser modificado de forma que a recursão chegue 
a um término
11
EX: SOMA N PRIMEIROS NÚMEROS 
INTEIROS
main( )
{
int n;
scanf(“%d”, &n);
printf(“%d”, soma(n));
}
int soma(int n)
{
if (n == 1) return (1);
else return (n + soma(n – 1));
}
12
EXEMPLO: PRINTD(INT)
printd(int) imprime um inteiro usando 
recursão
void printd(int n) {
/* imprime sinal */if (n < 0) {
putchar('-'); 
n = -n;
}
if (n / 10) /* termino recursao */
printd(n/10); /* recursao se n>10 */ 
putchar(n % 10 + '0'); /* senao imprime char */
}
13
EXEMPLO PRINTD()
printd(-1974)
==> (n < 0) --> putchar(„-‟) -
==>printd(197) -
==> printd(19)
==> printd(1) 
(1 / 10 = = 0)
putchar(1 + „0‟)
putchar(19%10 + „0‟)
putchar(197%10 + „0‟)
putchar(1974 %10 + „0‟)
-
-
-
-1
-19
-197
-1974 14
ANALISANDO RECURSIVIDADE
Vantagens X Desvantagens
 Um programa recursivo é mais elegante e
menor que a sua versão iterativa, além de
exibir com maior clareza o processo
utilizado, desde que o problema ou os
dados sejam naturalmente definidos
através de recorrência.
 Por outro lado, um programa recursivo
exige mais espaço de memória e é, na
grande maioria dos casos, mais lento do
que a versão interativa.
15
Exemplos de Programas com 
função recursiva 
1. Escreva uma função recursiva para
calcular o valor de uma base x elevada a
um expoente y.
2. Escrever uma função recursiva
que retorna o tamanho de um
string,
tamstring(char s[])
3. Fazer uma função recursiva que conta o
número de ocorrências de um
determinado caracter, caract(char c, char
s[])
4. Escreva uma função recursiva que produza
o reverso de um string, reverse(char s[])
Exemplos de Programas com 
função recursiva 
1. Escreva uma função recursiva para calcular o
valor de uma base b elevada a um expoente e.
Recorrência:
be=1, se e=0 | be= b, se e=1
be=b*potencia(b, e-1), se e>1
#include <stdio.h> 
#include <conio.h>
int expo (int x, int y)
{
if (y == 0) 
return 1;
if (y == 1)
return x;
return x*expo(x,y-1);
}
int main(void) { 
int x, y, e;
printf("Exponencial de x elevado a y\n\n"); 
printf("\nDigite o numero inteiro x:"); 
scanf("%d", &x);
printf("\nDigite o numero inteiro y:");
scanf("%d", &y);
if (y < 0) {
printf("y tem que ser maior ou igual a zero!!"); 
getch(); }
else{ 
e=expo(x,y);
printf("\n\nX elevado a y eh: %d", e);
getch();}
}
17
#include <stdio.h>
#include <conio.h>
int tamstring(char s[])
{
if (s[0] == '\0')
return 0;
return 1+tamstring(&s[1]);
}
int main(void)
{
char s[20]; 
int t;
printf("Tamanho de string\n\n"); 
printf("\nDigite a string: "); 
scanf("%s", s);
t=tamstring(s);
printf("\n\nO tamanho eh %d", t);
getch();
}
18
/* conta quantas vezes um caractere ocorre em uma string*/ 
#include <stdio.h>
#include <conio.h>
int carac(char c,char s[])
{
if (s[0] == '\0')
return 0;
if (s[0]==c) return (1+carac(c,++s)); 
return carac(c,++s);
}
int main(void)
{
char s[30],c; 
int t;
printf("Busca em string\n\n"); 
printf("\nDigite a string: "); 
gets(s);
printf("\nDigite o caractere desejado: "); 
c=getchar();
t=carac(c,s);
printf("\n\nEncontrei %d vezes", t);
getch();
}
19
/* imprime uma string em ordem reversa*/
#include <stdio.h>
#include <conio.h>
void contrario(char s[])
{
if (s[0] != '\0'){
contrario(&s[1]); 
printf("%c",s[0]);}
}
int main(void)
{
char s[30],c;
int t;
printf("Imprime reverso\n\n"); 
printf("\nDigite a string: "); 
gets(s);
contrario(s);
getch();
}
20
Atividade – Aula01
1. Defina e exemplifique o conceito 
de recursividade.
2. Descreva sobre as Vantagens e 
desvantagens da Recursividade.
3. Qual o custo de memória e o 
esforço computacional para uma 
função recursiva?
BIBLIOGRAFIA BÁSICA
DOBRUSHKIN, Vladimir A. Métodos para Análise de Algoritmos. LTC, 03/2012.
TANENBAUM, Andrew S., WOODHULL, S. Sistemas Operacionais: Projetos e
Implementação - O Livro do Minix. Bookman, 01/2008.
MONTEIRO, Mario A. Introdução à Organização de Computadores, 5ª edição. LTC,
05/2007.