Recursividade

Share

Uma definição recursiva é um termo que usa a si mesmo para se descrever. Em algoritmos, vamos definir que há recursividade quando uma função ou procedimento faz uma chamada a si mesma. Neste texto vamos apresentar como projetar funções recursivas e os principais cuidados a serem tomados durante o seu projeto e uso.

A recursividade é uma forma de repetição e em vários casos o seu uso pode simplificar um problema que seria mais difícil de ser resolvido com uma estrutura de repetição tradicional. Ao utilizar estruturas recursivas, deve-se tomar um cuidado extra pois um projeto ruim pode conduzir ao equivalente dos “laços infinitos”. Por exemplo, considere o programa abaixo que define um procedimento que imprime um número passado como parâmetro:

#include <stdio.h>
void imprimaN(int n){
   printf("%d\n", n);
}
 
int main(){
  imprimaN(1);
}

O procedimento acima não é um procedimento recursivo pois não faz uma chamada a si mesmo. Façamos então a seguinte modificação para que o procedimento imprima o valor de n e em seguida o de n+1:

#include <stdio.h>
void imprimaNRecInf(int n){
   printf("%d\n", n);
   imprimaNRecInf(n+1);
}
 
int main(){
  imprimaNRecInf(1);
}

O procedimento imprimaNRecInf() é um procedimento recursivo pois ele faz uma chamada a ele próprio em seu corpo. Este procedimento apresenta o problema de não ter um limite definido: independente do valor de n ele faz uma cópia de si mesmo com o parâmetro n+1. Em teoria, isto continuaria indefinidamente mas na prática o comportamento é diferente. Como cada nova chamada a função ou procedimento ocupa uma pequena quantidade de memória e há quantidade limitada para nosso programa, o número de vezes que a função recursiva pode ser chamada é finito. Quando o limite é atingido o processo é interrompido.

Para evitar o estouro de memória devemos adicionar um teste de guarda logo no início da função:

#include <stdio.h>
void imprimaNRec(int n){
   if(n>10) {
      return;
   } 
   printf("%d\n", n);
   imprimaNRec(n+1);
}
 
int main(){
  imprimaNRec(1);
}

O procedimento acima sempre verifica se a sua condição de parada foi atendida. Se de acordo com seus parâmetros atuais tal condição não for atendida, ela cria novas funções filha com parâmetros diferentes.

Para nos assegurarmos que uma função recursiva não vai “explodir”, devemos tomar as seguintes precauções:

  • Testar se os parâmetros atuais indicam o término;
  • Fazer as operações necessárias usando os parâmetros atuais;
  • Chamar a própria função recursivamente, alterando os parâmetros de forma que estes vão em algum momento tender para a condição de parada.

Exemplo 1

Construir um procedimento que imprime na tela números de 1 a 100. O seguinte programa faz uma chamada ao procedimento conta() que resolve o problema de forma iterativa, ou seja, usando uma estrutura de repetição.

/*
 * Construa um procedimento iterativo para imprimir na 
 * tela os números de 1 até 100
 */
#include <stdio.h>
void conta(){
   int i;
   for(i = 1; i<=100; i++){
      printf("%d\n",i);
   }
}
 
int main(){
   conta();
}

Vamos trocar o procedimento iterativo por um recursivo, o contaRec(). Para isto precisamos definir uma condição de parada (condição base) para interromper o processo. Já queremos contar até 100, podemos definir que qualquer valor acima de 100 indica que o objetivo já foi alcançado.

/*
 * Construa um procedimento recursivo para imprimir na 
 * tela os números de 1 até 100
 */
#include <stdio.h>
void contaRec(int i){
   if(i > 100){
      return; 
   }
   printf("%d\n",i);
   contaRec(i+1);
}
 
int main(){
   contaRec(1);
}

O contaRec() primeiramente testa se a condição de parada já foi atingida (caso base). Neste caso ele faz uma chamada a return() para garantir que não vai continuar a execução e vai devolver o controle para quem a chamou. Não sendo atingida uma condição base, o procedimento faz o que tem que fazer com seus parâmetros, no caso apenas (imprimir o valor) e em seguida faz uma chamada a ele mesmo, porém com o parâmetro atual incrementado em 1. Sendo observado que o parâmetro vai ser incrementado em 1 cada vez que um procedimento é chamado, podemos concluir que ele vai atingir a condição de parada em algum momento.

Exemplo 2

Construir uma função iterativa para calcular a soma dos números inteiros de 1 até 20. A versão iterativa é feita usando uma variável local para guardar o valor da soma:

/*
 * Construa uma função iterativa para calcular a 
 * soma dos números inteiros de 1 até 20
 */
