Introdução à Programação
Um enfoque orientado a construção de
modelos em programas baseados em objetos
Gustavo Motta
Departamento de Informática - UFPB
6. Comandos iterativos e recursão
► Comandos
iterativos ou de repetição
 Definição
comando iterativo (também chamado de laço) tem um
subcomando (o corpo do laço) que é executado repetidamente
e uma cláusula que determina quando a repetição cessará
► Um
 Essencial para uma linguagem ser universal
 Necessários em muitos modelos e aplicações
► Calcular
a média das notas de todos os alunos de uma turma
► Comparar
a seqüência de caracteres em um string que
representa parte de um DNA com outra, caractere por
caractere, do primeiro até o último
► Repetir
a leitura da senha de um usuário enquanto ela não
estiver correta
(C) 2008 Gustavo Motta
2
6. Comandos iterativos e recursão
► Comandos
iterativos ou de repetição
 Modalidades
► Comandos
de iteração indefinida
 Aqueles nos quais o número de iterações não é determinado
previamente
 Depende de uma condição de repetição
► Enquanto
não alcançar a última linha do arquivo, continue
lendo a próxima linha para imprimi-la
 Em Java, são os comandos while e do-while
► Comandos
de iteração definida
 Aqueles nos quais o número de iterações é sabido antecipadamente
 Caracterizado pelo uso de uma variável de controle, denominada de
contador do laço
► Some
os valores de uma seqüência de números, desde a
primeira posição, até a centésima
(C) 2008 Gustavo Motta
 Em Java, é o comando for
3
6. Comandos iterativos e recursão
►O
comando while
► while
(expressão-lógica)
subcomando;
► while
(expressão-lógica) {
subcomando_1;
subcomando_2;
...
subcomando_n;
}
 A avaliação da expressão-lógica determina a condição
de repetição. Caso true, o subcomando (ou o bloco de
subcomandos) é executado e a condição é reavaliada
► Enquanto
► Quando
a condição for true, o subcomando é executado
a condição for false, o comando while é encerrado e
(C) 2008 Gustavo Motta
4
o próximo comando é executado
6. Comandos iterativos e recursão
►O
comando while
 Exemplo: calcular o somatório dos primeiros N números
inteiros positivos
Memória
n
1
int somatório(int n) {
int soma = 0, proximoInt = 1;
2
soma
while (proximoInt <= n) {
soma = soma + proximoInt;
3 proximoInt
proximoInt = proximoInt + 1;
}
return soma;
}
...
System.out.println(“Somátório de 5: ”+somatório(5));
(C) 2008
Gustavo Motta
Somatório de 5:
15
5
10
15
0
1
3
6
1
2
3
4
5
6
5
6. Comandos iterativos e recursão
►O
comando while
 usar
Recomendações
de while
verificação
Pode-se
o próprio comando
para obrigar o usuário a entrar
Verificar
se inteiros
a condição
de repetição inicial do while permite a
somente ►
com
números
positivos
entrada no laço de forma correta
 Caso
