Recursividade

A recursividade pode ser vista por muitos como um bicho de sete cabeças, porém muitas vezes pode ser a melhor maneira de resolver um determinado problema, além de ser uma forma mais legível e simples do que a forma interativa. Então vamos tentar entender como funciona a recursão:

Definição e Comparação

Você já viu um jogo de bonecas russas? A princípio, você vê apenas uma boneca, geralmente de madeira pintada, parecida com esta:

Você pode tirar a metade de cima da primeira boneca, e o que vê dentro dela? Outra boneca, um pouco menor!

Você pode tirar essa boneca de dentro da outra e separar suas metades inferior e superior. E você verá outra boneca, ainda menor:

E de novo:

Você pode continuar fazendo isso. Eventualmente você vai encontrar uma boneca russa pequenininha. Ela é formada por uma peça única, e não se abre:

Começamos com uma boneca grande, e vimos bonecas cada vez menores, até encontrar uma tão pequena que não podia conter nenhuma outra.

O que as bonecas russas têm a ver com Recursividade? Já vamos descobrir.

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

Toda função recursiva é composta por duas partes:

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.

Descobriu?

Assim como uma boneca russa tem dentro de si uma boneca menor, que tem dentro de si uma boneca ainda menor, até chegarmos a uma boneca pequena demais para ter outra dentro de si, a recursividade soluciona um problema dividindo-o em instâncias menores (chamadas recursivas) até chegar ao ponto em que não conseguimos mais dividir esse problema (caso base).

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.

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

Caso não se tenha cuidado é fácil cair em um loop infinito recursivo o qual pode inclusive esgotar a memória

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

Vamos fazer o cálculo do fatorial de um dado número. Primeiramente utilizaremos uma solução iterativa:

#include < stdio.h >
int fatorial(int num){
    int i, resultado = 1;
    for(i = 1; i <= num; i++){
	resultado = resultado * i;
    }
    return resultado;
}
int main(){
    int num, resultado;
    scanf("%d", &num);
    if(num < 0){
        printf("Erro: Numero negativo!");
    }else{
        resultado = fatorial(num);
        printf("Resultado: %d", resultado);
    }
    return 0;
}

Agora uma solução recursiva:

/*Cálculo de fatorial com função recursiva*/
#include < stdio.h >
/*Função recursiva que calcula o fatorial de um numero inteiro n*/
int fatorial(int n){
    int vfat;
    /*Caso base: fatorial de n == 0 retorna 1*/
    if(n == 0){
        return 1;
    }else{
        /*Chamada recursiva*/
        vfat = n * fatorial(n - 1);
        return vfat;
    }
}
int main(){
    int numero, fat;
    printf("Digite o numero que deseja calcular o fatorial: ");
    scanf("%d",&numero);
    /*chamada da função fatorial*/
    if(numero < 0){
        printf("Erro: Numero negativo!");
    }else{
        fat = fatorial(numero);
        printf("Fatorial de %d = %d",numero,fat);
    }
    return 0;
}

Perceba que na solução acima dividimos o nosso problema em instâncias menores do problema. Nos temos o caso base que é quando o número n for igual a 0, para esse caso retornamos o valor 1 e a função encerrada sem necessidade de chamadas recursivas. Caso o número seja maior que 0 temos as chamadas recursivas até cair no caso base que é resolvido e assim, as chamadas retornam valores de forma a solucionar o cálculo.

Vejamos o raciocionio:

• 1- Identifico o caso base: o fatorial de 0 igual a 1, então para este caso retornamos 1.
• 2- Para encontrar a maneira correta de se retornar o resultado de uma ou mais chamadas recursivas vamos pensar: o fatorial de um número n consiste em por exemplo: fatorial de 1 = 1 * 1, 2 = 1 * 2, de 3 = 1 * 2 * 3, de 4 = 1 * 2 * 3 * 4..., então alteraremos o n a cada chamada para que este chegue até o valor base. Então fazemos: return n * fatorial (n - 1).
• 3- Também é necessário impedir que n seja < 0, portanto foi adicionado um if para não aceitar essa condição.

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

Outro exemplo

Vamos escrever um programa que tenha uma função recursiva para calcular o valor de uma base elevada a um expoente.

/*Cálculo o valor de uma base elevada a um expoente.*/
#include < stdio.h >
/*Função recursiva*/
int pot(int base, int expoente){
    /*caso base*/
    if(expoente == 0)
        return 1;
    /*Chamada recursiva*/
    return base * pot(base,expoente-1);
}

int main(){
    int base, expoente;
    printf("Digite a base: ");
    scanf("%d", &base);
    printf("Digite o expoente: ");
    scanf("%d", &expoente);
    if(base < 1 || expoente < 0){
       printf("Erro!");
    }else{
    /*Chamada da função recursiva juntamente com o resultado*/
        printf("\nResultado: %d", pot(base, expoente));
    }
    return 0;
}

Podemos observar mais uma vez um problema que pode ser subdivido em subproblemas menores. Temos o caso base que é quando o expoente for igual a 0 e também as chamadas recursivas que fazem com que o expoente vá diminuindo a medida em que são feitas as chamas de função, até chegar ao caso base.

A lógica é bem simples, porém requer atenção:

• 1- Identifico o caso base: todo número elevado a 0 é igual a 1, então para este caso retornamos 1.
• 2- Para encontrar a maneira correta de se retornar o resultado de uma ou mais chamadas recursivas vamos pensar: se a potência de um número n elevado x é igual a n * n *n.… x vezes, então não precisaremos modificar a base. Ora então alteraremos o expoente a cada chamada, para que este chegue até o valor do expoente base. Então fazemos: return base*(base, expoente-1).

Na figura abaixo temos a representação das chamadas de função para 4 elevado a 3.