Projeto de Algoritmos  |  Linguagem C  |  Índice  |  English

Recursão e algoritmos recursivos

Muitos problemas computacionais têm a seguinte propriedade: cada instância do problema contém uma instância menor do mesmo problema. Dizemos que esses problemas têm estrutura recursiva.  Para resolver uma instância de um problema desse tipo, podemos aplicar o seguinte método:

• se a instância em questão for pequena,

  resolva-a diretamente (use força bruta se necessário);

• senão

  reduza-a a uma instância menor do mesmo problema,

  aplique o método à instância menor,

  volte à instância original.

O programador só precisa mostrar como obter uma solução da instância original a partir de uma solução da instância menor; o computador faz o resto.  A aplicação desse método produz um algoritmo recursivo.

Um exemplo

Para ilustrar o conceito de algoritmo recursivo, considere o seguinte problema:  Encontrar o valor de um elemento máximo de um vetor  v[0..n-1].  (O problema já foi mencionado num dos exercícios na página Vetores.)

Observe que o problema só faz sentido se o vetor não é vazio, ou seja, se n ≥ 1.  Eis uma função recursiva que resolve o problema:

// Ao receber v e n >= 1, a função devolve
// o valor de um elemento máximo do
// vetor v[0..n-1].

int 
maximo (int n, int v[])
{ 
   if (n == 1)
      return v[0];
   else {
      int x;
      x = maximo (n-1, v);
      // x é o máximo de v[0..n-2] 
      if (x > v[n-1]) return x;
      else return v[n-1]; 
   }
}

A análise da correção da função tem a forma de uma prova por indução.  Para começar, considere uma instância em que n vale 1. Nessa instância, a resposta que a função devolve, v[0], está correta pois v[0] é o único elemento relevante do vetor.  Agora considere uma instância em que n é maior que 1. Nessa instância, o vetor tem duas partes não vazias:

v[0..n-2]  e  v[n-1].

Podemos supor que a função resolve corretamente a instância v[0..n-2] do problema, pois essa instância é menor que a original. Portanto, depois da linha x = maximo (n-1, v), podemos supor que x é um máximo correto de v[0..n-2]. Logo, a solução da instância original é o maior dos números x e v[n-1]. E é justamente esse o número que a função calcula e devolve.  Isso conclui a prova de que a função maximo está correta.

Para que uma função recursiva seja compreensível, é essencial que o autor diga o que a função faz. Isso deve ser dito de maneira explicita e completa, como fiz acima no comentário que precede o código da função.

Como o computador executa uma função recursiva?  Embora relevante e importante, essa pergunta será ignorada por enquanto. (Mas você pode ver o apêndice A pilha de execução de um programa do capítulo Pilhas.)  Vamos nos limitar a mostra um exemplo de execução. Se v[0..3] é o vetor  77 88 66 99  então teremos a seguinte sequência de chamadas da função:

rmaximum(4,v)
│ rmaximum(3,v) 
│ │ rmaximum(2,v) 
│ │ │ rmaximum(1,v)
│ │ │ └──────────── returns 77
│ │ └────────────── returns 88
│ └──────────────── returns 88
└────────────────── returns 99

Desempenho.  Algumas pessoas acreditam que funções recursivas são inerentemente lentas, mas isso não passa de lenda.  Talvez a lenda tenha origem em certos usos descuidadas da recursão, como em alguns dos exercícios abaixo.  (Nem tudo são flores, entretanto: o espaço de memória que uma função recursiva consome para rascunho pode ser grande.)

Exercícios 1

Outra solução

A função maximo discutida acima reduz a instância v[0..n-1] do problema à instância v[0..n-2].  Podemos escrever uma função que reduza v[0..n-1] a v[1..n-1], ou seja, empurre pra direita o início do vetor:

// Ao receber v e n >= 1, esta função devolve
// o valor de um elemento máximo do vetor
// v[0..n-1].

int 
maximo2 (int n, int v[]) 
{
   return max (0, n, v);
}

A função maximo2 é apenas uma embalagem ou invólucro (= wrapper-function); o serviço propriamente dito é executado pela função recursiva max:

// Recebe v e i < n e devolve o valor de
// um elemento máximo do vetor v[i..n-1].

int 
max (int i, int n, int v[]) 
{
   if (i == n-1) return v[i];
   else {
      int x;
      x = max (i + 1, n, v);
      if (x > v[i]) return x;
      else return v[i]; 
   } 
}

A função max resolve um problema mais geral que o original (veja o parâmetro i).  A necessidade de generalizar o problema original ocorre com frequência no projeto de algoritmos recursivos.

A título de curiosidade, eis outra maneira, talvez surpreendente, de aplicar recursão ao segmento v[1..n-1] do vetor.  Ela usa aritmética de endereços em lugar do parâmetro adicional  i.

int maximo2b (int n, int v[]) {
   if (n == 1) return v[0];
   int x = maximo2b (n - 1, v + 1);
   if (x > v[0]) return x;
   return v[0];
}

Exercícios 2

Exercícios 3

Exercícios 4