a condição
inicial
seja false, o subcomando ou bloco de
Scanner entrada
= new
Scanner
(System.in);
subcomandos
do while não será executado nem mesmo uma vez
int intPositive
= entrada.nextInt();
while (intPositive
<= o0)valor
{ de n seja zero ou negativo, a condição inicial é
► Caso
System.out.println("===O
numero
nao pode ser
zero===");
false, bloco
de subcomandos
do negativo
while do ou
exemplo
anterior
intPositive = não
entrada.nextInt();
é executado nenhuma vez e o resultado do somatório é 0
}
 Nesta versão abaixo do exemplo anterior, o bloco de subcomandos
do laço nunca é executado porque a condição sempre é false
int soma = demowhile.somatório(intPositive);
int somatório(int n) {
System.out.println("Somatorio
de "+intPositive+":
"+soma);
int soma = 0, proximoInt
= n + 1;
while (proximoInt <= n) {
soma = soma + proximoInt;
proximoInt = proximoInt + 1;
}
(C) 2008 Gustavo Motta
return soma;
}
6
6. Comandos iterativos e recursão
►O
comando while
• Por exemplo,
o comando while
abaixo nunca termina porque a sua condição
 Recomendações
de verificação
do sempre ►
será
verdadeira
n inicialmente
>= 1),doouwhile
seja, não
varia com
Verificar
se a(sendo
condição
de repetição
permite
o
a execução dos
subcomandos
laço
encerramento
no do
laço
de acordo com a modificação, no bloco de
subcomandos do laço, das variáveis usadas na condição
int somatório(int n) {
int soma = 0, proximoInt = 1;
 No exemplo anterior, supondo que proximoInt = 1 e que n é
while (proximoInt
<= n) {
positivo, o subcomando proximoInt = proximoInt + 1; no do laço
soma = soma
+ proximoInt;
assegura
que a condição proximoInt <= n será false numa dada
proximoInt
= proximoInt
0; o número de repetições sempre será
iteração
do while , ou+ seja,
}
finito (igual a n)
return soma;
}
 Caso a condição seja sempre true, isto é, não possa variar com a
execução sucessiva do bloco de subcomandos do while, então o
• Embora não termine
de forma
normal,
é possível
programa
continuará
executando
parainterromper
sempre, ou anormalmente
seja, o número
deloop
repetições
será infinito do sistema operacional ou
um programa (em
) com comandos
simplesmente desligando o computador,
porém
os resultados obtidos podem 7
(C) 2008 Gustavo
Motta
ser indesejáveis
6. Comandos iterativos e recursão
►O
comando while
 Recomendações de verificação
• Isto porque se o resultado não pode ser armazenado, o valor efetivamente
► Quando
se ao
tratar
de valor
números
no comando
while,
deve-se
armazenado
corresponde
menor
armazenável
(-128 no
caso do
tipo
observar
possibilidade
daoocorrência
dearmazenável
overflow
byte) adicionado
pelo a
valor
que excede
maior valor
menos 1
 Em números inteiros, o overflow ocorre quando o resultado da
valorArmazenado
= menorInteiro
(Resultadoaritmética
– maiorInteiro
– 1)número maior (ou
avaliação
de uma +expressão
é um
menor) que o maior (menor) número que pode ser representado
• Por exemplo, caso
tente
o valor 200 numa variável do tipo
numse
dado
tipoarmazenar
inteiro
short, o valor efetivamente
armazenado
será
► Por exemplo,
uma variável
do tipo byte pode armazenar
qualquer valor no intervalo -128 até +127
valorArmazenado = –128 + (200 – 127 – 1) = –56
byte contador = 127;
• É importante frisar que
o nem o compilador, nem a maquina virtual Java,
contador = (byte) (contador + 1);
acusa este tipo de erro.
System.out.println(“Contador: ”+contador);
Cabe ao programador tomar cuidado, examinando cuidadosamente os
► No
-128 é o valor
impressoem variáveis
limites máximos
e exemplo
mínimosacima,
potencialmente
assumidos
(C) 2008 Gustavo Motta
8
inteiras e sua adequação do tipo escolhido: byte, short, int ou long
6. Comandos iterativos e recursão
►O
comando while
 Recomendações de verificação
► Quando
se tratar de números no comando while, deve-se
observar a possibilidade da ocorrência de overflow
 Em números de ponto flutuante, o overflow também pode ocorrer,
mas nestes casos, a linguagem Java estabelece valores constantes
especiais para designar o infinito positivo e o infinito negativo
► Por
exemplo, ao final da execução do código abaixo
float valor = Float.MAX_VALUE;
valor = valor * 2;
System.out.println(“Valor: ” + valor);
► No
exemplo acima, Infinity é o valor impresso e
corresponde
ao
valor
da
constante
Float.POSITIVE_INFINITY
definida na classe Float da
(C) 2008 Gustavo Motta
9
biblioteca de classes de Java
6. Comandos iterativos e recursão
►O
comando while
 Recomendações de verificação
► Quando
se tratar de números de ponto flutuante no comando
while, deve-se observar a possibilidade da ocorrência de
underflow
• O compilador
arredonda para zero valores muito próximos de zero que não
 O underflow
pode
ocorrer
quando
o tipoflutuante
ponto flutuante não for
podem ser representados
num
dado
número
de ponto
capaz de representar um número muito próximo de zero
• Cabe ao programador
todas
► Portomar
exemplo,
ao as
finalprecauções
da execuçãonecessárias!
do código abaixo
float quociente = 1;
while (quociente > 0) {
System.out.println(quociente);
quociente = quociente / 2;
}
o valor da variável quociente é zero, embora devesse ser um
número muito pequeno, próximo de zero, mas não zero
(C) 2008 Gustavo Motta
10
6. Comandos iterativos e recursão
►O
comando while
 Recomendações de verificação
► Seja
cuidadoso ao usar desigualdades em condições de controle
de repetições no comando while
• Em casos como este, deve-se evitar o uso de desiguladades. O código
► Por exemplo, a execução do código abaixo
anterior pode ser reescrito da forma mais segura abaixo
float saldo = 10;
float while
saldo (saldo
= 10; != 0) {
while (saldo
>= 0) {
System.out.println(saldo);
System.out.println(saldo);
saldo = saldo – 0.1f;
saldo
= saldo – 0.1f;
}
}
nunca termina, pois devido a imprecisão na representação de
números decimais (e. g., o valor 0.1) em notação de ponto
flutuante em base binário, o valor do saldo passa de um
número positivo muito próximo de zero para um número
negativo também muito próximo a zero, mas sem ser zero,
11
como esperado(C) 2008 Gustavo Motta
6. Comandos iterativos e recursão
►O
comando while
 Comandos de iteração em Java podem ser encerrados
abruptamente, independente da condição de repetição,
com o uso do comando break
► Sempre
que um break é executado dentro de um laço, ele força
o seu encerramento imediato, seguindo o programa o fluxo
normal de execução do próximo comando após o laço
►
Por exemplo, o laço abaixo
while (true) {
String opcao = entrada.nextLine();
if (opcao.equals(“s”))
break;
System.out.println(opcao);
}
só termina quando
valor
opcao for igual a s e o valor de
(C) 2008 o
Gustavo
Motta
opcao só é impresso se ela for diferente de s
12
6. Comandos iterativos e recursão
►O
comando while
 Comandos de iteração em Java podem ser parcialmente
interrompidos com o comando continue
► Sempre
que um continue é executado dentro de um laço, ele
interrompe a execução dos subcomandos do laço nesta iteração,
a partir do próximo subcomando, voltando para a avaliação da
condição de terminação do laço
►
Por exemplo, no laço abaixo
String opcao = “a”;
while (!opcao.equals(“s”)) {
opcao = entrada.nextLine();
if (opcao.equals(“s”))
continue;
System.out.println(“Entre Opção diferente de s”);
}
o último subcomando só é executado quando a opção é
Gustavo
Motta
diferente de s.(C) 2008
Caso
contrário,
o continue força o desvio 13
do
fluxo de execução para a avaliação da condição do laço
6. Comandos iterativos e recursão
►O
comando do-while
do {
subcomando_1;
subcomando_2;
...
subcomando_n;
}
while (expressão-lógica);
 A avaliação da expressão-lógica
condição de repetição
►Enquanto
determina
a
a condição for true, o bloco de subcomandos é
executado
►Quando
a condição for false, o comando do-while é
encerrado e o próximo comando é executado
►A
diferença em relação
ao comando while é que o bloco de
(C) 2008 Gustavo Motta
14
subcomandos é, necessariamente, executado pelo menos uma vez
6. Comandos iterativos e recursão
►O
comando do-while
 Exemplo: ler a opção do menu de uma aplicação
int menuCartãoCrédito() {
int opcao = 0;
Scanner entrada = new Scanner(System.in);
do {
System.out.print(“1 - compra | 2 - paga | 3 - ver saldo | “);
System.out.println(“4 - ver bonus | 5 - encerra: ");
System.out.print("Sistema de Cartao de Credito. ”);
System.out.print("Escolha a opcao: ");
opcao = entrada.nextInt();
}
while (!(opcao > = 1 && opcao <= 5));
return opcao;
}
(C) 2008 Gustavo Motta
15
6. Comandos iterativos e recursão
► Contadores
 Contadores são variáveis que recebem um valor inicial e
que são modificadas a cada iteração de comando de
repetição de Java
► Contadores
são modificados mediante a atribuição do resultado
da avaliação de uma expressão aritmética envolvendo o próprio
contador
 soma = soma + 1;
 fatorial = fatorial * n;
 saldo = saldo – 100;
 quociente = quociente / 2;
► Java
permite a utilização de operadores
modificação de variáveis que são contadores
(C) 2008 Gustavo Motta
especiais
para
16
6. Comandos iterativos e recursão
► Contadores
 Operador ++ : quando aplicado a uma variável numérica,
incrementa o valor da variável em um
soma++;
► é o mesmo que
soma = soma + 1;
► Além
de modificar o valor, o operador ++ retorna um valor
 Caso o operador seja aplicado à direita do operando, o valor
retornado é igual ao valor da variável antes da aplicação, por
exemplo
► int resultado = 0, contador = 1;
resultado = contador++;
►o
conteúdo da variável resultado após a atribuição é 1
enquanto o conteúdo de contador é 2
 Caso o operador fosse aplicado à esquerda
► resultado
►o
= (C)++contador;
2008 Gustavo Motta
conteúdo de ambas as variáveis seria 2
17
6. Comandos iterativos e recursão
► Contadores
 Operador -- : quando aplicado a uma variável numérica,
decrementa o valor da variável em um
total--;
► é o mesmo que
total = total - 1;
► Além
de modificar o valor, o operador  retorna um valor
 Caso o operador seja aplicado à direita do operando, o valor
retornado é igual ao valor da variável antes da aplicação, por
exemplo
► int resultado = 0, total = 100;
resultado = total--;
►o
conteúdo da variável resultado após a atribuição é 100
enquanto o conteúdo de total é 99
 Caso o operador fosse aplicado à esquerda
► resultado
►o
= (C)--total;
2008 Gustavo Motta
conteúdo de ambas as variáveis seria 99
18
6. Comandos iterativos e recursão
► Contadores
 Operador += : quando aplicado a uma variável numérica,
adiciona, ao valor da variável atribuída, o valor à direita
do operando
saldo += 100;
►é
o mesmo que
saldo = saldo + 100;
 Operador -= : quando aplicado a uma variável numérica,
subtrai, do valor da variável atribuída, o valor à direita do
operando
saldo -= 50;
►é
o mesmo que
saldo = saldo -(C) 2008
50;
Gustavo Motta
19
6. Comandos iterativos e recursão
► Contadores
 Operador *= : quando aplicado a uma variável numérica,
multiplica, o valor da variável atribuída, pelo valor à
direita do operando
fatorial *= n;
►é
o mesmo que
fatorial = fatorial * n;
 Operador /= : quando aplicado a uma variável numérica,
divide, o valor da variável atribuída, pelo valor à direita do
operando
quociente /= 100;
►
o mesmo que
quociente = quociente
/ 100;
(C) 2008 Gustavo Motta
20
6. Comandos iterativos e recursão
►O
comando for
 for (inicialização; expressão-lógica; atualização)
subcomando;
 for (inicialização; expressão-lógica; atualização) {
subcomando_1;
subcomando_2;
...
subcomando_n;
}
► inicialização
atribui um valor inicial para o contador do for
► expressão-lógica
► atualização
estabelece a condição de repetição do laço
(C) 2008 Gustavo Motta
modifica
o valor do contador do for
21
6. Comandos iterativos e recursão
►O
comando for
 Exemplo: calcular o fatorial de N
Memória
n
long fatorial(int n) {
1
long fat = 1;
2
fat
fat
fat
for (int i = 1; i <= n; i++) {
fat = fat * i;
i
3
}
return fat;
}
...
System.out.println(“Fatorial de 5: ”+ fatorial(5));
Fatorial de 5: (C)120
2008 Gustavo Motta
5
120
24
6
2
1
5
3
2
1
4
22
6. Comandos iterativos e recursão
►O
comando for
 Outras formas de uso
int contador;
for (contador = 0; contador < 100; contador++) {
System.out.println(contador);
}
for (contador = 200;contador >= 0; contador -= 10) {
System.out.println(contador);
}
for (double controle = 0;controle < 0; controle += 3.5) {
System.out.println(controle);
}
(C) 2008 Gustavo Motta
23
6. Comandos iterativos e recursão
►O
comando for
 Outras formas de uso
double início
= 100;
double fim
= 200;
double incremento = 2.5;
for(;;) {
//executa para sempre
System.out.println(início);
if (início >= fim) break;
início += incremento;
}
for (contador = 0;contador < 1000; contador+=2) {
System.out.println(contador);
contador = 0;
}
(C) 2008 Gustavo Motta
24
6. Comandos iterativos e recursão
►
Recursão
 Recursão (ou recursividade)
é
uma
técnica
de
programação na qual uma
computação é definida em
termos dela mesma
long fatorial(int n) n)
{ ={4)
n
5) {
1)
2)
3)
if (n <= 1) {
return 1;
}
else {
return n * fatorial(n 1);
}
}
...
System.out.println(“Fatorial
de 5: ”+ fatorial(5));
Memória
1
n
5
2
n
4
3
n
3
4
n
2
5
n
1
Drawing
(1948),
Fatorial
5
120
* 24
fatorial(4)
4
* 6
fatorial(3)
3
de
* 5:
fatorial(2)
2
120
*Hands
fatorial(1)
1
(C) 2008 litogravura
Gustavo Motta - M C Escher
25
6. Comandos iterativos e recursão
► Recursão
 A natureza da recursividade
