Tutorial de Programação em C no Linux Parte 18: Funções Recursivas

Independentemente da linguagem de programação que você usa, à medida que começa a codificar cada vez mais, você aprende conceitos que tornam seu código mais claro e fácil de ler/compreender. Existem vários desses conceitos em C também. Um deles é ‘funções recursivas’, que discutiremos aqui neste artigo.

Uma função recursiva é uma função que chama a si mesma. A chamada pode ser feita diretamente dentro do corpo da função ou indiretamente a partir de alguma outra função que é chamada pela função em questão.

Segue um exemplo de recursão direta:

int func (int a)  
{  
    //declarações  
  
    func(a-1);  
  
    // declarações  
  
    return 0;  
}

E aqui está um exemplo de recursão indireta:

int func (int a)  
{  
    //declarações  
  
    func_new(a);  
  
    // declarações  
  
    return 0;  
}  
  
int func_new(int b)  
{  
    //declarações  
  
    func(b-1);  
  
    //declaraçõesur  
  
    return 0;  
}

Como já mencionado no início, a recursão ajuda você a alcançar um código compacto, que não é apenas fácil de escrever, mas também fácil de entender e revisar. Vamos pegar um exemplo para deixar essa vantagem mais clara.

Tenho certeza de que todos vocês já ouviram falar sobre o conceito de fatorial. Para aqueles que não estão cientes, o fatorial é o resultado que você obtém ao multiplicar um inteiro por todos os inteiros positivos menores que ele. Por exemplo, o fatorial de 5 é 5x4x3x2x1, que é igual a 120.

Aqui está um código simples para encontrar o fatorial de um número:

#include   
  
int main()  
{  
 int a = 0, i = 0, fact = 1;  
 printf("Digite um número: ");  
  
 scanf("%d", &a);  
   
 for(i=1; i<=a; i++)  
 {  
 fact = fact * i;  
   
 }  
 printf("O fatorial do número é: %d ", fact);  
 return 0;  
}

Note que este código é apenas para que você saiba como o fatorial de um número pode ser calculado através de um programa em C. O programa não cuida de casos extremos que podem afetar a precisão do resultado que produz.

Então, esta é uma das muitas maneiras de calcular o fatorial de um número sem usar uma função recursiva. Agora vamos ver um trecho de código que usa recursão para calcular um fatorial.

#include   
  
int factorial (int b)  
{  
 if(!b)  
 return 1;  
   
 return (b * factorial(b-1));  
}  
  
int main()  
{  
 int a = 0, fact = 1;  
 printf("Digite um número: ");  
  
 scanf("%d", &a);  
   
 fact = factorial(a);  
   
 printf("O fatorial do número é: %d ", fact);  
 return 0;  
}

Então você pode ver, a função ‘factorial’ que realmente calcula o fatorial é muito compacta. E se você prestar atenção, também é muito fácil de entender.

Para aqueles que não sabem o que está acontecendo, o valor que o usuário inseriu, digamos 5, é passado para a função ‘factorial’ quando é chamada pela primeira vez a partir da função ‘main’. Dentro da função ‘factorial’, há uma verificação para ver se o valor de entrada é zero, o que não é verdade quando a função é chamada pela primeira vez com o valor de entrada ‘5’.

Então, a instrução de retorno contém uma expressão que multiplica 5 pelo valor de retorno de ‘factorial(4)’. Então agora, a função ‘factorial’ é executada mais uma vez, e chegamos à seguinte expressão: return (4 * factorial(3)). E então novamente esses passos se repetem.

Então, se você olhar amplamente, aqui está como essas chamadas de função são empilhadas:

• 5 * factorial(4)
• 4 * factorial(3)
• 3 * factorial(2)
• 2 * factorial (1)
• 1 * factorial (0)

Agora, quando factorial(0) é executado, a condição ‘if’ na função ‘factorial’ se torna verdadeira, e o valor ‘1’ é retornado. Então agora, é assim que as chamadas listadas acima se completam (compare a última entrada na lista anterior com a primeira entrada nesta lista, e assim por diante):

• 1 * 1
• 2 (11)
• 3 (2(1*1))
• 4 (3(2(11)))
• 5 (4 (3(2(1*1))))

Que é efetivamente 5 4 3 2 1, que por sua vez é 120, o fatorial de 5.

Então é assim que as funções recursivas funcionam. Embora não haja dúvida sobre as vantagens da função recursiva que listamos até agora, também existem algumas desvantagens.

Por exemplo, em nosso exemplo acima, até que a chamada ‘factorial(0)’ fosse concluída, todas as chamadas anteriores de ‘factorial’ estavam esperando que o processamento da função fosse concluído. Sem mencionar o fato de que variáveis automáticas ou locais ocupam memória para cada chamada recursiva feita.

Portanto, não há efetivamente economia de espaço de armazenamento ao usar recursão. Além disso, também não há garantia de que seu código será mais rápido na execução. A verdadeira vantagem de uma função recursiva é quando você lida com estruturas de dados, que discutiremos mais adiante como parte desta série de tutoriais em C.

Conclusão

Para concluir, embora você possa não usar funções recursivas com frequência em suas tarefas de codificação do dia a dia, é um conceito importante do qual você deve estar ciente. Experimente o exemplo que mencionamos aqui e ajuste-o para entender o conceito de funções recursivas ainda melhor.