Algoritmos recursivos

Esta página foi extraída (com algumas modificações) do capítulo 4 do livro de Eric Roberts.

Palíndromo

Um palíndromo é uma palavra que pode ser lida, indiferentemente, da esquerda para a direita ou da direita para a esquerda. Exemplo: "seres".  Eis uma função que decide se uma cadeia de caracteres é ou não um palíndromo.

#include <string.h> typedef enum {FALSE, TRUE} bool; // Esta função devolve TRUE se a cadeia de caracteres // str é um palíndromo e FALSE em caso contrário. // bool EhPalindromo( char str[]) { return Verifica( str, strlen( str)); }

O trabalho pesado é feito pela função "auxiliar" Verifica, que resolve um problema ligeiramente diferente:

// Esta função devolve TRUE se o vetor de caracteres // str[0..len-1] é um palíndromo e FALSE em caso contrário. // bool Verifica( char str[], int len) { if (len <= 1) return TRUE; else { bool x, y; x = str[0] == str[len-1]; y = Verifica( str + 1, len - 2); return x && y; } }

Eis uma outra versão (mais eficiente) da função Verifica:

bool Verifica( char str[], int len) { if (len <= 1) return TRUE; else { if (str[0] != str[len-1]) return FALSE; return Verifica( str + 1, len - 2); } }

Mais uma versão (agora a diferença é apenas cosmética):

bool Verifica( char str[], int len) { if (len <= 1) return TRUE; if (str[0] != str[len-1]) return FALSE; return Verifica( str + 1, len - 2); }

Exercícios

1. Critique a seguinte função para o problema dos palíndromos. Se a função estiver correta, escreva a documentação da função (ou seja, diga o que ela faz).

   typedef char * string;
   
   int palindromo( string str) {
      int n;
      n = strlen( str);
      if (n <= 1) return 1;
      else {
         if (str[0] != str[n-1]) return 0;
         str[n-1] = 0;
         return palindromo( str + 1);
      }
   }
   

2. [Roberts, cap.7, exr.1, p.318]  Escreva uma função recursiva que calcule xⁿ. Sua função deve fazer cerca de log₂ n multitplicações apenas.