► Existem
maiscomo
casosuma
simples
de um para
problema,
chamados
• A recursividade
podeum
serouusada
alternativa
iteração
de casos de parada, que têm solução trivial
fatorial 1 = 1
• Em geral, é uma solução menos eficiente em termos de tempo e espaço
► Os demais casos podem ser solucionados pela substituição para
uma versão reduzida do problema, mais próximo do caso de
• Em muitos
paradacasos, oferece soluções naturais e simples para problemas
n com
= n comandos
* fatorial
n - 1
que são difíceisfatorial
de resolver
iterativos
► Num
dado momento, o problema se reduz a um caso de
parada, que permite a resolução do demais casos
n * n – 1 (C)
* 2008
n Gustavo
– 2 Motta
* ... *
1
26
6. Comandos iterativos e recursão
► Recursão
 Exemplo: torres de Hanói
► Objetivo:
mover os 5 discos do pino 1 para o pino 3,
obedecendo as seguintes regras
 Apenas um disco pode ser movido por vez, sempre o disco no
topo de algum pino
 Um disco de diâmetro maior jamais pode ser colocado sobre um
disco com diâmetro menor
1
1
2
3
4
5
2
(C) 2008 Gustavo Motta
3
27
6. Comandos iterativos e recursão
► Recursão
 Exemplo: torres de Hanói
