Recursão e algoritmos recursivos

Ao tentar resolver o problema,
encontrei obstáculos dentro de obstáculos.
Por isso, adotei uma solução recursiva.

— aluno S.Y.

To understand recursion,
we must first understand recursion.

— anônimo

Para fazer um procedimento recursivo
é preciso ter fé.

— prof. Siang Wun Song

Muitos problemas 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 um tal problema, podemos aplicar o seguinte método:

A aplicação desse método produz um algoritmo recursivo. Para mostrar como isso funciona, examinaremos um exemplo concreto.

Um exemplo

Considere o seguinte problema:   Determinar o valor de um elemento máximo de um vetor  v[0..n-1] . É claro que o problema só faz sentido se o vetor não é vazio, ou seja, se n1.

Para preparar o terreno, examine uma tradicional solução iterativa do problema:

int maximo (int n, int v[]) { 
   int j, x;
   x = v[0];
   for (j = 1; j < n; j += 1)
      if (x < v[j]) x = v[j];
   return x;
}

Exercícios 1

  1. Considere a função iterativa  maximo  acima.  Faz sentido trocar  x = v[0]  por  x = 0, como fazem alguns programadores descuidados?  Faz sentido trocar  x = v[0]  por  x = INT_MIN?  Faz sentido trocar  x < v[j]  por  x <= v[j]?  [Veja uma solução parcial.]
  2. A função abaixo promete encontrar o valor de um elemento máximo de v[0..n-1]. A função cumpre a promessa?
    int maxi (int n, int v[]) {       
       int j, m = v[0];
       for (j = 1; j < n; ++j)
          if (v[j-1] < v[j]) m = v[j];
       return m;
    }
    
  3. Que tipos de problemas um algoritmo recursivo é capaz de resolver?

Solução recursiva do problema

Eis uma solução recursiva do problema da seção anterior:

int 
maximoR (int n, int v[])
{ 
   if (n == 1)
      return v[0];
   else {
      int x;
      x = maximoR (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 do algoritmo tem a mesma forma que uma prova por indução.  Se n vale 1 então v[0] é o único elemento relevante do vetor e portanto v[0] é o máximo.  Agora suponha que n vale mais que 1. Então nosso vetor tem duas partes: v[0..n-2] e v[n-1] e portanto o valor que procuramos é o maior dentre

v[n-1]      e      um máximo de v[0..n-2].

(Eis um roteiro que pode ajudar a verificar se a função está correta:  1. Escreva o que a função deve fazer.  2. Verifique que a função de fato faz o que deveria quando n é pequeno, ou seja, quando n vale 1.  3. Agora imagine que n é grande, ou seja, n > 1, e verifique que a função faz a coisa certa supondo que faria a coisa certa se no lugar de n tivéssemos algo menor que n.)

Para que uma função recursiva seja compreensível, é muito importante que o autor da função diga, explicitamente, o que a função faz. Portanto, eu deveria escrever o seguinte comentário antes do código:

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

Desempenho.   Algumas pessoas acreditam que funções recursivas são inerentemente ineficientes e lentas, mas isso não passa de lenda.  Talvez a lenda tenha origem em usos descuidadas da recursão, como num dos exercícios abaixo(Nem tudo são flores, entretanto. É preciso lembrar do espaço de memória que a pilha de recursão consome.)

Como o computador executa um algoritmo recursivo?  Embora relevante, essa pergunta será ignorada por enquanto. Veja o capítulo sobre pilhas.

Exercícios 2

  1. Verifique que a seguinte maneira de escrever a função maximoR é exatamente equivalente à vista acima:
    int maximoR (int n, int v[]) {
       int x;
       if (n == 1) x = v[0];
       else {
          x = maximoR (n-1, v); 
          if (x < v[n-1]) x = v[n-1];
       }
       return x;
    }
    
  2. Verifique que a seguinte maneira de escrever a função maximoR é exatamente equivalente à vista acima:
    int maximoR (int n, int v[]) {
       int x; 
       if (n == 1) return v[0];
       x = maximoR (n-1, v);
       if (x > v[n-1]) return x;
       else return v[n-1]; 
    }
    
  3. Critique a seguinte função recursiva; ela promete encontrar o valor de um elemento máximo de v[0..n-1].
    int maximoR1 (int n, int v[]) {       
       int x;
       if (n == 1) return v[0];    
       if (n == 2) {
          if (v[0] < v[1]) return v[1];
          else return v[0];
       }
       x = maximoR1 (n-1, v);
       if (x < v[n-1]) return v[n-1];
       else return x;
    }
    
  4. Critique a seguinte função recursiva, que promete encontrar o valor de um elemento máximo de v[0..n-1].
    int maximoR2 (int n, int v[]) {
       if (n == 1) return v[0];
       if (maximoR2 (n-1, v) < v[n-1]) 
          return v[n-1];
       else 
          return maximoR2 (n-1, v);
    }
    
  5. Escreva uma função recursiva maxmin que calcule o valor de um elemento máximo e o valor de um elemento mínimo de um vetor v[0..n-1]. Quantas comparações envolvendo os elementos do vetor sua função faz?
  6. Programa de teste.  Escreva um pequeno programa para testar a função recursiva maximoR.  O seu programa deve esperar que o usuário digite uma sequência de números e em seguida devolver o valor do maior dos números digitados.  [Veja uma solução.]   Agora faça uma nova versão do programa para determinar um elemento máximo de um vetor aleatório. Acrescente ao seu programa uma função que confira a resposta dada por maximoR.  [Veja uma solução]
  7. Escreva uma função recursiva que calcule a soma dos elementos positivos do vetor de inteiros  v[0..n-1].  O problema faz sentido quando n é igual a 0?  Quanto deve valer a soma nesse caso?  [Veja solução.]
  8. Escreva uma função recursiva que calcule o produto dos elementos estritamente positivos de um vetor de inteiros  v[0..n-1].  O problema faz sentido quando todos os elementos do vetor são nulos?  O problema faz sentido quando n vale 0?  Quanto deve valer o produto nesses casos?

Outra solução recursiva

A função maximoR discutida acima aplica a recursão ao segmento v[0..n-2].  É possível escrever uma versão que aplique a recursão ao segmento v[1..n-1]:

// 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 maxR (0, n, v);
}

A função maximo2 é apenas uma embalagem (= wrapper-function); o serviço pesado é executado pela função recursiva maxR:

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

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

A função maxR resolve um problema mais geral que o original.  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].  Ela usa aritmética de endereços:

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

Exercícios 3

  1. A seguinte função recursiva pretende encontrar o valor de um elemento máximo de v[p..u], supondo pu.  (O índice p aponta o primeiro elemento do vetor e o índice u aponta o último.)  A função está correta? Suponha que p e u valem 06 respectivamente e mostre a sequência, devidamente indentada, de chamadas de max.
    int max (int p, int u, int v[]) {
       if (p == u) return v[u];
       else {
          int i, x, y;
          i = (p + u)/2;
          x = max (p, i, v);
          y = max (i+1, u, v);
          if (x >= y) return x;
          else return y;
       }
    }
    
  2. Escreva uma função recursiva que calcule a soma dos elementos positivos do vetor  v[p..u-1].  O problema faz sentido quando  p é igual a u?  Quanto deve valer a soma nesse caso?
  3. Critique a documentação do seguinte código:
    // Recebe um vetor de tamanho n
    // e devolve a soma do vetor.
    int soma (int v[], int n) {
       return sss (v, n+1); 
    }
    int sss (int v[], int n) {
       if (n == 1) return 0;
       return sss (v, n-1) + v[n-1]; 
    }
    
  4. Diga o que a função abaixo faz.  Para quais valores dos parâmetros sua resposta está correta?
    int ttt (int x[], int n) {
       if (n == 0) return 0;
       if (x[n] > 100)  return x[n] + ttt (x, n-1);
       else  return ttt (x, n-1);
    }
    
  5. Escreva uma função recursiva que calcule a soma dos dígitos de um inteiro estritamente positivo n. A soma dos dígitos de 132, por exemplo, é 6.
  6. Escreva uma função recursiva que calcule o piso do logaritmo de N na base 2.  (Veja uma versão iterativa do exercício.)

Exercícios 4

  1. Qual o valor de X (4) se X é dada pelo seguinte código?  [Veja uma solução.]
    int X (int n) {
       if (n == 1 || n == 2) return n;
       else return X (n-1) + n * X (n-2);
    }
    
  2. Qual é o valor de f (1,10)? Escreva uma função equivalente que seja mais simples.
    double f (double x, double y) {
       if (x >= y) return (x + y)/2;
       else return f (f (x+2, y-1), f (x+1, y-2));
    }
    
  3. Qual o resultado da execução do seguinte programa?
    int ff (int n) {
       if (n == 1) return 1;
       if (n % 2 == 0) return ff (n/2);
       return ff ((n-1)/2) + ff ((n+1)/2);
    }
    int main (void) {
       printf ("%d", ff(7)); 
       return EXIT_SUCCESS;
    }
    
  4. Execute fusc (7,0). Mostre a sequência, devidamente indentada, das chamadas a fusc.
    int fusc (int n, int profund) {
      int i;
      for (i = 0; i < profund; ++i) 
         printf ("  ");
      printf ("fusc(%d,%d)\n", n, profund);
      if (n = 1) 
         return 1;
      if (n % 2 == 0) 
         return fusc (n/2, profund+1);
      return fusc ((n-1)/2, profund+1) + 
             fusc ((n+1)/2, profund+1);
    }
    
  5. Importante.  Critique a seguinte função recursiva:
    int XX (int n) {
       if (n == 0) return 0;
       else return XX (n/3+1) + n;
    }
    
  6. Fibonacci.  A função de Fibonacci é definida assim:   F(0) = 0F(1) = 1   e   F(n) = F(n-1) + F(n-2)   para n > 1. Descreva a função F em linguagem C. Faça uma versão iterativa e uma recursiva.
  7. Seja F a versão recursiva da função de Fibonacci.  O cálculo do valor da expressão F(3) provocará a seguinte sequência de invocações da função:
       F(3)
         F(2)
           F(1)
           F(0)
         F(1)
    
    Qual a sequência de invocações da função durante o cálculode F(5)?
  8. Euclides.  A seguinte função calcula o maior divisor comum dos inteiros estritamente positivos m e n. Escreva uma função recursiva equivalente.
    int Euclides (int m, int n) {
       int r;
       do {
          r = m % n; 
          m = n; 
          n = r;
       } while (r != 0);
       return m; 
    }
    
  9. Exponenciação.  Escreva uma função recursiva eficiente que receba inteiros estritamente positivos k e n e calcule kn.  (Suponha que kn cabe em um int.)  Quantas multiplicações sua função executa aproximadamente?
    .
    . -
    . --
    . -
    . ---
    . -
    . --
    . -
    . ----
    . -
    . --
    . -
    . ---
    . -
    . --
    . -
    .
    
  10. Régua inglesa [Sedgewick 5.8, Roberts 5.11]  Escreva uma função recursiva que imprima uma régua de ordem n no intervalo [0..2n].  O traço no ponto médio da régua deve ter comprimento n, os traços nos pontos médios dos subintervalos superior e inferior devem ter comprimento n−1, e assim por diante.  A figura mostra uma régua de ordem 4.

Perguntas e respostas