#include <stdio.h>
int soma(){
   int i, soma = 0;
   for(i = 1; i<=20; i++){
      soma = soma+i;
   }
   return soma;
}
 
int main(){
   printf("%d\n",soma());
}

Para alterarmos a função precisamos encontrar uma forma de defini-la recursivamente e uma condição base. Seja uma função S(100) = 100+99+98+…+2+1 que retorne o resultado da soma de 1 a 100. Podemos dizer que S(100) = 100 + S(99) e S(99) = 99+S(98), e assim até que S(1) = 1. Se trocarmos o 100 por uma constante N, temos que S(N) = N+S(N-1) e S(1) = 1, que podemos usar como nossa definição recursiva e nosso caso base:

/*
 * Construa uma função recursiva para somar os 
 * numeros inteiros de 1 até 100
 */
#include <stdio.h>
int somaRec(int N){
   if(N == 1){
      return 1; 
   }
   return N+somaRec(N-1);
}
 
int main(){
   printf("%d\n", somaRec(1,0));
}

A função somaRec() é responsável por devolver o resultado para quem a chamou. Em último caso, quando a contagem atingiu o limite N=1 o valor de retorno é 1 e todas as funções acima recebem o resultado para realizar a conta.

Exemplo 3

Algumas funções matemáticas já possuem definições na forma recursiva e sua implementação fica muito facil. Por exemplo o fatorial N! pode ser definido como N!= Nx(N-1)! e 0! = 1. Façamos as implementações iterativa e recursiva de uma função fatorial.

A versão iterativa pode ser feita com um laço simples fazendo variando uma variável do seu valor inicial até N:

/* 
 * Construir uma função iterativa que calcule o fatorial de um
 * número passado como parâmetro.
 */
#include <stdio.h>
 
int fat(int N){
   int fatorial = 1;
   int i;
   for(i=N;i>1;i--){
      fatorial = fatorial*i;
   }
   return fatorial;
}
 
int main(){
   int n;
   scanf("%d", &n);
   printf("%d! = %d\n",n,fat(n));
}

A versão recursiva pode ser obtida diretamente da definição matemática N!= Nx(N-1)! e 0!=1.

/* 
 * Construir uma função recursiva que calcule o fatorial de um
 * número passado como parâmetro.
 */
#include <stdio.h>
 
int fatRec(int N){
   if(N == 0){
      return 1;
   }
   return N*fatRec(N-1);
}
 
int main(){
   int n;
   scanf("%d", &n);
   printf("%d! = %d\n",n,fatRec(n));
}

Exemplo 4

Outra função conhecida por sua definição recursiva é a seqüência de Fibonacci onde um termo é formado pela soma dos dois termos anteriores: F(n) = F(n-2) + F(n-1); com F(0) = 1 e F(1) = 1.

Podemos pensar na solução iterativa por realizar a soma dos termos N-2 vezes, com N≤3.

/* 
 * Construir uma função iterativa que calcule o termo da série de Fibonacci
 * de um número passado como parâmetro.
 */
#include <stdio.h>
 
int fibo(int N){
   int A = 0;
   int B = 1;
   int C;
   int i;
   for(i = 0; i<N; i++) {
      C = A + B;
      A = B;
      B = C;
   }
   return A;
}
 
int main(){
   int n;
   scanf("%d", &n);
   printf("fibo(%d) = %d\n",n,fibo(n));
}

Novamente temos que a versão recursiva diretamente da definição:

/* 
 * Construir uma função recursiva que calcule o termo da série de Fibonacci
 * de um número passado como parâmetro.
 */
#include <stdio.h>
 
int fiboRec(int N){
   if(N == 0){
      return 0;
   }
   if(N == 1){
      return 1;
   }
   return fiboRec(N-2)+fiboRec(N-1);
}
 
int main(){
   int n;
   scanf("%d", &n);
   printf("fibo(%d) = %d\n",n,fiboRec(n));
}

Vale lembrar que dependendo da quantidade de iterações necessárias os algoritmos recursivos podem apresentar um menor desempenho se comparado aos iterativos. Os algoritmos recursivos associados podem se tornar de difícil depuração e manutenção, mesmo que sejam mais compactos que suas versões iterativas. O uso ou não de funções recursivas fica refém de um estudo de custo/benefício entre tempo de desenvolvimento e recursos como tempo de execução e memória disponível.

Share
Um comentário sobre “Recursividade
  1. Rodrigo disse:

    Parabéns pelas explicações…
    Eu ja estava surtando com tantos textos técnicos. Seus exemplos simples e completos me auxiliaram muito.
    Obrigado

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *

*