► Solução
 Caso de parada
► Mover um único disco de um pino para outro, por exemplo,
mover o disco 1 para o pino 3
 Versão reduzida do problema
► 1. Mover 4 discos do pino 1 para o pino 2
► 2. Mover o disco 5 para o pino 3
► 3. Mover 4 discos do pino 2 para o pino 3
1
1
2
3
4
5
2
(C) 2008 Gustavo Motta
3
28
6. Comandos iterativos e recursão
► Recursão
 Exemplo: torres de Hanói
► Solução
 Refinamento do passo 1
► 1. Mover 4 discos do pino 1 para o pino 2
1.1 Mover 3 discos do pino 1 para o pino 3
1.2 Mover o disco 4 do pino 1 para o pino 2
1.3 Mover 3 discos do pino 3 para o pino 2
1
1
2
3
4
5
2
(C) 2008 Gustavo Motta
3
29
6. Comandos iterativos e recursão
► Recursão
 Exemplo: torres de Hanói
► Solução
 Refinamento do passo 1.1
► 1.1 Mover 3 discos do pino 1 para o pino 3
1.1.1 Mover 2 discos do pino 1 para o pino 2
1.1.2 Mover o disco 3 do pino 1 para o pino 3
1.1.3 Mover 2 discos do pino 2 para o pino 3
1
1
2
3
4
5
2
(C) 2008 Gustavo Motta
3
30
6. Comandos iterativos e recursão
► Recursão
 Exemplo: torres de Hanói
