Recursividade

Funções recursivas de cauda

Implementação de um programa que resolve se um número é primo ou não, usando funções recursivas de cauda.

Fonte: Shutterstock.

Deseja ouvir este material?

Áudio disponível no material digital.

sem medo de errar

Após conhecer a técnica de recursividade, chegou o momento de implementar o programa para os matemáticos do laboratório onde trabalha. Lembre-se: foi solicitado a você implementar um programa que resolve se um número é primo ou não, porém, usando funções recursivas de cauda.

Para implementar essa solução, você precisa de um programa que solicite ao usuário um número.

Você pode seguir os seguintes passos para a implementação:

1. Crie a função ehPrimo() de modo que ela receba um parâmetro, o valor a ser verificado e retorne um número inteiro:
   int ehPrimo(int n)
   
2. Crie uma função auxiliar ehPrimoAux(), que recebe, além do valor a ser verificado, um inteiro x, inicialmente 2, que será utilizado para calcular os divisores de 2 até n.
3. Caso o número n seja divisível por x, então, a função deve retornar o valor 0, informando que o número não é um primo. Caso isso não aconteça até que x seja igual a n, então retorna-se 1.

Veja, no Código 3.22, uma possível implementação para essa solução.

#include<stdio.h>

int ehPrimo(int n) {
    return ehPrimoAux(n, 2);
}

int ehPrimoAux(int n, int x) {
    if (x == n) {
        return 1;
    } else if (n % x == 0) {
        return 0;
    } else {
        return ehPrimoAux(n, x + 1); 
    }
}

Agora, você pode testar o código da solução completa utilizando a ferramenta Paiza.io.

Avançando na prática

Máximo divisor comum

Você foi contratado como professor de programação e, em conversa com o professor de matemática instrumental, ficou sabendo que os alunos têm dúvidas quanto ao mecanismo para calcular o Máximo Divisor Comum (MDC). Seu novo colega sugeriu que você implementasse essa solução com os alunos, para que eles possam, de fato, compreender o algoritmo. Como os alunos já têm conhecimento em programação, como você implementaria a solução?

Resolução

Para implementar essa solução, você deve optar por funções recursivas a fim de desenvolver ainda mais o raciocínio lógico. Para isso, você terá que recorrer ao método numérico de divisões sucessivas (PIRES, 2015). Para entender o mecanismo, considere como exemplo encontrar o MDC entre 16 e 24.

1. É preciso dividir o primeiro número pelo segundo e guardar o resto: $\frac{16}{24}=1$, com resto 16.
   
2. O divisor da operação anterior deve ser dividido pelo resto da divisão. $\frac{24}{16}=1$, com resto 8.
   
3. O segundo passo deve ser repetido, até que o resto seja nulo e, então, o divisor será o MDC. $\frac{16}{8}=2$, com resto 0.
   

Veja, no Código 3.23, uma possível implementação para o MDC.

#include<stdio.h>
int calcularMDC(int a, int b) {
    int r = a % b;
    if (r == 0) {
        return b;
    } else {
        return calcularMDC(b,r);
    }
}
int main(){
    int n1, n2, resultado;
    printf("\nDigite dois números inteiros positivos: ");
    scanf("%d %d", &n1, &n2);
    resultado = calcularMDC(n1,n2);
    printf("\nMDC = %d",resultado);
    return 0;
}

Agora, você pode testar o código utilizando a ferramenta Paiza.io.