Laços dentro de laços

Um laço para a linha, dois para a tabela

Um laço só resolve uma dimensão: uma fila de nomes, uma sequência de preços. Mas muita informação vive em duas dimensões, em linhas e colunas: o tabuleiro de xadrez, a planilha de notas, a grade de horários. Para percorrer uma tabela dessas, um laço não basta; precisa de dois, encaixados. O laço de fora caminha pelas linhas; para cada linha, o laço de dentro caminha por todas as colunas daquela linha. O resultado é uma varredura completa, casa por casa, como quem lê uma página inteira palavra por palavra, linha após linha. Esse é o motor por trás das matrizes, o tema do próximo módulo.

para linha de 1 até 3 faça
  para coluna de 1 até 3 faça
    escreva("(", linha, ",", coluna, ") ")
  fim
  quebra_de_linha()
fim
// imprime a grade 3x3:
// (1,1) (1,2) (1,3)
// (2,1) (2,2) (2,3)
// (3,1) (3,2) (3,3)

O laço externo conta as linhas; o interno, as colunas. São 3 x 3 = 9 posições visitadas.

O laço de dentro roda inteiro a cada volta do de fora

A chave para entender laços aninhados é essa frase: o laço interno completa TODAS as suas voltas a cada UMA volta do externo. É como um relógio: enquanto o ponteiro das horas anda uma casa, o dos minutos dá a volta completa. No exemplo da grade, quando o laço externo está na linha 1, o interno percorre as colunas 1, 2 e 3 inteiras antes de o externo avançar para a linha 2. Quem tenta acompanhar os dois ao mesmo tempo se perde; o jeito certo é congelar o externo numa linha e seguir o interno até o fim, depois avançar o externo uma casa e repetir. Teste de mesa com laços aninhados é isso: uma tabela de duas colunas anotando o valor de cada laço.

total <- 0
para i de 1 até 4 faça
  para j de 1 até 3 faça
    total <- total + 1
  fim
fim
escreva(total)

O custo que explode

Aqui vem o alerta mais importante do módulo. Como o total de execuções é o produto das voltas, os laços aninhados ficam caros rápido. Dois laços de 10 voltas dão 100 execuções, tranquilo. Dois de 1.000 voltas dão 1 milhão. Dois de 10.000 dão 100 milhões, e o programa que era instantâneo começa a travar. Pior: dobrar o tamanho dos dados não dobra o trabalho, quadruplica, porque os dois laços crescem juntos. Essa relação, em que o custo cresce com o quadrado do tamanho, tem nome e um módulo inteiro reservado para ela mais adiante (eficiência e Big-O). Por enquanto, guarde a intuição: laço dentro de laço percorrendo os mesmos dados grandes é um sinal amarelo que pede atenção.