► Solução
 Refinamento do passo 1.1.1
► 1.1.1 Mover 2 discos do pino 1 para o pino 2
1.1.1 Mover 1 disco do pino 1 para o pino 3
1.1.2 Mover o disco 2 do pino 1 para o pino 2
1.1.3 Mover 1 disco do pino 3 para o pino 2
1
1
2
3
4
5
2
(C) 2008 Gustavo Motta
3
31
6. Comandos iterativos e recursão
► Recursão
 Exemplo: torres de Hanói
► Solução
 Versão generalizada da solução
► 1. Caso N > 0
1.1 Mover os (N – 1) primeiros discos do pino 1 para o pino 2
1.2 Mover o disco N para o pino final
1.3 Mover os (N – 1) primeiros discos do pino 2 para o pino 3
1
1
2
3
4
5
2
(C) 2008 Gustavo Motta
3
32
6. Comandos iterativos e recursão
► Recursão
 Exemplo: torres de Hanói
► Solução
em Java
void torresDeHanói(int númeroDeDiscos,
String origem,String destino,
String auxiliar) {
if (númeroDeDiscos > 0) {
torresDeHanói(númeroDeDiscos - 1,origem,auxiliar,destino);
System.out.println("Mover disco "+númeroDeDiscos+
" do "+origem+" para o"+destino);
torresDeHanói(númeroDeDiscos - 1,auxiliar,destino,origem);
}
}
(C) 2008 Gustavo Motta
33
6. Comandos iterativos e recursão
► Recursão
 Exemplo: torres de Hanói
