Aula 28 - Recursividade

Prévia do material em texto

A28: Recursividade
Kazuki Yokoyama
kmyokoyama@inf.ufrgs.br
Algoritmos e Programação
INF01202 – Algoritmos e Programação, 2018/01, Turmas I e J
*adaptado do material do prof. Marcelo Walter e prof. Rodrigo Ruas Oliveira e cedido pela profª. Mariana 
Recamonde 
Atenção:
O material aqui contido não substitui a leitura do livro texto e é incompleto sem a 
apresentação do professor em aula.
2
Recursividade
3
O que é? auto-referência em um procedimento (ou seja, o procedimento chama 
a si mesmo em algum ponto da execução).
Recursividade
TIPO exemplo_recursao(...){
 ...
 exemplo_recursao(...);
 ...
}
4
O que é? auto-referência em um procedimento (ou seja, o procedimento chama 
a si mesmo em algum ponto da execução).
Quando usar? em problemas que são resolvidos pela composição de instâncias 
menores do mesmo problema. Algum exemplo já visto em aula?
Recursividade
Ex: n! = n * (n-1)!
5
Recursividade
O que é? auto-referência em um procedimento (ou seja, o procedimento chama 
a si mesmo em algum ponto da execução).
Quando usar? em problemas que são resolvidos pela composição de instâncias 
menores do mesmo problema. Ex: n! = n * (n-1)!
Como usar?
- criar um procedimento que chame a si mesmo
- definir um critério de parada, para impedir repetição indefinida
- incluir mudança na chamada da função, de forma a garantir que, em algum 
momento, as chamadas recursivas alcancem a condição de parada
6
O que é? auto-referência em um procedimento (ou seja, o procedimento chama 
a si mesmo em algum ponto da execução).
Quando usar? em problemas que são resolvidos pela composição de instâncias 
menores do mesmo problema. Ex: n! = n * (n-1)!
Como usar?
- criar um procedimento que chame a si mesmo
- definir um critério de parada, para impedir repetição indefinida
- incluir mudança na chamada da função, de forma a garantir que, em algum 
momento, as chamadas recursivas alcancem a condição de parada
Recursividade
Nós já terminamos? Se sim, retorne os resultados // Sem uma 
condição de parada como esta, uma recursão iria se repetir eternamente.
Senão, simplifique o problema // resolva o(s) problema(s) mais simples , 
e então encaixe os resultados na solução do problema original
7
Recursividade
Como usar?
- criar um procedimento que chame a si mesmo
- definir um critério de parada, para impedir repetição indefinida
- incluir mudança na chamada da função, de forma a garantir que alguma das 
chamadas recursivas alcancem condição de parada
Fatorial:
0! = 1
n! = n*(n-1)!
caso base (com solução trivial)
definição recursiva (convergente p/ caso base) 8
5! = 5 x 4!
 4! = 4 x 3!
 3! = 3 x 2!
 2! = 2 x 1!
 1! = 1 x 0!
Recursividade: exemplo
caso base: 0! = 1
1
1
2
6
24120
Fatorial:
0! = 1
n! = n*(n-1)!
9
Recursividade: exemplo, solução iterativa
unsigned int fatorial (unsigned int n) { // solução iterativa
 // (NÃO-RECURSIVA)
 unsigned int fat; // valor acumulado a cada iteração
 unsigned int cont;
 fat = 1;
 for (cont = 1; cont <= n; cont++){ // se n=0, nem entra
 fat = fat * cont;
 }
 return fat; // encerra função, retornando valor do fatorial
} 10
Recursividade: exemplo, solução recursiva
unsigned int fatorial (unsigned int n) { // solução recursiva
 unsigned int fat;
 if (n == 0) {
 fat = 1;
 } else {
 fat = n * fatorial(n - 1);
 }
 return fat; // encerra função, retornando valor do fatorial
} 11
Recursividade: empilhamento
unsigned int fatorial (unsigned int n)
{
 unsigned int fat;
 if (n == 0) {
 fat = 1;
 } else {
 fat = n * fatorial(n - 1);
 }
 return fat;
}
int main() {
 ...
 res = fatorial(6);
 printf("6! = %d", res);
 ...
}
res = fatorial(6);
12
Recursividade: empilhamento
unsigned int fatorial (unsigned int n)
{
 unsigned int fat;
 if (n == 0) {
 fat = 1;
 } else {
 fat = n * fatorial(n - 1);
 }
 return fat;
}
int main() {
 ...
 res = fatorial(6);
 printf("6! = %d", res);
 ...
}
fat = 6 * fatorial(5);
res = fatorial(6);
13
Recursividade: empilhamento
unsigned int fatorial (unsigned int n)
{
 unsigned int fat;
 if (n == 0) {
 fat = 1;
 } else {
 fat = n * fatorial(n - 1);
 }
 return fat;
}
int main() {
 ...
 res = fatorial(6);
 printf("6! = %d", res);
 ...
}
fat = 6 * fatorial(5);
res = fatorial(6);
fat = 5 * fatorial(4);
14
Recursividade: empilhamento
unsigned int fatorial (unsigned int n)
{
 unsigned int fat;
 if (n == 0) {
 fat = 1;
 } else {
 fat = n * fatorial(n - 1);
 }
 return fat;
}
int main() {
 ...
 res = fatorial(6);
 printf("6! = %d", res);
 ...
}
fat = 6 * fatorial(5);
res = fatorial(6);
fat = 5 * fatorial(4);
fat = 4 * fatorial(3);
fat = 3 * fatorial(2);
fat = 2 * fatorial(1);
fat = 1 * fatorial(0);
15
Recursividade: empilhamento
unsigned int fatorial (unsigned int n)
{
 unsigned int fat;
 if (n == 0) {
 fat = 1;
 } else {
 fat = n * fatorial(n - 1);
 }
 return fat;
}
int main() {
 ...
 res = fatorial(6);
 printf("6! = %d", res);
 ...
}
fat = 6 * fatorial(5);
res = fatorial(6);
fat = 5 * fatorial(4);
fat = 4 * fatorial(3);
fat = 3 * fatorial(2);
fat = 2 * fatorial(1);
fat = 1 * fatorial(0);
fat = 1;
16
Recursividade: empilhamento
unsigned int fatorial (unsigned int n)
{
 unsigned int fat;
 if (n == 0) {
 fat = 1;
 } else {
 fat = n * fatorial(n - 1);
 }
 return fat;
}
int main() {
 ...
 res = fatorial(6);
 printf("6! = %d", res);
 ...
}
fat = 6 * fatorial(5);
res = fatorial(6);
fat = 5 * fatorial(4);
fat = 4 * fatorial(3);
fat = 3 * fatorial(2);
fat = 2 * fatorial(1);
fat = 1 * fatorial(0);
17
Recursividade: empilhamento
unsigned int fatorial (unsigned int n)
{
 unsigned int fat;
 if (n == 0) {
 fat = 1;
 } else {
 fat = n * fatorial(n - 1);
 }
 return fat;
}
int main() {
 ...
 res = fatorial(6);
 printf("6! = %d", res);
 ...
}
fat = 6 * fatorial(5);
res = fatorial(6);
fat = 5 * fatorial(4);
fat = 4 * fatorial(3);
fat = 3 * fatorial(2);
fat = 2 * fatorial(1);
fat = 1 * 1;
return 1;
18
Recursividade: empilhamento
unsigned int fatorial (unsigned int n)
{
 unsigned int fat;
 if (n == 0) {
 fat = 1;
 } else {
 fat = n * fatorial(n - 1);
 }
 return fat;
}
int main() {
 ...
 res = fatorial(6);
 printf("6! = %d", res);
 ...
}
fat = 6 * fatorial(5);
res = fatorial(6);
fat = 5 * fatorial(4);
fat = 4 * fatorial(3);
fat = 3 * fatorial(2);
fat = 2 * 1;
return 1;
19
Recursividade: empilhamento
unsigned int fatorial (unsigned int n)
{
 unsigned int fat;
 if (n == 0) {
 fat = 1;
 } else {
 fat = n * fatorial(n - 1);
 }
 return fat;
}
int main() {
 ...
 res = fatorial(6);
 printf("6! = %d", res);
 ...
}
fat = 6 * fatorial(5);
res = fatorial(6);
fat = 5 * fatorial(4);
fat = 4 * fatorial(3);
fat = 3 * 2;
return 2;
20
Recursividade: empilhamento
unsigned int fatorial (unsigned int n)
{
 unsigned int fat;
 if (n == 0) {
 fat = 1;
 } else {
 fat = n * fatorial(n - 1);
 }
 return fat;
}
int main() {
 ...
 res = fatorial(6);
 printf("6! = %d", res);
 ...
}
fat = 6 * fatorial(5);
res = fatorial(6);
fat = 5 * fatorial(4);
fat = 4 * 6;
return 6;
21
Recursividade: empilhamento
unsigned int fatorial (unsigned int n)
{
 unsigned int fat;
 if (n == 0) {
 fat = 1;
 } else {
 fat = n * fatorial(n - 1);
 }
 return fat;
}
int main() {
 ...
 res = fatorial(6);
 printf("6! = %d", res);
 ...
}
fat = 6 * fatorial(5);
res = fatorial(6);
fat = 5 * 24;
return 24;
22
Recursividade: empilhamento
unsigned int fatorial(unsigned int n)
{
 unsigned int fat;
 if (n == 0) {
 fat = 1;
 } else {
 fat = n * fatorial(n - 1);
 }
 return fat;
}
int main() {
 ...
 res = fatorial(6);
 printf("6! = %d", res);
 ...
}
fat = 6 * 120;
res = fatorial(6);
return 120;
23
Recursividade: empilhamento
unsigned int fatorial (unsigned int n)
{
 unsigned int fat;
 if (n == 0) {
 fat = 1;
 } else {
 fat = n * fatorial(n - 1);
 }
 return fat;
}
int main() {
 ...
 res = fatorial(6);
 printf("6! = %d", res);
 ...
}
return 720;
res = 720;
24
Recursividade: empilhamento
unsigned int fatorial (unsigned int n)
{
 unsigned int fat;
 if (n == 0) {
 fat = 1;
 } else {
 fat = n * fatorial(n - 1);
 }
 return fat;
}
int main() {
 ...
 res = fatorial(6);
 printf("6! = %d", res);
 ...
}
return 720;
res = 720;
Início da execução
 – alocação de variáveis locais
 – parâmetros
