Compreendendo a Recursão

Como você viu, C permite dividir seu programa em partes menores chamadas funções. Usando funções, o programa torna-se mais fácil de compreender, programar e testar. Além disso, você normalmente poderá usar as funções que criar para um programa dentro de outro programa. À medida que seus programas são executados, uma função pode chamar outra, que chama outra, que pode, por sua vez, chamar várias outras funções. Dentro da série, cada função executa uma operação específica. C permite até mesmo que uma função chame a si mesma ! Uma função recursiva é uma função que chama a si mesma para executar uma operação específica. O processo de uma função chamar a si mesma é conhecido como recursão. Á medida que a complexidade de seus programas e funções aumentar, você descobrirá que pode facilmente definir muitas operações em termos recursivos. Quando você usa programas e funções complexas, pode querer criar urna função recursiva. Por exemplo, muitos livros sobre programação usam o problema do fatorial para ilustrar como a recursão funciona. O fatorial de 1 é 1. O fatorial de 2 é 2*1. O fatorial de 3 é 3*2*1. Da mesma forma, o fatorial de 4 é 4*3*2*1. O processo do fatorial pode prosseguir infinitamente. Se você examinar o processamento que o fatorial realiza, verá que o fatorial de 4, por exemplo, é na verdade 4 vezes o fatorial de 3 (3*2*1). Da mesma forma, o fatorial de 3 é, na verdade, 3 vezes o fatorial de 2 (2*1). O fatorial de 2 é 2 vezes o fatorial de 1 (1). A Tabela abaixo ilustra o processamento do fatorial.

O programa a seguir,cria a função recursiva fatorial, e, depois, usa a função para retornar os valores de fatorial para os valores de 1 até 5:

#include "stdio.h"

int fatorial (int valor)
{
      if (valor == 1)
         return (1);
      else
         return (valor * fatorial (valor-1));
}

void main (void)
{
      int i;

      for (i = 1; i <= 5; i++)
         printf ("O fatorial de %d é %d\n", i, fatorial (i));
}

Compreendendo a Função Recursiva Fatorial

Apresentando a função fatorial para ilustrar a recursão. A função fatorial recebe um valor de parâmetro específico. Quando a função inicia, ela primeiro verifica se o valor é 1, que, pela definição de fatorial, é 1. Se o valor for 1, a função retornará o valor 1. Se o valor não for 1, a função retornará o resultado do valor vezes o fatorial do valor menos 1. Por exemplo, suponha que o programa chame a função com o valor 3. A função retornará o resultado de 3 * fatorial (3-1). Quando C encontrar a chamada da função dentro do comando return, C chamará a função uma Segunda vez - desta vez com valor de 3-1 ou 2. Novamente, como o valor não é 1, a função retorna o resultado de 2 * fatorial (2-1). Na terceira vez em que a função é chamada, o valor é 1. Como resultado, a função retorna o valor para a função chamadora, o que, por sua vez, retorna o resultado de 2*1 para a função chamadora. A função chamadora então retorna o resultado de 3*2*1 para sua função chamadora.
Uma função recursiva é similar a uma construção de repetição, em que você precisa especificar a condição de término. Se você não especificar uma condição de término, a função nunca terá fim. No problema do fatorial, a condição de término é o fatorial de 1, que é, por definição, 1.

Programando Outro Exemplo Recursivo

A dica anterior, por sua vez, apresentou e explicou a função recursiva fatorial. Como a recursão pode ser um conceito difícil, esta dica apresenta mais uma função recursiva, exibe_invert, que exibirá as letras de uma string ABCDE em ordem invertida:

#include "stdio.h"

void exibe_invert (char *string)
{
      if (*string)
         {
            exibe_invert (string+1);
            putchar (*string);
         }
}

void main (void)
{
      exibe_invert ("ABCDE");
}

Exibindo Valores Para Compreender Melhor a Recursão

Para lhe ajudar a compreender melhor o processo de recursão, o programa abaixo inclui comandos printf dentro da função fatorial para ilustrar o processamento recursivo da função dentro do programa:

#include "stdio.h"

int fatorial (int valor)
{
   printf ("Em fatorial com o valor %d\n", valor);
   if (valor == 1)
   {
      printf ("Retornando o valor 1\n");
      return (1);
   }
   else
   {
      printf ("Retornando %d * fatorial(%d)\n",valor,valor-1);
      return (valor * fatorial (valor-1));
   }
}