► Solução
em Java
N
= 2
Origem "p1","p3","p2")
= “p1”
torresDeHanói(3,
Destino = “p2”
auxiliar = “p3”
torresDeHanói(1, “p1”, “p3”, “p2”)
Mover disco 2 de p1 para p2
torresDeHanói(1, “p3”, “p2”, “p1”)
return
N
= 3
Origem
= “p1”
Destino = “p3”
auxiliar = “p2”
torresDeHanói(2, “p1”, “p2”, “p3”)
Mover disco 3 de p1 para p3
torresDeHanói(2, “p2”, “p3”, “p1”)
return
N
= 1
Origem
= “p1”
Destino = “p3”
auxiliar = “p2”
Mover disco 1 de p1 para p3
return
N
= 1
Origem
= “p3”
Destino = “p2”
auxiliar = “p1”
Mover disco 1 de p3 para p2
return
N
= 1
Origem
= “p2”
Destino = “p1”
auxiliar = “p3”
Mover disco 1 de p2 para p1
return
N
= 1
Origem
= “p1”
Destino = “p3”
auxiliar = “p2”
Mover disco 1 de p1 para p3
return
N
= 2
Origem
= “p2”
Destino = “p3”
auxiliar = “p1”
torresDeHanói(1, “p2”, “p1”, “p3”)
Mover
disco
(C) 2008
Gustavo
Motta2
de p2 para p3
torresDeHanói(1, “p1”, “p3”, “p2”)
return
34