Recursividade em C

Por: Eduardo Casavella
Chamamos de recursividade ou recursão quando uma função chama a si mesma.

Sim amigos, isto é possível, uma função pode invocar a si mesma!
Como funciona a recursividade?

Em uma função recursiva, a cada chamada é criada na memória uma nova ocorrência da função com comandos e variáveis “isolados” das ocorrências anteriores.

A função é executada até que todas as ocorrências tenham sido resolvidas.

Porém um problema que surge ao usar a recursividade é como fazê-la parar. Caso o programador não tenha cuidado é fácil cair num loop infinito recursivo o qual pode inclusive esgotar a memória…

Toda recursividade é composta por um caso base e pelas chamadas recursivas,.

Caso base: é o caso mais simples. É usada uma condição em que se resolve o problema com facilidade.

Chamadas Recursivas: procuram simplificar o problema de tal forma que convergem para o caso base.

Vantagens da recursividade

  • Torna a escrita do código mais simples e elegante, tornando-o fácil de entender e de manter.

Desvantagens da recursividade

  • Quando o loop recursivo é muito grande é consumida muita memória nas chamadas a diversos níveis de recursão, pois cada chamada recursiva aloca memória para os parâmetros, variáveis locais e de controle.
  • Em muitos casos uma solução iterativa gasta menos memória, e torna-se mais eficiente em termos de performance do que usar recursão.

Exemplo clássico de recursividade: fatorial


//Cálculo de fatorial com função recursiva
#include <stdio.h>
#include <conio.h>

//protótipo da função fatorial
double fatorial(int n);

int main(void)
{
  int numero;
  double f;

  printf("Digite o numero que deseja calcular o fatorial: ");
  scanf("%d",&numero);

  //chamada da função fatorial
  f = fatorial(numero);

  printf("Fatorial de %d = %.0lf",numero,f);

  getch();
  return 0;
}

//Função recursiva que calcula o fatorial
//de um numero inteiro n
double fatorial(int n)
{

  double vfat;

  if ( n <= 1 )
     //Caso base: fatorial de n <= 1 retorna 1
     return (1);
  else
  {
     //Chamada recursiva
     vfat = n * fatorial(n - 1);
     return (vfat);
  }
}

 

Tela de Execução

Tela de execução classico de recursividade

Tela de execução clássico de recursividade fatorial

Explicação do código

No programa acima, se o número n for menor ou igual a 1 o valor 1 será retornado e a função encerrada, sem necessidade de chamadas recursivas. Caso contrário dá-se início a chamadas recursivas até cair no caso mais simples que é resolvido e assim, as chamadas retornam valores de forma a solucionar o cálculo.

Veja a figura a seguir que representa as chamadas recursivas para o cálculo de 5!

calculo recursivo 5

Cálculo recursivo 5!

 

Até a próxima!