Processamento
 – se a execução for interrompida por nova chamada 
recursiva, ocorre o “empilhamento” dos indicadores 
de execução atuais (valores, ponto de retorno)
Fim da execução
 – liberação de variáveis locais - “desempilhamento”
 – retorno ao ponto de chamada
25
Recursividade: o que faz?
void f(int n, int m) {
 if ( n < m ) {
 printf("%d\n", n);
 f(n+2, m);
 } else {
 printf("%d\n", n);
 }
}
int main() {
 f(1, 10);
 return 0;
}
26
Recursividade: o que faz?
void f(int n, int m) {
 if ( n < m ) {
 printf("%d\n", n);
 f(n+2, m);
 } else {
 printf("%d\n", n);
 }
}
int main() {
 f(1, 10);
 return 0;
}
~$./a.out
1
3
5
7
9
11
27
Recursividade: o que faz?
void f(int n, int m) {
 if ( n < m ) {
 f(n+2, m);
 printf("%d\n", n);
 } else {
 printf("%d\n", n);
 }
}
int main() {
 f(1, 10);
 return 0;
}
void f(int n, int m) {
 if ( n < m ) {
 printf("%d\n", n);
 f(n+2, m);
 } else {
 printf("%d\n", n);
 }
}
int main() {
 f(1, 10);
 return 0;
}
~$./a.out
1
3
5
7
9
11
28
Recursividade: o que faz?
void f(int n, int m) {
 if ( n < m ) {
 f(n+2, m);
 printf("%d\n", n);
 } else {
 printf("%d\n", n);
 }
}
int main() {
 f(1, 10);
 return 0;
}
void f(int n, int m) {
 if ( n < m ) {
 printf("%d\n", n);
 f(n+2, m);
 } else {
 printf("%d\n", n);
 }
}
int main() {
 f(1, 10);
 return 0;
}
~$./a.out
1
3
5
7
9
11
~$./a.out
11
9
7
5
3
1
29
Recursividade: exercício, potência
30
int pot(int a, int b) {
 if ( b == 1 )
 return a;
 else
 return a * pot(a, b-1);
}
Recursividade: exercício, potência
31
int main( ){
 int p;
 p=pot(5,3);
 printf("%d\n", p);
 return 0;
}
int pot(int a, int b) {
 if ( b == 1 )
 return a;
 else
 return a * pot(a, b-1);
}
Recursividade: exercício, potência
int pot( 5, 3) {
 if ( 3 == 1 )
 return 5;
 else
 return 5*pot(5, 3-1);
}
int pot( 5, 2) {
 if ( 2 == 1 )
 return 5;
 else
 return 5*pot(5, 2-1);
}
int pot( 5, 1) {
 if ( 1 == 1 )
 return 5;
 else
 return 5*pot(5, 1-1);
}
525
125
32
Vantagens da Recursividade:
- Código mais compacto;
- Especialmente conveniente para estruturas de dados definidas 
recursivamente, tais como árvores (serão estudadas na disciplina de 
Estruturas de Dados);
- Código pode ser mais fácil de entender;
- Implementação mais imediata de funções matemáticas que já são 
definidas recursivamente.
33
Desvantagens da Recursividade:
- Maior ocupação de memória;
- Maior tempo de processamento.
34
Recursividade: exercício, fibonacci
Fibonacci:
Fib(0) = 0
Fib(1) = 1
Fib(n) = Fib(n-1) + Fib(n-2)
35
Recursividade: exercício, fibonacci
Fibonacci:
Fib(0) = 0
Fib(1) = 1
Fib(n) = Fib(n-1) + Fib(n-2)
unsigned int Fib(unsigned int n) {
 if (n == 0)
 return 0;
 else
 if (n == 1)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
36
unsigned int Fib(unsigned int n) {
 if (n == 0)
 return 0;
 else
 if (n == 1)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
int main(){
 int f;
 f=Fib(5);
 printf("%d\n", f);
 return 0;
}
Recursividade: exercício, fibonacci
f = Fib(5);
37
unsigned int Fib(unsigned int n) {
 if (n == 0)
 return 0;
 else
 if (n == 1)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
int main(){
 int f;
 f=Fib(5);
 printf("%d\n", f);
 return 0;
}
Recursividade: exercício, fibonacci
return Fib(4) + Fib(3)
f = Fib(5);
38
unsigned int Fib(unsigned int n) {
 if (n == 0)
 return 0;
 else
 if (n == 1)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
int main(){
 int f;
 f=Fib(5);
 printf("%d\n", f);
 return 0;
}
Recursividade: exercício, fibonacci
return Fib(3) + Fib(2)
return Fib(4) + Fib(3)
f = Fib(5);
39
unsigned int Fib(unsigned int n) {
 if (n == 0)
 return 0;
 else
 if (n == 1)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
int main(){
 int f;
 f=Fib(5);
 printf("%d\n", f);
 return 0;
}
Recursividade: exercício, fibonacci
return Fib(2) + Fib(1)
return Fib(3) + Fib(2)
return Fib(4) + Fib(3)
f = Fib(5);
40
unsigned int Fib(unsigned int n) {
 if (n == 0)
 return 0;
 else
 if (n == 1)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
int main(){
 int f;
 f=Fib(5);
 printf("%d\n", f);
 return 0;
}
Recursividade: exercício, fibonacci
return Fib(1) + Fib(0)
return Fib(2) + Fib(1)
return Fib(3) + Fib(2)
return Fib(4) + Fib(3)
f = Fib(5);
41
unsigned int Fib(unsigned int n) {
 if (n == 0)
 return 0;
 else
 if (n == 1)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
int main(){
 int f;
 f=Fib(5);
 printf("%d\n", f);
 return 0;
}
Recursividade: exercício, fibonacci
1
return 1
return 1 + Fib(0)
return Fib(2) + Fib(1)
return Fib(3) + Fib(2)
return Fib(4) + Fib(3)
f = Fib(5);
42
unsigned int Fib(unsigned int n) {
 if (n == 0)
 return 0;
 else
 if (n == 1)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
int main(){
 int f;
 f=Fib(5);
 printf("%d\n", f);
 return 0;
}
Recursividade: exercício, fibonacci
1 0
return 0
return 1 + 0
return Fib(2) + Fib(1)
return Fib(3) + Fib(2)
return Fib(4) + Fib(3)
f = Fib(5);
43
unsigned int Fib(unsigned int n) {
 if (n == 0)
 return 0;
 else
 if (n == 1)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
int main(){
 int f;
 f=Fib(5);
 printf("%d\n", f);
 return 0;
}
Recursividade: exercício, fibonacci
1 0
1
return 1
return 1 + Fib(1)
return Fib(3) + Fib(2)
return Fib(4) + Fib(3)
f = Fib(5);
44
unsigned int Fib(unsigned int n) {
 if (n == 0)
 return 0;
 else
 if (n == 1)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
int main(){
 int f;
 f=Fib(5);
 printf("%d\n", f);
 return 0;
}
Recursividade: exercício, fibonacci
1 0
1 1
return 1
return 1 + 1
return Fib(3) + Fib(2)
return Fib(4) + Fib(3)
f = Fib(5);
45
unsigned int Fib(unsigned int n) {
 if (n == 0)
 return 0;
 else
 if (n == 1)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
int main(){
 int f;
 f=Fib(5);
 printf("%d\n", f);
 return 0;
}
Recursividade: exercício, fibonacci
1 0
1 1
2
return 2
return 2 + Fib(2)
return Fib(4) + Fib(3)
f = Fib(5);
46
unsigned int Fib(unsigned int n) {
 if (n == 0)
 return 0;
 else
 if (n == 1)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
int main(){
 int f;
 f=Fib(5);
 printf("%d\n", f);
 return 0;
}
Recursividade: exercício, fibonacci
1 0
1 1
2
return Fib(1) + Fib(0)
return 2 + Fib(2)
return Fib(4) + Fib(3)
f = Fib(5);
47
unsigned int Fib(unsigned int n) {
 if (n == 0)
 return 0;
 else
 if (n == 1)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
int main(){
 int f;
 f=Fib(5);
 printf("%d\n", f);
 return0;
}
Recursividade: exercício, fibonacci
1 0
1 1
2
1
return 1
return 1 + Fib(0)
return 2 + Fib(2)
return Fib(4) + Fib(3)
f = Fib(5);
48
unsigned int Fib(unsigned int n) {
 if (n == 0)
 return 0;
 else
 if (n == 1)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
int main(){
 int f;
 f=Fib(5);
 printf("%d\n", f);
 return 0;
}
Recursividade: exercício, fibonacci
1 0
1 1
2
1 0
return 0
return 1 + 0
return 2 + Fib(2)
return Fib(4) + Fib(3)
f = Fib(5);
49
unsigned int Fib(unsigned int n) {
 if (n == 0)
 return 0;
 else
 if (n == 1)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
int main(){
 int f;
 f=Fib(5);
 printf("%d\n", f);
 return 0;
}
Recursividade: exercício, fibonacci
1 0
1 1
2
1 0
1
return 1
return 2 + 1
return Fib(4) + Fib(3)
f = Fib(5);
50
unsigned int Fib(unsigned int n) {
 if (n == 0)
 return 0;
 else
 if (n == 1)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
int main(){
 int f;
 f=Fib(5);
 printf("%d\n", f);
 return 0;
}
Recursividade: exercício, fibonacci
1 0
1 1
2
1 0
1
3
return 3
return 3 + Fib(3)
f = Fib(5);
51
unsigned int Fib(unsigned int n) {
 if (n == 0)
 return 0;
 else
 if (n == 1)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
int main(){
 int f;
 f=Fib(5);
 printf("%d\n", f);
 return 0;
}
Recursividade: exercício, fibonacci
1 0
1 1
2
1 0
1
3
return Fib(2) + Fib(1)
return 3 + Fib(3)
f = Fib(5);
52
unsigned int Fib(unsigned int n) {
 if (n == 0)
 return 0;
 else
 if (n == 1)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
int main(){
 int f;
 f=Fib(5);
 printf("%d\n", f);
 return 0;
}
Recursividade: exercício, fibonacci
1 0
1 1
2
1 0
1
3
return Fib(1) + Fib(0)
return Fib(2) + Fib(1)
return 3 + Fib(3)
f = Fib(5);
53
unsigned int Fib(unsigned int n) {
 if (n == 0)
 return 0;
 else
 if (n == 1)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
int main(){
 int f;
 f=Fib(5);
 printf("%d\n", f);
 return 0;
}
Recursividade: exercício, fibonacci
1 0
1 1
2
1 0
1
3
1
return 1
return 1 + Fib(0)
return Fib(2) + Fib(1)
return 3 + Fib(3)
f = Fib(5);
54
unsigned int Fib(unsigned int n) {
 if (n == 0)
 return 0;
 else
 if (n == 1)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
int main(){
 int f;
 f=Fib(5);
 printf("%d\n", f);
 return 0;
}
Recursividade: exercício, fibonacci
1 0
1 1
2
1 0
1
3
1 0
return 0
return 1 + 0
return Fib(2) + Fib(1)
return 3 + Fib(3)
f = Fib(5);
55
unsigned int Fib(unsigned int n) {
 if (n == 0)
 return 0;
 else
 if (n == 1)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
int main(){
 int f;
 f=Fib(5);
 printf("%d\n", f);
 return 0;
}
Recursividade: exercício, fibonacci
1 0
1 1
2
1 0
1
3
1 0
1
return 1
return 1 + Fib(1)
return 3 + Fib(3)
f = Fib(5);
56
unsigned int Fib(unsigned int n) {
 if (n == 0)
 return 0;
 else
 if (n == 1)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
int main(){
 int f;
 f=Fib(5);
 printf("%d\n", f);
 return 0;
}
Recursividade: exercício, fibonacci
1 0
1 1
2
1 0
1
3
1 0
1 1
return 1
return 1 + 1
return 3 + Fib(3)
f = Fib(5);
57
unsigned int Fib(unsigned int n) {
 if (n == 0)
 return 0;
 else
 if (n == 1)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
int main(){
 int f;
 f=Fib(5);
 printf("%d\n", f);
 return 0;
}
Recursividade: exercício, fibonacci
1 0
1 1
2
1 0
1
3
1 0
1 1
2
return 2
return 3 + 2
f = Fib(5);
58
unsigned int Fib(unsigned int n) {
 if (n == 0)
 return 0;
 else
 if (n == 1)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
int main(){
 int f;
 f=Fib(5);
 printf("%d\n", f);
 return 0;
}
Recursividade: exercício, fibonacci
1 0
1 1
2
1 0
1
3
1 0
1 1
2
5
return 5
f = 5;
59
unsigned int Fib(unsigned int n) {
 if (n == 0)
 return 0;
 else
 if (n == 1)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
int main(){
 int f;
 f=Fib(5);
 printf("%d\n", f);
 return 0;
}
Recursividade: exercício, fibonacci
REDUNDANTE!
60
unsigned int Fib(unsigned int n) {
 if (n == 0)
 return 0;
 else
 if (n == 1)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
int main(){
 int f;
 f=Fib(5);
 printf("%d\n", f);
 return 0;
}
Recursividade: exercício, fibonacci
REDUNDANTE!
REDUNDANTE!
61
unsigned int Fib(unsigned int n) {
 if (n == 0)
 return 0;
 else
 if (n == 1)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
int main(){
 int f;
 f=Fib(5);
 printf("%d\n", f);
 return 0;
}
Recursividade: exercício, fibonacci
REDUNDANTE!
REDUNDANTE!
62
Desempenho poderia ser melhorado com o uso de 
métodos de memoization (fora do escopo da 
disciplina)
Recursividade: exercício, somatório
Em uma lista L={l
1
, l
2
, l
3
, …, l
n
}, onde l
1
 é o primeiro elemento e
l
n
 é o último.
O somatório de todos os elementos da lista pode ser dado por:
 Implemente esta recorrência para calcular o somatório de uma lista.
63
Recursividade: exercício, somatório
int somatorio(int lista[], int tamanho) {
 if ( tamanho == 0 )
 return 0;
 else
 return lista[tamanho-1] + somatorio(lista, tamanho-1);
}
64
#include <stdio.h>
#define N 10
int somatorio(int lista[], int tamanho) {
 if ( tamanho == 0 )
 return 0;
 else
 return lista[tamanho-1] + somatorio(lista, tamanho-1);
}
int main() {
 int numeros[N], i;
 for (i=0; i<N; i++)
 scanf("%d", &numeros[i]);
 printf("soma: %d\n", somatorio(numeros, N));
 return 0;
}
Recursividade: exercício, somatório
~$./a.out 
4
1
3
7
5
6
2
1
2
3
soma: 34
65
#include <stdio.h>
#define N 10
int somatorio(int lista[], int tamanho) {
 if ( tamanho == 0 )
 return 0;
 else
 return lista[tamanho-1] + somatorio(lista, tamanho-1);
}
int main() {
 int numeros[N], i;
 for (i=0; i<N; i++)
 scanf("%d", &numeros[i]);
 printf("soma: %d\n", somatorio(numeros, N));
 return 0;
}
Recursividade: exercício, somatório
~$./a.out 
4
1
3
7
5
6
2
1
2
3
soma: 34
return 0;
4+somatorio(lista, 0);
1+somatorio(lista, 1);
3+somatorio(lista, 2);
7+somatorio(lista, 3);
5+somatorio(lista, 4);
6+somatorio(lista, 5);
2+somatorio(lista, 6);
1+somatorio(lista, 7);
2+somatorio(lista, 8);
3+somatorio(lista, 9);
somatorio(lista, 10)
66
Recursão: uma palavra é palíndroma se
- suas extremidades forem iguais, e
- seu núcleo for uma palavra palíndroma (ou se não tiver núcleo)
Uma palavra é palíndroma quando seu sentido é o mesmo, quer se leia da 
esquerda para direita ou direita para esquerda. Ex.: ana, mirim, osso, reviver
Recursividade: exercício, palíndroma
67
EhPalíndroma(palavra)
1. Se primeira e última letras da palavra forem diferentes
2. Retorna FALSO
3. Se palavra tem núcleo
4. Retorna EhPalíndroma(palavra sem primeira e última letras)
5. Senão
6. Retorna VERDADEIRO
Recursividade: exercício, palíndroma
68
Recursividade: exercício, palíndroma
typedef enum {TRUE = 1, FALSE = 0} bool_t;
bool_t EhPalindroma(char palavra[], int prim, int ult) {
 if (palavra[prim] != palavra[ult])
 return FALSE;
 // Se a posição da primeira letra não for igual ou uma
 // anterior à posição da última, ainda tem núcleo
 if (prim < (ult-1))
 return EhPalindroma(palavra, prim+1, ult-1);
 else
 return TRUE;
} 69
Recursividade: exercício, palíndroma (versão 2)
int palindroma (char s[ ]) // retorna 1, se a string "s" for palindroma, ou 0, se não for
{
char s1[strlen(s)-2]; // define outra string, que recebera a parte central de "s"
int eh_palind; // saida da funcao
if (s[0] == s[strlen(s)-1]) { // compara a primeira e ultima letras
if (( strlen(s) == 1 ) || ( strlen(s) == 2)) // se a string tiver 1 ou2 letras, retorna 1
eh_palind = 1;
else {
/* monta uma nova string tirando os 2 extremos */
strncpy (s1, &s[1], strlen(s) - 2);
s1[strlen(s) - 2] = '\0'; // coloca o simbolo de final de string
/* chamada recursiva para a substring central */
eh_palind = palindroma (s1);
}
}
else // retorna zero se o teste falhar para alguma substring
eh_palind = 0;
return eh_palind;
}
70
int main (void)
{
char str[40];
gets(str);
if (palindroma(str)==1)
 printf("%s eh palindroma\n", str);
else
 printf("%s NAO eh palindroma\n", str);
return 0;
}
typedef enum {TRUE = 1, FALSE = 0} bool_t;
bool_t EhPar(unsigned int n) {
 if (n == 0)
 return TRUE;
 else
 return EhImpar(n - 1);
}
bool_t EhImpar(unsigned int n) {
 if (n == 0)
 return FALSE;
 else
 return EhPar(n - 1);
}
Quando duas funções interdependem nas suas definições.
Exemplo:
Recursividade: recursão mútua
71
#define N 1000
int BuscaLinearIter(int lista[N], int elem)
{
 int ind = 0, encontrou = 0;
 while (ind < N && !encontrou) {
 if (elem == lista[ind])
 encontrou = 1;
 else
 ind++;
 }
 return ind;
}
Recursividade: busca em lista ordenada
Encontre determinado elemento em uma lista ordenada e retorne seu índice.
Método linear:
- Verifique os elementos da 
lista, um a um
- Pare quando encontrar o 
elemento e retorne a sua 
posição
72
#define N 1000
int BuscaLinearIter(int lista[N], int elem)
{
 int ind = 0, encontrou = 0;
 while (ind < N && !encontrou) {
 if (elem == lista[ind])
 encontrou = 1;
 else
 ind++;
 }
 return ind;
}
Recursividade: busca em lista ordenada
Encontre determinado elemento em uma lista ordenada e retorne seu índice.
Método linear:
- Verifique os elementos da 
lista, um a um
- Pare quando encontrar o 
elemento e retorne a sua 
posição
Esse é o método mais eficiente?
Qual o modo mais natural de se 
fazer uma busca em uma lista 
ordenada?
73
Recursividade: busca em lista ordenada
Abigail Remígio
Adelina Azambuja
Adelina Verguero
Adão Simão
Adélia Beltrán
Agostinho Lages
Alarico Quinzeiro
Aldo Vides
Aldonça Sampaio
Alvito Tomé
Alzira Pino
Amandio Ruela
Américo Freixo
Anselmo Peres
Átila Quinta
Augusta Caiado
Balduíno Cruz
Barnabé Simão
Bartira Lemes
Belchior Mendonça
Bento Inácio
Burtira Imperial
Caetano Saloio
Calisto Maciel
Carla Carvalhal
Carlos Ferreira
Carlos Marmou
Cauã Núñez
Caím Ribas
Crispim Ríos
Cássio Siqueira
Célia Pasos
Deise Meira
Delfina Cayubi
Dinarte Barboza
Domingos Neiva
Débora Oliveira
Eliseu Pacheco
Ema Figueroa
Emiliana Cortesão
Eugénio Pires
Ezequiel Mayor
Feliciana Ferraz
Feliciana Lemes
Florbela Medeiros
Fábia Rego
Gedeão Villena
Gerardo Lago
Glauco Moreyra
Gonçalo Camarinho
Gonçalo Capucho
Greice Sampaio
Gui Freixo
Guido Bernardes
Guiomar Vargas
Gustavo Dâmaso
Heitor Quintal
Honório Carneiro
Isaac, Isaque Benevides
Israel Paranaguá
Jaci Toledo
Jacir Bezerril
Janaína Hollanda
Jonas Vilas Boas
Jorgina Quirós
Josefa Galindo
Laurinda Pires
Letícia Sampaio
Luciano Regalado
Lucrécia Ribas
Luísa Setúbal
Lázaro Tigre
Lénia Abreu
Lídia Eiró
Lúcia Díaz
Magali Souza
Mamede Rivas
Marcos Juruna
Mariano Mata
Marli Marmou
Marília Aquino
Marília Corrêa
Márcio Zarco
Nazaré Coello
Olívia Brum
Ordonho Paranhos
Orestes Vale
Paula Cardin
Paula Toscano
Penélope Loureiro
Potira Quiroga
Raimundo Briones
Remo Lóio
Ricardo Imbassaí
Rita Vicario
Rogério Natal
Romano Ferrão
Roque Cabeza de Vaca
Rosalina Garrau
Rubim Muñiz
Rui Valério
Sancha Borba
Simeão Areosa
Siquenique Nogueira
Solange Mattos
Sonás Rebelo
Suniário Barateiro
Telma Ramires
Tibúrcio Tabajara
Tomás Valle
Tomé Viégas
Trajano Sampaio
Ubaldo Arruda
Virgílio Casado
Viviana Almeida
Viviana Villaça
Vlademiro Barbosa
Vlademiro Beltrán
Xerxes Carijó
Zita Tabosa
Onde está Heitor Quintal?
74
Recursividade: busca em lista ordenada
Abigail Remígio
Adelina Azambuja
Adelina Verguero
Adão Simão
Adélia Beltrán
Agostinho Lages
Alarico Quinzeiro
Aldo Vides
Aldonça Sampaio
Alvito Tomé
Alzira Pino
Amandio Ruela
Américo Freixo
Anselmo Peres
Átila Quinta
Augusta Caiado
Balduíno Cruz
Barnabé Simão
Bartira Lemes
Belchior Mendonça
Bento Inácio
Burtira Imperial
Caetano Saloio
Calisto Maciel
Carla Carvalhal
Carlos Ferreira
Carlos Marmou
Cauã Núñez
Caím Ribas
Crispim Ríos
Cássio Siqueira
Célia Pasos
Deise Meira
Delfina Cayubi
Dinarte Barboza
Domingos Neiva
Débora Oliveira
Eliseu Pacheco
Ema Figueroa
Emiliana Cortesão
Eugénio Pires
Ezequiel Mayor
Feliciana Ferraz
Feliciana Lemes
Florbela Medeiros
Fábia Rego
Gedeão Villena
Gerardo Lago
Glauco Moreyra
Gonçalo Camarinho
Gonçalo Capucho
Greice Sampaio
Gui Freixo
Guido Bernardes
Guiomar Vargas
Gustavo Dâmaso
Heitor Quintal
Honório Carneiro
Isaac, Isaque Benevides
Israel Paranaguá
Jaci Toledo
Jacir Bezerril
Janaína Hollanda
Jonas Vilas Boas
Jorgina Quirós
Josefa Galindo
Laurinda Pires
Letícia Sampaio
Luciano Regalado
Lucrécia Ribas
Luísa Setúbal
Lázaro Tigre
Lénia Abreu
Lídia Eiró
Lúcia Díaz
Magali Souza
Mamede Rivas
Marcos Juruna
Mariano Mata
Marli Marmou
Marília Aquino
Marília Corrêa
Márcio Zarco
Nazaré Coello
Olívia Brum
Ordonho Paranhos
Orestes Vale
Paula Cardin
Paula Toscano
Penélope Loureiro
Potira Quiroga
Raimundo Briones
Remo Lóio
Ricardo Imbassaí
Rita Vicario
Rogério Natal
Romano Ferrão
Roque Cabeza de Vaca
Rosalina Garrau
Rubim Muñiz
Rui Valério
Sancha Borba
Simeão Areosa
Siquenique Nogueira
Solange Mattos
Sonás Rebelo
Suniário Barateiro
Telma Ramires
Tibúrcio Tabajara
Tomás Valle
Tomé Viégas
Trajano Sampaio
Ubaldo Arruda
Virgílio Casado
Viviana Almeida
Viviana Villaça
Vlademiro Barbosa
Vlademiro Beltrán
Xerxes Carijó
Zita Tabosa
Onde está Heitor Quintal?
H > E, está mais adiante...
75
Recursividade: busca em lista ordenada
Abigail Remígio
Adelina Azambuja
Adelina Verguero
Adão Simão
Adélia Beltrán
Agostinho Lages
Alarico Quinzeiro
Aldo Vides
Aldonça Sampaio
Alvito Tomé
Alzira Pino
Amandio Ruela
Américo Freixo
Anselmo Peres
Átila Quinta
Augusta Caiado
Balduíno Cruz
Barnabé Simão
Bartira Lemes
Belchior Mendonça
Bento Inácio
Burtira Imperial
Caetano Saloio
Calisto Maciel
Carla Carvalhal
Carlos Ferreira
Carlos Marmou
Cauã Núñez
Caím Ribas
Crispim Ríos
Cássio Siqueira
Célia Pasos
Deise Meira
Delfina Cayubi
Dinarte Barboza
Domingos Neiva
Débora Oliveira
Eliseu Pacheco
Ema Figueroa
Emiliana Cortesão
Eugénio Pires
Ezequiel Mayor
Feliciana Ferraz
Feliciana Lemes
Florbela Medeiros
Fábia Rego
Gedeão Villena
Gerardo Lago
Glauco Moreyra
Gonçalo Camarinho
Gonçalo Capucho
Greice Sampaio
Gui Freixo
Guido Bernardes
Guiomar Vargas
Gustavo Dâmaso
Heitor Quintal
Honório Carneiro
Isaac, Isaque Benevides
Israel Paranaguá
Jaci Toledo
Jacir Bezerril
Janaína Hollanda
Jonas Vilas Boas
Jorgina Quirós
Josefa Galindo
Laurinda Pires
Letícia Sampaio
Luciano Regalado
Lucrécia Ribas
Luísa Setúbal
Lázaro Tigre
Lénia Abreu
Lídia Eiró
Lúcia Díaz
Magali Souza
Mamede Rivas
Marcos Juruna
Mariano Mata
Marli Marmou
Marília Aquino
Marília Corrêa
Márcio Zarco
Nazaré Coello
Olívia Brum
Ordonho Paranhos
Orestes Vale
Paula Cardin
Paula Toscano
Penélope Loureiro
Potira Quiroga
Raimundo Briones
Remo Lóio
Ricardo Imbassaí
Rita Vicario
Rogério Natal
Romano Ferrão
Roque Cabeza de Vaca
Rosalina Garrau
Rubim Muñiz
Rui Valério
Sancha Borba
Simeão Areosa
Siquenique Nogueira
Solange Mattos
Sonás Rebelo
Suniário Barateiro
Telma Ramires
Tibúrcio Tabajara
Tomás Valle
Tomé Viégas
Trajano Sampaio
Ubaldo Arruda
Virgílio Casado
Viviana Almeida
Viviana Villaça
Vlademiro Barbosa
Vlademiro Beltrán
Xerxes Carijó
Zita Tabosa
Onde está Heitor Quintal?
H < L, está mais atrás...
76
Recursividade: busca em lista ordenada
Abigail Remígio
Adelina Azambuja
Adelina Verguero
Adão Simão
Adélia Beltrán
Agostinho Lages
Alarico Quinzeiro
Aldo Vides
Aldonça Sampaio
Alvito Tomé
Alzira Pino
Amandio Ruela
Américo Freixo
Anselmo Peres
Átila Quinta
Augusta Caiado
Balduíno Cruz
Barnabé Simão
Bartira Lemes
Belchior Mendonça
Bento Inácio
Burtira Imperial
Caetano Saloio
Calisto Maciel
Carla Carvalhal
Carlos Ferreira
Carlos Marmou
Cauã NúñezCaím Ribas
Crispim Ríos
Cássio Siqueira
Célia Pasos
Deise Meira
Delfina Cayubi
Dinarte Barboza
Domingos Neiva
Débora Oliveira
Eliseu Pacheco
Ema Figueroa
Emiliana Cortesão
Eugénio Pires
Ezequiel Mayor
Feliciana Ferraz
Feliciana Lemes
Florbela Medeiros
Fábia Rego
Gedeão Villena
Gerardo Lago
Glauco Moreyra
Gonçalo Camarinho
Gonçalo Capucho
Greice Sampaio
Gui Freixo
Guido Bernardes
Guiomar Vargas
Gustavo Dâmaso
Heitor Quintal
Honório Carneiro
Isaac, Isaque Benevides
Israel Paranaguá
Jaci Toledo
Jacir Bezerril
Janaína Hollanda
Jonas Vilas Boas
Jorgina Quirós
Josefa Galindo
Laurinda Pires
Letícia Sampaio
Luciano Regalado
Lucrécia Ribas
Luísa Setúbal
Lázaro Tigre
Lénia Abreu
Lídia Eiró
Lúcia Díaz
Magali Souza
Mamede Rivas
Marcos Juruna
Mariano Mata
Marli Marmou
Marília Aquino
Marília Corrêa
Márcio Zarco
Nazaré Coello
Olívia Brum
Ordonho Paranhos
Orestes Vale
Paula Cardin
Paula Toscano
Penélope Loureiro
Potira Quiroga
Raimundo Briones
Remo Lóio
Ricardo Imbassaí
Rita Vicario
Rogério Natal
Romano Ferrão
Roque Cabeza de Vaca
Rosalina Garrau
Rubim Muñiz
Rui Valério
Sancha Borba
Simeão Areosa
Siquenique Nogueira
Solange Mattos
Sonás Rebelo
Suniário Barateiro
Telma Ramires
Tibúrcio Tabajara
Tomás Valle
Tomé Viégas
Trajano Sampaio
Ubaldo Arruda
Virgílio Casado
Viviana Almeida
Viviana Villaça
Vlademiro Barbosa
Vlademiro Beltrán
Xerxes Carijó
Zita Tabosa
Onde está Heitor Quintal?
H < J, está mais atrás...
77
Feliciana Ferraz
Feliciana Lemes
Florbela Medeiros
Fábia Rego
Gedeão Villena
Gerardo Lago
Glauco Moreyra
Gonçalo Camarinho
Gonçalo Capucho
Greice Sampaio
Gui Freixo
Guido Bernardes
Guiomar Vargas
Gustavo Dâmaso
Heitor Quintal
Honório Carneiro
Isaac, Isaque Benevides
Israel Paranaguá
Jaci Toledo
Jacir Bezerril
Janaína Hollanda
Recursividade: busca em lista ordenada
Abigail Remígio
Adelina Azambuja
Adelina Verguero
Adão Simão
Adélia Beltrán
Agostinho Lages
Alarico Quinzeiro
Aldo Vides
Aldonça Sampaio
Alvito Tomé
Alzira Pino
Amandio Ruela
Américo Freixo
Anselmo Peres
Átila Quinta
Augusta Caiado
Balduíno Cruz
Barnabé Simão
Bartira Lemes
Belchior Mendonça
Bento Inácio
Burtira Imperial
Caetano Saloio
Calisto Maciel
Carla Carvalhal
Carlos Ferreira
Carlos Marmou
Cauã Núñez
Caím Ribas
Crispim Ríos
Cássio Siqueira
Célia Pasos
Deise Meira
Delfina Cayubi
Dinarte Barboza
Domingos Neiva
Débora Oliveira
Eliseu Pacheco
Ema Figueroa
Emiliana Cortesão
Eugénio Pires
Ezequiel Mayor
Jonas Vilas Boas
Jorgina Quirós
Josefa Galindo
Laurinda Pires
Letícia Sampaio
Luciano Regalado
Lucrécia Ribas
Luísa Setúbal
Lázaro Tigre
Lénia Abreu
Lídia Eiró
Lúcia Díaz
Magali Souza
Mamede Rivas
Marcos Juruna
Mariano Mata
Marli Marmou
Marília Aquino
Marília Corrêa
Márcio Zarco
Nazaré Coello
Olívia Brum
Ordonho Paranhos
Orestes Vale
Paula Cardin
Paula Toscano
Penélope Loureiro
Potira Quiroga
Raimundo Briones
Remo Lóio
Ricardo Imbassaí
Rita Vicario
Rogério Natal
Romano Ferrão
Roque Cabeza de Vaca
Rosalina Garrau
Rubim Muñiz
Rui Valério
Sancha Borba
Simeão Areosa
Siquenique Nogueira
Solange Mattos
Sonás Rebelo
Suniário Barateiro
Telma Ramires
Tibúrcio Tabajara
Tomás Valle
Tomé Viégas
Trajano Sampaio
Ubaldo Arruda
Virgílio Casado
Viviana Almeida
Viviana Villaça
Vlademiro Barbosa
Vlademiro Beltrán
Xerxes Carijó
Zita Tabosa
Onde está Heitor Quintal?
H > G, está mais adiante...
78
Feliciana Ferraz
Feliciana Lemes
Florbela Medeiros
Fábia Rego
Gedeão Villena
Gerardo Lago
Glauco Moreyra
Gonçalo Camarinho
Gonçalo Capucho
Greice Sampaio
Gui Freixo
Guido Bernardes
Guiomar Vargas
Gustavo Dâmaso
Heitor Quintal
Honório Carneiro
Isaac, Isaque Benevides
Israel Paranaguá
Jaci Toledo
Jacir Bezerril
Janaína Hollanda
Recursividade: busca em lista ordenada
Abigail Remígio
Adelina Azambuja
Adelina Verguero
Adão Simão
Adélia Beltrán
Agostinho Lages
Alarico Quinzeiro
Aldo Vides
Aldonça Sampaio
Alvito Tomé
Alzira Pino
Amandio Ruela
Américo Freixo
Anselmo Peres
Átila Quinta
Augusta Caiado
Balduíno Cruz
Barnabé Simão
Bartira Lemes
Belchior Mendonça
Bento Inácio
Burtira Imperial
Caetano Saloio
Calisto Maciel
Carla Carvalhal
Carlos Ferreira
Carlos Marmou
Cauã Núñez
Caím Ribas
Crispim Ríos
Cássio Siqueira
Célia Pasos
Deise Meira
Delfina Cayubi
Dinarte Barboza
Domingos Neiva
Débora Oliveira
Eliseu Pacheco
Ema Figueroa
Emiliana Cortesão
Eugénio Pires
Ezequiel Mayor
Jonas Vilas Boas
Jorgina Quirós
Josefa Galindo
Laurinda Pires
Letícia Sampaio
Luciano Regalado
Lucrécia Ribas
Luísa Setúbal
Lázaro Tigre
Lénia Abreu
Lídia Eiró
Lúcia Díaz
Magali Souza
Mamede Rivas
Marcos Juruna
Mariano Mata
Marli Marmou
Marília Aquino
Marília Corrêa
Márcio Zarco
Nazaré Coello
Olívia Brum
Ordonho Paranhos
Orestes Vale
Paula Cardin
Paula Toscano
Penélope Loureiro
Potira Quiroga
Raimundo Briones
Remo Lóio
Ricardo Imbassaí
Rita Vicario
Rogério Natal
Romano Ferrão
Roque Cabeza de Vaca
Rosalina Garrau
Rubim Muñiz
Rui Valério
Sancha Borba
Simeão Areosa
Siquenique Nogueira
Solange Mattos
Sonás Rebelo
Suniário Barateiro
Telma Ramires
Tibúrcio Tabajara
Tomás Valle
Tomé Viégas
Trajano Sampaio
Ubaldo Arruda
Virgílio Casado
Viviana Almeida
Viviana Villaça
Vlademiro Barbosa
Vlademiro Beltrán
Xerxes Carijó
Zita Tabosa
Onde está Heitor Quintal?
79
Feliciana Ferraz
Feliciana Lemes
Florbela Medeiros
Fábia Rego
Gedeão Villena
Gerardo Lago
Glauco Moreyra
Gonçalo Camarinho
Gonçalo Capucho
Greice Sampaio
Gui Freixo
Guido Bernardes
Guiomar Vargas
Gustavo Dâmaso
Heitor Quintal
Honório Carneiro
Isaac, Isaque Benevides
Israel Paranaguá
Jaci Toledo
Jacir Bezerril
Janaína Hollanda
Recursividade: busca em lista ordenada
Abigail Remígio
Adelina Azambuja
Adelina Verguero
Adão Simão
Adélia Beltrán
Agostinho Lages
Alarico Quinzeiro
Aldo Vides
Aldonça Sampaio
Alvito Tomé
Alzira Pino
Amandio Ruela
Américo Freixo
Anselmo Peres
Átila Quinta
Augusta Caiado
Balduíno Cruz
Barnabé Simão
Bartira Lemes
Belchior Mendonça
Bento Inácio
Burtira Imperial
Caetano Saloio
Calisto Maciel
Carla Carvalhal
Carlos Ferreira
Carlos Marmou
Cauã Núñez
Caím Ribas
Crispim Ríos
Cássio Siqueira
Célia Pasos
Deise Meira
Delfina Cayubi
Dinarte Barboza
Domingos Neiva
Débora Oliveira
Eliseu Pacheco
Ema Figueroa
Emiliana Cortesão
Eugénio Pires
Ezequiel Mayor
Jonas Vilas Boas
Jorgina Quirós
Josefa Galindo
Laurinda Pires
Letícia Sampaio
Luciano Regalado
Lucrécia Ribas
Luísa Setúbal
Lázaro Tigre
Lénia Abreu
Lídia Eiró
Lúcia Díaz
Magali Souza
Mamede Rivas
Marcos Juruna
Mariano Mata
Marli Marmou
Marília Aquino
Marília Corrêa
Márcio Zarco
Nazaré Coello
Olívia Brum
Ordonho Paranhos
Orestes Vale
Paula Cardin
Paula Toscano
Penélope Loureiro
Potira Quiroga
Raimundo Briones
Remo Lóio
Ricardo Imbassaí
Rita Vicario
Rogério Natal
Romano Ferrão
Roque Cabeza de Vaca
Rosalina Garrau
Rubim Muñiz
Rui Valério
Sancha Borba
Simeão Areosa
Siquenique Nogueira
Solange Mattos
Sonás Rebelo
Suniário Barateiro
Telma Ramires
Tibúrcio Tabajara
Tomás Valle
Tomé Viégas
Trajano Sampaio
Ubaldo Arruda
Virgílio Casado
Viviana Almeida
Viviana Villaça
Vlademiro Barbosa
Vlademiro Beltrán
Xerxes Carijó
Zita Tabosa
Onde está Heitor Quintal?
A cada passo são selecionadas 
posições na lista que indicam qual 
parte dela pode ser ignorada e 
qual parte precisa ser avaliada.
80
Feliciana Ferraz
Feliciana Lemes
Florbela Medeiros
Fábia Rego
Gedeão Villena
Gerardo Lago
Glauco Moreyra
Gonçalo Camarinho
Gonçalo Capucho
Greice Sampaio
Gui Freixo
Guido Bernardes
Guiomar Vargas
Gustavo Dâmaso
Heitor Quintal
Honório Carneiro
Isaac, Isaque Benevides
Israel Paranaguá
Jaci Toledo
Jacir Bezerril
Janaína Hollanda
Recursividade: busca em lista ordenada
Abigail Remígio
Adelina Azambuja
Adelina Verguero
Adão Simão
Adélia Beltrán
Agostinho Lages
Alarico Quinzeiro
Aldo Vides
Aldonça Sampaio
Alvito Tomé
Alzira Pino
Amandio Ruela
Américo Freixo
Anselmo Peres
Átila Quinta
Augusta Caiado
Balduíno Cruz
Barnabé Simão
Bartira Lemes
Belchior Mendonça
Bento Inácio
Burtira Imperial
Caetano Saloio
Calisto Maciel
Carla Carvalhal
Carlos Ferreira
Carlos Marmou
Cauã Núñez
Caím Ribas
Crispim Ríos
Cássio Siqueira
Célia Pasos
Deise Meira
Delfina Cayubi
Dinarte Barboza
Domingos Neiva
Débora Oliveira
EliseuPacheco
Ema Figueroa
Emiliana Cortesão
Eugénio Pires
Ezequiel Mayor
Jonas Vilas Boas
Jorgina Quirós
Josefa Galindo
Laurinda Pires
Letícia Sampaio
Luciano Regalado
Lucrécia Ribas
Luísa Setúbal
Lázaro Tigre
Lénia Abreu
Lídia Eiró
Lúcia Díaz
Magali Souza
Mamede Rivas
Marcos Juruna
Mariano Mata
Marli Marmou
Marília Aquino
Marília Corrêa
Márcio Zarco
Nazaré Coello
Olívia Brum
Ordonho Paranhos
Orestes Vale
Paula Cardin
Paula Toscano
Penélope Loureiro
Potira Quiroga
Raimundo Briones
Remo Lóio
Ricardo Imbassaí
Rita Vicario
Rogério Natal
Romano Ferrão
Roque Cabeza de Vaca
Rosalina Garrau
Rubim Muñiz
Rui Valério
Sancha Borba
Simeão Areosa
Siquenique Nogueira
Solange Mattos
Sonás Rebelo
Suniário Barateiro
Telma Ramires
Tibúrcio Tabajara
Tomás Valle
Tomé Viégas
Trajano Sampaio
Ubaldo Arruda
Virgílio Casado
Viviana Almeida
Viviana Villaça
Vlademiro Barbosa
Vlademiro Beltrán
Xerxes Carijó
Zita Tabosa
Onde está Heitor Quintal?
A cada passo são selecionadas 
posições na lista que indicam qual 
parte dela pode ser ignorada e 
qual parte precisa ser avaliada.
Qual método utilizar para 
selecionar as posições de 
comparação?
Sempre seleciona metade: garante que metade 
dos dados serão ignorados a cada passo.
81
Recursividade: busca binária em lista ordenada
Seleciona o elemento na mediana da lista (posição da metade)
- Se o elemento for o procurado, retorna sua posição
- Se o elemento for menor, retorna o resultado da busca na metade anterior
- Se o elemento for maior, retorna o resultado da busca na metade posterior
82
Recursividade: busca binária em lista ordenada
Abigail Remígio
Adelina Azambuja
Adelina Verguero
Adão Simão
Adélia Beltrán
Agostinho Lages
Alarico Quinzeiro
Aldo Vides
Aldonça Sampaio
Alvito Tomé
Alzira Pino
Amandio Ruela
Américo Freixo
Anselmo Peres
Átila Quinta
Augusta Caiado
Balduíno Cruz
Barnabé Simão
Bartira Lemes
Belchior Mendonça
Bento Inácio
Burtira Imperial
Caetano Saloio
Calisto Maciel
Carla Carvalhal
Carlos Ferreira
Carlos Marmou
Cauã Núñez
Caím Ribas
Crispim Ríos
Cássio Siqueira
Célia Pasos
Deise Meira
Delfina Cayubi
Dinarte Barboza
Domingos Neiva
Débora Oliveira
Eliseu Pacheco
Ema Figueroa
Emiliana Cortesão
Eugénio Pires
Ezequiel Mayor
Feliciana Ferraz
Feliciana Lemes
Florbela Medeiros
Fábia Rego
Gedeão Villena
Gerardo Lago
Glauco Moreyra
Gonçalo Camarinho
Gonçalo Capucho
Greice Sampaio
Gui Freixo
Guido Bernardes
Guiomar Vargas
Gustavo Dâmaso
Heitor Quintal
Honório Carneiro
Isaac, Isaque Benevides
Israel Paranaguá
Jaci Toledo
Jacir Bezerril
Janaína Hollanda
Jonas Vilas Boas
Jorgina Quirós
Josefa Galindo
Laurinda Pires
Letícia Sampaio
Luciano Regalado
Lucrécia Ribas
Luísa Setúbal
Lázaro Tigre
Lénia Abreu
Lídia Eiró
Lúcia Díaz
Magali Souza
Mamede Rivas
Marcos Juruna
Mariano Mata
Marli Marmou
Marília Aquino
Marília Corrêa
Márcio Zarco
Nazaré Coello
Olívia Brum
Ordonho Paranhos
Orestes Vale
Paula Cardin
Paula Toscano
Penélope Loureiro
Potira Quiroga
Raimundo Briones
Remo Lóio
Ricardo Imbassaí
Rita Vicario
Rogério Natal
Romano Ferrão
Roque Cabeza de Vaca
Rosalina Garrau
Rubim Muñiz
Rui Valério
Sancha Borba
Simeão Areosa
Siquenique Nogueira
Solange Mattos
Sonás Rebelo
Suniário Barateiro
Telma Ramires
Tibúrcio Tabajara
Tomás Valle
Tomé Viégas
Trajano Sampaio
Ubaldo Arruda
Virgílio Casado
Viviana Almeida
Viviana Villaça
Vlademiro Barbosa
Vlademiro Beltrán
Xerxes Carijó
Zita Tabosa
Onde está Jorgina Quirós?
1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
9. 
10. 
11. 
12. 
13. 
14. 
15. 
16. 
17. 
18. 
19. 
20. 
21.
22. 
23. 
24. 
25. 
26. 
27. 
28. 
29. 
30. 
31. 
32. 
33. 
34. 
35. 
36. 
37. 
38. 
39. 
40. 
41. 
42.
43. 
44. 
45. 
46. 
47. 
48. 
49. 
50. 
51. 
52. 
53. 
54. 
55. 
56. 
57. 
58. 
59. 
60. 
61. 
62. 
63.
64. 
65. 
66. 
67. 
68. 
69. 
70. 
71. 
72. 
73. 
74. 
75. 
76. 
77. 
78. 
79. 
80. 
81. 
82. 
83. 
84.
85. 
86. 
87. 
88. 
89. 
90. 
91. 
92. 
93. 
94. 
95. 
96. 
97. 
98. 
99. 
100. 
101. 
102. 
103. 
104. 
105.
106. 
107. 
108. 
109. 
110. 
111. 
112. 
113. 
114. 
115. 
116. 
117. 
118. 
119. 
120. 
83
Recursividade: busca binária em lista ordenada
Abigail Remígio
Adelina Azambuja
Adelina Verguero
Adão Simão
Adélia Beltrán
Agostinho Lages
Alarico Quinzeiro
Aldo Vides
Aldonça Sampaio
Alvito Tomé
Alzira Pino
Amandio Ruela
Américo Freixo
Anselmo Peres
Átila Quinta
Augusta Caiado
Balduíno Cruz
Barnabé Simão
Bartira Lemes
Belchior Mendonça
Bento Inácio
Burtira Imperial
Caetano Saloio
Calisto Maciel
Carla Carvalhal
Carlos Ferreira
Carlos Marmou
Cauã Núñez
Caím Ribas
Crispim Ríos
Cássio Siqueira
Célia Pasos
Deise Meira
Delfina Cayubi
Dinarte Barboza
Domingos Neiva
Débora Oliveira
Eliseu Pacheco
Ema Figueroa
Emiliana Cortesão
Eugénio Pires
Ezequiel Mayor
Feliciana Ferraz
Feliciana Lemes
Florbela Medeiros
Fábia Rego
Gedeão Villena
Gerardo Lago
Glauco Moreyra
Gonçalo Camarinho
Gonçalo Capucho
Greice Sampaio
Gui Freixo
Guido Bernardes
Guiomar Vargas
Gustavo Dâmaso
Heitor Quintal
Honório Carneiro
Isaac, Isaque Benevides
Israel Paranaguá
Jaci Toledo
Jacir Bezerril
Janaína Hollanda
Jonas Vilas Boas
Jorgina Quirós
Josefa Galindo
Laurinda Pires
Letícia Sampaio
Luciano Regalado
Lucrécia Ribas
Luísa Setúbal
Lázaro Tigre
Lénia Abreu
Lídia Eiró
Lúcia Díaz
Magali Souza
Mamede Rivas
Marcos Juruna
Mariano Mata
Marli Marmou
Marília Aquino
Marília Corrêa
Márcio Zarco
Nazaré Coello
Olívia Brum
Ordonho Paranhos
Orestes Vale
Paula Cardin
Paula Toscano
Penélope Loureiro
Potira Quiroga
Raimundo Briones
Remo Lóio
Ricardo Imbassaí
Rita Vicario
Rogério Natal
Romano Ferrão
Roque Cabeza de Vaca
Rosalina Garrau
Rubim Muñiz
Rui Valério
Sancha Borba
Simeão Areosa
Siquenique Nogueira
Solange Mattos
Sonás Rebelo
Suniário Barateiro
Telma Ramires
Tibúrcio Tabajara
Tomás Valle
Tomé Viégas
Trajano Sampaio
Ubaldo Arruda
Virgílio Casado
Viviana Almeida
Viviana Villaça
Vlademiro Barbosa
Vlademiro Beltrán
Xerxes Carijó
Zita Tabosa
Onde está Jorgina Quirós?
1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
9. 
10. 
11. 
12. 
13. 
14. 
15. 
16. 
17. 
18. 
19. 
20. 
21.
22. 
23. 
24. 
25. 
26. 
27. 
28. 
29. 
30. 
31. 
32. 
33. 
34. 
35. 
36. 
37. 
38. 
39. 
40. 
41. 
42.
43. 
44. 
45. 
46. 
47. 
48. 
49. 
50. 
51. 
52. 
53. 
54. 
55. 
56. 
57. 
58. 
59. 
60. 
61. 
62. 
63.
64. 
65. 
66. 
67. 
68. 
69. 
70. 
71. 
72. 
73. 
74. 
75. 
76. 
77. 
78. 
79. 
80. 
81. 
82. 
83. 
84.
85. 
86. 
87. 
88. 
89. 
90. 
91. 
92. 
93. 
94. 
95. 
96. 
97. 
98. 
99. 
100. 
101. 
102. 
103. 
104. 
105.
106. 
107. 
108. 
109. 
110. 
111. 
112. 
113. 
114. 
115. 
116. 
117. 
118. 
119. 
120. 
84
Recursividade: busca binária em lista ordenada
Abigail Remígio
Adelina Azambuja
Adelina Verguero
Adão Simão
Adélia Beltrán
Agostinho Lages
Alarico Quinzeiro
Aldo Vides
Aldonça Sampaio
Alvito Tomé
Alzira Pino
Amandio Ruela
Américo Freixo
Anselmo Peres
Átila Quinta
Augusta Caiado
Balduíno Cruz
Barnabé Simão
Bartira Lemes
Belchior Mendonça
Bento Inácio
Burtira Imperial
Caetano Saloio
Calisto Maciel
Carla Carvalhal
Carlos Ferreira
Carlos Marmou
Cauã Núñez
Caím Ribas
Crispim Ríos
Cássio Siqueira
Célia Pasos
Deise Meira
Delfina Cayubi
Dinarte Barboza
Domingos Neiva
Débora Oliveira
Eliseu Pacheco
Ema Figueroa
Emiliana Cortesão
Eugénio Pires
Ezequiel Mayor
Feliciana Ferraz
Feliciana Lemes
Florbela Medeiros
Fábia Rego
Gedeão Villena
Gerardo Lago
Glauco Moreyra
Gonçalo Camarinho
Gonçalo Capucho
Greice Sampaio
Gui Freixo
Guido Bernardes
Guiomar Vargas
Gustavo Dâmaso
Heitor Quintal
Honório Carneiro
Isaac, Isaque Benevides
Israel Paranaguá
Jaci Toledo
Jacir Bezerril
Janaína Hollanda
Jonas Vilas Boas
Jorgina Quirós
Josefa Galindo
Laurinda Pires
Letícia Sampaio
Luciano Regalado
Lucrécia Ribas
Luísa Setúbal
Lázaro Tigre
Lénia Abreu
Lídia Eiró
Lúcia Díaz
Magali Souza
Mamede Rivas
Marcos Juruna
Mariano Mata
Marli Marmou
Marília Aquino
Marília Corrêa
Márcio Zarco
Nazaré Coello
Olívia Brum
Ordonho Paranhos
Orestes Vale
PaulaCardin
Paula Toscano
Penélope Loureiro
Potira Quiroga
Raimundo Briones
Remo Lóio
Ricardo Imbassaí
Rita Vicario
Rogério Natal
Romano Ferrão
Roque Cabeza de Vaca
Rosalina Garrau
Rubim Muñiz
Rui Valério
Sancha Borba
Simeão Areosa
Siquenique Nogueira
Solange Mattos
Sonás Rebelo
Suniário Barateiro
Telma Ramires
Tibúrcio Tabajara
Tomás Valle
Tomé Viégas
Trajano Sampaio
Ubaldo Arruda
Virgílio Casado
Viviana Almeida
Viviana Villaça
Vlademiro Barbosa
Vlademiro Beltrán
Xerxes Carijó
Zita Tabosa
Onde está Jorgina Quirós?
1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
9. 
10. 
11. 
12. 
13. 
14. 
15. 
16. 
17. 
18. 
19. 
20. 
21.
22. 
23. 
24. 
25. 
26. 
27. 
28. 
29. 
30. 
31. 
32. 
33. 
34. 
35. 
36. 
37. 
38. 
39. 
40. 
41. 
42.
43. 
44. 
45. 
46. 
47. 
48. 
49. 
50. 
51. 
52. 
53. 
54. 
55. 
56. 
57. 
58. 
59. 
60. 
61. 
62. 
63.
64. 
65. 
66. 
67. 
68. 
69. 
70. 
71. 
72. 
73. 
74. 
75. 
76. 
77. 
78. 
79. 
80. 
81. 
82. 
83. 
84.
85. 
86. 
87. 
88. 
89. 
90. 
91. 
92. 
93. 
94. 
95. 
96. 
97. 
98. 
99. 
100. 
101. 
102. 
103. 
104. 
105.
106. 
107. 
108. 
109. 
110. 
111. 
112. 
113. 
114. 
115. 
116. 
117. 
118. 
119. 
120. 
85
Recursividade: busca binária em lista ordenada
Abigail Remígio
Adelina Azambuja
Adelina Verguero
Adão Simão
Adélia Beltrán
Agostinho Lages
Alarico Quinzeiro
Aldo Vides
Aldonça Sampaio
Alvito Tomé
Alzira Pino
Amandio Ruela
Américo Freixo
Anselmo Peres
Átila Quinta
Augusta Caiado
Balduíno Cruz
Barnabé Simão
Bartira Lemes
Belchior Mendonça
Bento Inácio
Burtira Imperial
Caetano Saloio
Calisto Maciel
Carla Carvalhal
Carlos Ferreira
Carlos Marmou
Cauã Núñez
Caím Ribas
Crispim Ríos
Cássio Siqueira
Célia Pasos
Deise Meira
Delfina Cayubi
Dinarte Barboza
Domingos Neiva
Débora Oliveira
Eliseu Pacheco
Ema Figueroa
Emiliana Cortesão
Eugénio Pires
Ezequiel Mayor
Feliciana Ferraz
Feliciana Lemes
Florbela Medeiros
Fábia Rego
Gedeão Villena
Gerardo Lago
Glauco Moreyra
Gonçalo Camarinho
Gonçalo Capucho
Greice Sampaio
Gui Freixo
Guido Bernardes
Guiomar Vargas
Gustavo Dâmaso
Heitor Quintal
Honório Carneiro
Isaac, Isaque Benevides
Israel Paranaguá
Jaci Toledo
Jacir Bezerril
Janaína Hollanda
Jonas Vilas Boas
Jorgina Quirós
Josefa Galindo
Laurinda Pires
Letícia Sampaio
Luciano Regalado
Lucrécia Ribas
Luísa Setúbal
Lázaro Tigre
Lénia Abreu
Lídia Eiró
Lúcia Díaz
Magali Souza
Mamede Rivas
Marcos Juruna
Mariano Mata
Marli Marmou
Marília Aquino
Marília Corrêa
Márcio Zarco
Nazaré Coello
Olívia Brum
Ordonho Paranhos
Orestes Vale
Paula Cardin
Paula Toscano
Penélope Loureiro
Potira Quiroga
Raimundo Briones
Remo Lóio
Ricardo Imbassaí
Rita Vicario
Rogério Natal
Romano Ferrão
Roque Cabeza de Vaca
Rosalina Garrau
Rubim Muñiz
Rui Valério
Sancha Borba
Simeão Areosa
Siquenique Nogueira
Solange Mattos
Sonás Rebelo
Suniário Barateiro
Telma Ramires
Tibúrcio Tabajara
Tomás Valle
Tomé Viégas
Trajano Sampaio
Ubaldo Arruda
Virgílio Casado
Viviana Almeida
Viviana Villaça
Vlademiro Barbosa
Vlademiro Beltrán
Xerxes Carijó
Zita Tabosa
Onde está Jorgina Quirós?
1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
9. 
10. 
11. 
12. 
13. 
14. 
15. 
16. 
17. 
18. 
19. 
20. 
21.
22. 
23. 
24. 
25. 
26. 
27. 
28. 
29. 
30. 
31. 
32. 
33. 
34. 
35. 
36. 
37. 
38. 
39. 
40. 
41. 
42.
43. 
44. 
45. 
46. 
47. 
48. 
49. 
50. 
51. 
52. 
53. 
54. 
55. 
56. 
57. 
58. 
59. 
60. 
61. 
62. 
63.
64. 
65. 
66. 
67. 
68. 
69. 
70. 
71. 
72. 
73. 
74. 
75. 
76. 
77. 
78. 
79. 
80. 
81. 
82. 
83. 
84.
85. 
86. 
87. 
88. 
89. 
90. 
91. 
92. 
93. 
94. 
95. 
96. 
97. 
98. 
99. 
100. 
101. 
102. 
103. 
104. 
105.
106. 
107. 
108. 
109. 
110. 
111. 
112. 
113. 
114. 
115. 
116. 
117. 
118. 
119. 
120. 
86
Recursividade: busca binária em lista ordenada
Abigail Remígio
Adelina Azambuja
Adelina Verguero
Adão Simão
Adélia Beltrán
Agostinho Lages
Alarico Quinzeiro
Aldo Vides
Aldonça Sampaio
Alvito Tomé
Alzira Pino
Amandio Ruela
Américo Freixo
Anselmo Peres
Átila Quinta
Augusta Caiado
Balduíno Cruz
Barnabé Simão
Bartira Lemes
Belchior Mendonça
Bento Inácio
Burtira Imperial
Caetano Saloio
Calisto Maciel
Carla Carvalhal
Carlos Ferreira
Carlos Marmou
Cauã Núñez
Caím Ribas
Crispim Ríos
Cássio Siqueira
Célia Pasos
Deise Meira
Delfina Cayubi
Dinarte Barboza
Domingos Neiva
Débora Oliveira
Eliseu Pacheco
Ema Figueroa
Emiliana Cortesão
Eugénio Pires
Ezequiel Mayor
Feliciana Ferraz
Feliciana Lemes
Florbela Medeiros
Fábia Rego
Gedeão Villena
Gerardo Lago
Glauco Moreyra
Gonçalo Camarinho
Gonçalo Capucho
Greice Sampaio
Gui Freixo
Guido Bernardes
Guiomar Vargas
Gustavo Dâmaso
Heitor Quintal
Honório Carneiro
Isaac, Isaque Benevides
Israel Paranaguá
Jaci Toledo
Jacir Bezerril
Janaína Hollanda
Jonas Vilas Boas
Jorgina Quirós
Josefa Galindo
Laurinda Pires
Letícia Sampaio
Luciano Regalado
Lucrécia Ribas
Luísa Setúbal
Lázaro Tigre
Lénia Abreu
Lídia Eiró
Lúcia Díaz
Magali Souza
Mamede Rivas
Marcos Juruna
Mariano Mata
Marli Marmou
Marília Aquino
Marília Corrêa
Márcio Zarco
Nazaré Coello
Olívia Brum
Ordonho Paranhos
Orestes Vale
Paula Cardin
Paula Toscano
Penélope Loureiro
Potira Quiroga
Raimundo Briones
Remo Lóio
Ricardo Imbassaí
Rita Vicario
Rogério Natal
Romano Ferrão
Roque Cabeza de Vaca
Rosalina Garrau
Rubim Muñiz
Rui Valério
Sancha Borba
Simeão Areosa
Siquenique Nogueira
Solange Mattos
Sonás Rebelo
Suniário Barateiro
Telma Ramires
Tibúrcio Tabajara
Tomás Valle
Tomé Viégas
Trajano Sampaio
Ubaldo Arruda
Virgílio Casado
Viviana Almeida
Viviana Villaça
Vlademiro Barbosa
Vlademiro Beltrán
Xerxes Carijó
Zita Tabosa
Onde está Jorgina Quirós?
1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
9. 
10. 
11. 
12. 
13. 
14. 
15. 
16. 
17. 
18. 
19. 
20. 
21.
22. 
23. 
24. 
25. 
26. 
27. 
28. 
29. 
30. 
31. 
32. 
33. 
34. 
35. 
36. 
37. 
38. 
39. 
40. 
41. 
42.
43. 
44. 
45. 
46. 
47. 
48. 
49. 
50. 
51. 
52. 
53. 
54. 
55. 
56. 
57. 
58. 
59. 
60. 
61. 
62. 
63.
64. 
65. 
66. 
67. 
68. 
69. 
70. 
71. 
72. 
73. 
74. 
75. 
76. 
77. 
78. 
79. 
80. 
81. 
82. 
83. 
84.
85. 
86. 
87. 
88. 
89. 
90. 
91. 
92. 
93. 
94. 
95. 
96. 
97. 
98. 
99. 
100. 
101. 
102. 
103. 
104. 
105.
106. 
107. 
108. 
109. 
110. 
111. 
112. 
113. 
114. 
115. 
116. 
117. 
118. 
119. 
120. 
87
Recursividade: busca binária em lista ordenada
Abigail Remígio
Adelina Azambuja
Adelina Verguero
Adão Simão
Adélia Beltrán
Agostinho Lages
Alarico Quinzeiro
Aldo Vides
Aldonça Sampaio
Alvito Tomé
Alzira Pino
Amandio Ruela
Américo Freixo
Anselmo Peres
Átila Quinta
Augusta Caiado
Balduíno Cruz
Barnabé Simão
Bartira Lemes
Belchior Mendonça
Bento Inácio
Burtira Imperial
Caetano Saloio
Calisto Maciel
Carla Carvalhal
Carlos Ferreira
Carlos Marmou
Cauã Núñez
Caím Ribas
Crispim Ríos
Cássio Siqueira
Célia Pasos
Deise Meira
Delfina Cayubi
Dinarte Barboza
Domingos Neiva
Débora Oliveira
Eliseu Pacheco
Ema Figueroa
Emiliana Cortesão
Eugénio Pires
Ezequiel Mayor
Feliciana Ferraz
Feliciana Lemes
Florbela Medeiros
Fábia Rego
Gedeão Villena
Gerardo Lago
Glauco Moreyra
Gonçalo Camarinho
Gonçalo Capucho
Greice Sampaio
Gui Freixo
Guido Bernardes
Guiomar Vargas
Gustavo Dâmaso
Heitor Quintal
Honório Carneiro
Isaac, Isaque Benevides
Israel Paranaguá
Jaci Toledo
Jacir Bezerril
Janaína Hollanda
Jonas Vilas Boas
Jorgina Quirós
Josefa Galindo
Laurinda Pires
Letícia Sampaio
Luciano Regalado
Lucrécia Ribas
Luísa Setúbal
Lázaro Tigre
Lénia Abreu
Lídia Eiró
Lúcia Díaz
Magali Souza
Mamede Rivas
Marcos Juruna
Mariano Mata
Marli Marmou
Marília Aquino
Marília Corrêa
Márcio Zarco
Nazaré Coello
Olívia Brum
Ordonho Paranhos
Orestes Vale
Paula Cardin
Paula Toscano
Penélope Loureiro
Potira Quiroga
Raimundo Briones
Remo Lóio
Ricardo Imbassaí
Rita Vicario
Rogério Natal
Romano Ferrão
Roque Cabeza de Vaca
Rosalina Garrau
Rubim Muñiz
Rui Valério
Sancha Borba
Simeão Areosa
Siquenique Nogueira
Solange Mattos
Sonás Rebelo
Suniário BarateiroTelma Ramires
Tibúrcio Tabajara
Tomás Valle
Tomé Viégas
Trajano Sampaio
Ubaldo Arruda
Virgílio Casado
Viviana Almeida
Viviana Villaça
Vlademiro Barbosa
Vlademiro Beltrán
Xerxes Carijó
Zita Tabosa
Onde está Jorgina Quirós?
1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
9. 
10. 
11. 
12. 
13. 
14. 
15. 
16. 
17. 
18. 
19. 
20. 
21.
22. 
23. 
24. 
25. 
26. 
27. 
28. 
29. 
30. 
31. 
32. 
33. 
34. 
35. 
36. 
37. 
38. 
39. 
40. 
41. 
42.
43. 
44. 
45. 
46. 
47. 
48. 
49. 
50. 
51. 
52. 
53. 
54. 
55. 
56. 
57. 
58. 
59. 
60. 
61. 
62. 
63.
64. 
65. 
66. 
67. 
68. 
69. 
70. 
71. 
72. 
73. 
74. 
75. 
76. 
77. 
78. 
79. 
80. 
81. 
82. 
83. 
84.
85. 
86. 
87. 
88. 
89. 
90. 
91. 
92. 
93. 
94. 
95. 
96. 
97. 
98. 
99. 
100. 
101. 
102. 
103. 
104. 
105.
106. 
107. 
108. 
109. 
110. 
111. 
112. 
113. 
114. 
115. 
116. 
117. 
118. 
119. 
120. 
88
Recursividade: busca binária em lista ordenada
Abigail Remígio
Adelina Azambuja
Adelina Verguero
Adão Simão
Adélia Beltrán
Agostinho Lages
Alarico Quinzeiro
Aldo Vides
Aldonça Sampaio
Alvito Tomé
Alzira Pino
Amandio Ruela
Américo Freixo
Anselmo Peres
Átila Quinta
Augusta Caiado
Balduíno Cruz
Barnabé Simão
Bartira Lemes
Belchior Mendonça
Bento Inácio
Burtira Imperial
Caetano Saloio
Calisto Maciel
Carla Carvalhal
Carlos Ferreira
Carlos Marmou
Cauã Núñez
Caím Ribas
Crispim Ríos
Cássio Siqueira
Célia Pasos
Deise Meira
Delfina Cayubi
Dinarte Barboza
Domingos Neiva
Débora Oliveira
Eliseu Pacheco
Ema Figueroa
Emiliana Cortesão
Eugénio Pires
Ezequiel Mayor
Feliciana Ferraz
Feliciana Lemes
Florbela Medeiros
Fábia Rego
Gedeão Villena
Gerardo Lago
Glauco Moreyra
Gonçalo Camarinho
Gonçalo Capucho
Greice Sampaio
Gui Freixo
Guido Bernardes
Guiomar Vargas
Gustavo Dâmaso
Heitor Quintal
Honório Carneiro
Isaac, Isaque Benevides
Israel Paranaguá
Jaci Toledo
Jacir Bezerril
Janaína Hollanda
Jonas Vilas Boas
Jorgina Quirós
Josefa Galindo
Laurinda Pires
Letícia Sampaio
Luciano Regalado
Lucrécia Ribas
Luísa Setúbal
Lázaro Tigre
Lénia Abreu
Lídia Eiró
Lúcia Díaz
Magali Souza
Mamede Rivas
Marcos Juruna
Mariano Mata
Marli Marmou
Marília Aquino
Marília Corrêa
Márcio Zarco
Nazaré Coello
Olívia Brum
Ordonho Paranhos
Orestes Vale
Paula Cardin
Paula Toscano
Penélope Loureiro
Potira Quiroga
Raimundo Briones
Remo Lóio
Ricardo Imbassaí
Rita Vicario
Rogério Natal
Romano Ferrão
Roque Cabeza de Vaca
Rosalina Garrau
Rubim Muñiz
Rui Valério
Sancha Borba
Simeão Areosa
Siquenique Nogueira
Solange Mattos
Sonás Rebelo
Suniário Barateiro
Telma Ramires
Tibúrcio Tabajara
Tomás Valle
Tomé Viégas
Trajano Sampaio
Ubaldo Arruda
Virgílio Casado
Viviana Almeida
Viviana Villaça
Vlademiro Barbosa
Vlademiro Beltrán
Xerxes Carijó
Zita Tabosa
Onde está Jorgina Quirós?
1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
9. 
10. 
11. 
12. 
13. 
14. 
15. 
16. 
17. 
18. 
19. 
20. 
21.
22. 
23. 
24. 
25. 
26. 
27. 
28. 
29. 
30. 
31. 
32. 
33. 
34. 
35. 
36. 
37. 
38. 
39. 
40. 
41. 
42.
43. 
44. 
45. 
46. 
47. 
48. 
49. 
50. 
51. 
52. 
53. 
54. 
55. 
56. 
57. 
58. 
59. 
60. 
61. 
62. 
63.
64. 
65. 
66. 
67. 
68. 
69. 
70. 
71. 
72. 
73. 
74. 
75. 
76. 
77. 
78. 
79. 
80. 
81. 
82. 
83. 
84.
85. 
86. 
87. 
88. 
89. 
90. 
91. 
92. 
93. 
94. 
95. 
96. 
97. 
98. 
99. 
100. 
101. 
102. 
103. 
104. 
105.
106. 
107. 
108. 
109. 
110. 
111. 
112. 
113. 
114. 
115. 
116. 
117. 
118. 
119. 
120. 
89
A busca termina pois o nome foi 
encontrado!
Na aula prática desta semana iremos 
implementar este algoritmo!
Quando usar recursão e quando usar laços?
Não há uma resposta definitiva, pois dependendo do caso soluções mais eficientes podem 
ser obtidos com recursão ou com algoritmos iterativos
No geral, toda implementação recursiva pode ser "convertida" em iterativa de alguma 
forma. Algumas dicas para uso de recursão:
Utilizar recursão quando a solução iterativa for muito complexa ou de difícil 
compreensão
Optar por recursão quando seu desempenho computacional for igual ou melhor que 
o método iterativo correspondente
Existem alguns recursos que serão vistos em outras disciplinas (como memoization), 
que tornam a execução de algoritmos naturalmente recursivos mais rápida, sendo neste 
caso recomendado o uso de recursão
90