void main (void)
{
      printf ("O fatorial de 4 é %d, fatorial (4));
}

Quando você compilar e executar o programa, sua tela exibirá a seguinte saída:

Em fatorial com o valor 4
Retornando 4 * fatorial (3)
Em fatorial com o valor 3
Retornando 3 * fatorial (2)
Em fatorial com o valor 2
Retornando 2 * fatorial (1)
Em fatorial com o valor 1
Retornando o valor 1
O fatorial de 4 é 24

Inserir o comando printf em todas as funções recursivas lhe ajudará a compreender o processamento que as funções executam.

Compreendendo a Recursão Direta e Indireta

Quando uma função chama a si mesma para realizar uma tarefa, a função executa uma recursão direta. Após você ter examinado algumas funções recursivas, deve poder compreender a maioria das funções que usa a recursão direta. Uma forma de recursão mais difícil, a recursão indireta, ocorre quando uma função (a função A) chama outra função (a função B), que, por sua vez, chama a função original (função A). Como a recursão indireta pode resultar em código que é muito dificil de compreender como regra você deverá evitar usar a recursão indireta sempre que possível.

Decidindo Usar ou Não a Recursão

Ao criar funções usando recursão, você pode criar soluções elegantes para muitos problemas. No entanto, você deve evitar a recursão sempre que possível por duas razões. Primeiro, as funções recursivas podem ser difíceis de compreender para os programadores novatos. Segundo, como regra, as funções recursivas normalmente são consideravelmente mais lentas que suas correspondentes não-recursivas. O programa a seguir, chama a função não-recursiva, string_tamanho, com a string "Bíblia do Programador CIC++, do Jamsa!" 100.000 vezes, e, depois, exibe a quantidade de tempo necessária para realizar o processamento:

#include "stdio.h"
#include "time.h"

int string_tamanho (const char *str)
{
      int tamanho = 0;

      while (*str++)
         tamanho++;
      return (tamanho);
}

void main (void)
{
   long int contador;
   time_t tempo_inicio, tempo_fim;
   time (&tempo_inicio);
   for (contador = 0; contador < 100000L; contador++)
        string_tamanho ("Bíblia do Programador C/C++, do Jamsa!");
   time (&tempo_fim);
   printf ("Tempo de processamento %d\n",tempo_fim-tempo_inicio);
}

Em seguida, o programa usa uma implementação recursiva da função string_tamanho para realizar o mesmo processamento:

#include "stdio.h"
#include "time.h"

int string_tamanho (const char *str)
{
      if (*str)
         return (1 + string_tamanho (str+1));
      else
         return (0);
}

void main (void)
{
   long int contador;

   time_t tempo_inicio, tempo_fim;
   time (&tempo_inicio);
   for (contador = 0; contador < 100000L; contador++)
        string_tamanho ("Bíblia do Programador C/C++, do Jamsa!");
   time (&tempo_fim);
   printf ("Tempo de processamento %d\n",tempo_fim-tempo_inicio);
}

Experimente esses programas, por exemplo, alterando o número de chamadas da função para um ou dois milhões. Como você descobrirá, a função não-recursiva é executada consideravelmente mais depressa que sua correspondente recursiva. Portanto, quando você projeta uma função recursiva, tenha em mente que pode acrescentar sobrecarga significativa ao tempo de execução do seu programa.

Uma função recursiva é uma função que chama a si mesma para realizar uma tarefa específica. Como você aprendeu uma razão para evitar o uso da recursão é que as funções recursivas em geral são consideravelmente mais lentas que suas correspondentes não-recursivas. As funções recursivas são lentas porque a sobrecarga da chamada ocorre toda vez que a função é chamada. Como já foi detalhado, toda vez que seu programa chama uma função, o compilador C coloca na pilha o endereço do comando que segue imediatamente a chamada da função (chamado endereço de retorno). Em seguida, o compilador coloca os valores dos parâmetros na pilha. Quando a função termina, o sistema operacional do computador retira o endereço de retorno da pilha no contador de programa da CPU. Embora os computadores possam realizar essas operações muito rapidamente, elas ainda requerem tempo. Como um exemplo, assuma que você chame a função fatorial recursiva com o valor 50. A função chamará a si mesma 49 vezes. Se cada função somar 10 milissegundos ao tempo de execução do seu programa, a função será meio segundo mais lenta que uma correspondente não-recursiva, que tem a sobrecarga de uma única chamada. Uma sobrecarga de meio segundo pode não parecer muito, porém, assuma que o programa chame a função 10 vezes. O retardo de meio segundo torna-se de cinco segundos. Se o programa usa a função 100 vezes, o retardo torna-se de 50 segundos, e assim por diante. Se você estiver desenvolvendo um programa que requer máximo desempenho, deverá tentar eliminar as funções recursivas sempre que possível. Nota: Com os novos e mais rápidos microprocessadores, o retardo provocado pelas funções recursivas não é tão importante como era antigamente. No entanto, o impacto das funções recursivas ainda é significativo e você deve tentar escrever código eficiente e legível sem recursão do sempre que possível.

#include "stdio.h"

int fatorial (int valor)
{
      int result =1;
      int contador;

      for (contador = 2; contador <= valor; contador++)
         result *= contador;
      return (result);
}

void main (void)
{
      int i;

      for (i = 1; i <= 5; i++)
         printf ("O fatorial de %d é %d\n", i, fatorial (i));
}

Sempre que você eliminar a recursão dentro de seus programas usando uma construção de laço de repetição, geralmente aumentará o desempenho do seu programa. No entanto, tenha em mente que os usuários podem compreender mais facilmente algumas operações que seus programas executarão quando você implementar as operações com recursão. Exatamente como algumas vezes você precisa escolher entre velocidade e consumo de memória do seu programa, algumas vezes precisa escolher entre legibilidade e desempenho.