O QUE É FUNÇÃO RECURSIVA?
É uma técnica de programação onde uma função chama a si própria.
Fonte: Shutterstock.
Deseja ouvir este material?
Áudio disponível no material digital.
Praticar para Aprender
Após trabalhar com a equipe de nutricionistas e estatísticos, agora é hora de enfrentar um novo desafio com a equipe de matemáticos do laboratório em que atua. Foi solicitado a você implementar um programa que calcula se um número é primo ou não, ou seja, se esse número é divisível apenas por 1 e por ele mesmo. Dessa forma, você deverá entregar o arquivo compilado para que eles possam utilizar. Após conhecer sua nova tarefa, seu gerente, que também é programador, pediu para que utilizasse a técnica de recursividade de cauda na implementação, portanto o usuário precisa informar o número que deseja verificar se é primo ou não. Pense um pouco e responda: o que determinará o término do cálculo; em outras palavras, qual será o caso base dessa recursão?
Aproveite mais essa oportunidade de aprimoramento e bons estudos!
Roteiro para o professor
Atualmente, o estudo de números primos é importantíssimo para a área de segurança computacional, pois eles são o núcleo de vários sistemas criptográficos. Sugira aos alunos que façam uma pesquisa sobre o conceito de criptografia RSA e respondam às seguintes questões:
- Qual a importância dos números primos para segurança computacional?
- Por que uma função que testa a primalidade de um número, como a função proposta na situação-problema, é importante para a criptografia RSA?
- Em que se baseia a “força” da criptografia RSA?
Para essa discussão, você pode usar as seguintes referências sobre o assunto que constam na apostila de Torres ([s. d.]), disponível em: https://bit.ly/3iWRpMz.
conceito-chave
Caro aluno, bem-vindo à última seção no estudo de funções e recursividade. A caminhada foi longa e muito produtiva. Você teve a oportunidade de conhecer diversas técnicas de programação e agora continuaremos avançando no estudo das funções. Você se lembra do algoritmo que calcula o fatorial de um número, o qual vimos na seção sobre estruturas de repetição? Para implementar computacionalmente uma solução desse tipo, você já conhece as estruturas de repetição, como o for, entretanto essa técnica não é a única opção, já que você também pode utilizar a recursividade, assunto central desta seção.
Nesta unidade, apresentamos as funções. Vimos como criar uma função, qual sua importância dentro de uma implementação e estudamos a saída de dados de uma função, bem como a entrada, feita por meio dos parâmetros.
Função recursiva
Entre as funções existe uma categoria especial chamada de funções recursivas. Para começarmos a nos apropriar dessa nova técnica de programação, primeiro vamos entender o significado da palavra recursão. Ao consultar diversos dicionários, como o Houaiss ou o Aulete, temos como resultado que a palavra recursão (ou recursividade) está associada à ideia de recorrência de uma determinada situação. Quando trazemos esse conceito para o universo da programação, deparamo-nos com as funções recursivas.
Nessa técnica, uma função é dita recursiva quando ela chama a si própria ou, nas palavras de Soffner: “Recursividade é a possibilidade de uma função chamar a si mesma” (SOFFNER, 2013, p. 107).
A sintaxe para implementação de uma função recursiva nada difere das funções gerais, ou seja, deverá ter um tipo de retorno, o nome da função, os parênteses e os parâmetros quando necessário. A diferença estará no corpo da função, pois a função será invocada dentro dela mesma.
Observe a Figura 3.6. Nela ilustramos a construção da função, bem como a chamada dela, primeiro na função principal e depois dentro dela mesma.
Assimile
Em termos de sintaxe, uma função recursiva difere de outras funções simplesmente pelo fato de apresentar, em seu conjunto de comandos, uma chamada a si própria.
Embora a sintaxe da função recursiva seja similar à das não recursivas, o funcionamento de ambas é bastante distinto e o mau uso dessa técnica pode acarretar uso indevido de memória, muitas vezes chegando a travar a aplicação e o sistema (MANZANO, 2015). Para entender o processo, vamos estabelecer alguns pontos de atenção:
- A função recursiva chama a si própria até que um ponto de parada seja estabelecido. O ponto de parada poderá ser alcançado por meio de uma estrutura condicional ou por meio de um valor informado pelo usuário.
- Uma função apresenta em seu corpo variáveis e comandos, os quais são alocados na memória de trabalho. No uso de uma função recursiva, os recursos (variáveis e comandos) são alocados (instanciados) em outro local da memória, ou seja, para cada chamada da função, novos espaços são destinados à execução do programa. E é justamente por esse motivo que o ponto de parada é crucial.
- As variáveis criadas em cada instância da função na memória são independentes, ou seja, mesmo as variáveis tendo nomes iguais, cada uma tem seu próprio endereço de memória e a alteração do valor em uma não afetará a outra.
Para auxiliá-lo na compreensão desse mecanismo observe a Figura 3.7. A instância 1 representa a primeira chamada à função funcaoRecursiva(), esta, por sua vez, tem em seu corpo um comando que invoca a si mesma; nesse momento é criada a segunda instância dessa função na memória de trabalho. Veja que um novo espaço é alocado, com variáveis e comandos, e, como a função é recursiva, novamente ela chama a si mesma, criando, então, a terceira instância da função. Dentro da terceira instância, uma determinada condição de parada é satisfeita, nesse caso, a função deixa de ser instanciada e passa a retornar valores.
- A partir do momento que a função recursiva alcança o ponto de parada, cada instância da função passa a retornar seus resultados para a instância anterior (a que fez a chamada). No caso da Figura 3.7, a instância três retornará para a dois, e a dois retornará para a um. Veja que, se o ponto de parada não fosse especificado na última chamada, a função seria instanciada até haver um estouro de memória.
Toda função recursiva deve ter uma instância com um caso que interromperá a chamada a novas instâncias. Essa instância é chamada de caso base, pois representa o caso mais simples, que resultará na interrupção.
Reflita
Toda função recursiva tem que dispor de um critério de parada. A instância da função que atenderá a esse critério é chamada de caso base. Um programador que implementa de maneira equivocada o critério de parada, acarretará um erro somente na sua aplicação, ou tal erro poderá afetar outras partes do sistema?
Vamos implementar uma função recursiva que faz a somatória dos antecessores de um número inteiro positivo, informado pelo usuário, ou seja, se o usuário digitar 5, o programa deverá retornar o resultado da soma 5 + 4 + 3 + 2 + 1 + 0. Com base nesse exemplo, você consegue determinar quando a função deverá parar de executar? Veja, a função deverá somar até o valor zero, portanto esse será o critério de parada. Veja a implementação da função no Código 3.19 e a seguir sua explicação.
#include<stdio.h>
int somar(int valor) {
if(valor == 0) {
//critério de parada
return valor;
} else {
//chamada recursiva
return valor + somar(valor - 1);
}
}
int main() {
int n, resultado;
printf("\nDigite um número inteiro positivo : ");
scanf("%d", &n);
resultado = somar(n); // primeira chamada da função
printf("\nResultado = %d",resultado);
return 0;
}
Teste o Código 3.19 utilizando a ferramenta Paiza.io.
A execução do programa no Código 3.19 começará na linha 11, pela função principal (main). Na linha 15, a função somar() é invocada, passando como parâmetro um número inteiro digitado pelo usuário. Nesse momento, a execução “salta” para a linha 2, onde a função é criada. Observe que ela foi criada para retornar e receber um valor inteiro. Na linha 3, o condicional foi usado como critério de parada; veja que, se o valor for diferente (!=) de zero, a execução passa para a linha 8, na qual a função é invocada novamente, mas dessa vez passando como parâmetro o valor menos 1. Quando o valor for zero, retorna-se o próprio valor, isto é, 0.
Exemplificando
A Figura 3.8 exemplifica o funcionamento na memória do computador da função somar(). Nessa ilustração, o usuário digitou o valor 2, então a função main() invocará a função somar(2), criando a primeira instância e passando esse valor. O valor 2 é diferente de zero na primeira instância, então, o critério de parada não é satisfeito e a função chama a si própria, criando a segunda instância, mas, agora, passando o valor 1 como parâmetro somar(1). Veja que, na primeira instância, o valor a ser retornado é 2 + ?, pois ainda não se conhece o resultado da função. Na segunda instância o valor também é diferente de zero, portanto a função chama a si mesma novamente, agora passando como parâmetro zero (valor – 1). Veja que o retorno fica como 1 + ?, pois também não se conhece, ainda, o resultado da função. Na terceira instância, o critério de parada é satisfeito, nesse caso a função retorna zero. Esse valor será usado pela instância anterior que, após somar 1 + 0, retornará seu resultado para a instância 1, que somará 2 + 1 e retornará o valor para a função principal, fechando o ciclo de recursividade.
Uma das grandes dúvidas dos programadores é quando utilizar a recursividade em vez de uma estrutura de repetição. A função somar(), criada no Código 3.19, poderia ser substituída por uma estrutura de repetição usando for?
No exemplo dado, poderia ser escrito algo como:
for(int i = 0; i <= 2; i++) {
resultado = resultado + i;
}
A verdade é que poderia, sim, ser substituída. A técnica de recursividade pode substituir o uso de estruturas de repetição, tornando o código mais elegante do ponto de vista das boas práticas de programação. Entretanto, como você viu, funções recursivas podem consumir mais memória que as estruturas iterativas. Para ajudar a elucidar quando optar por essa técnica, veja o que diz um professor da Universidade de São Paulo (USP):
Muitos problemas têm a seguinte propriedade: cada instância do problema contém uma instância menor do mesmo problema. Dizemos que esses problemas têm estrutura recursiva. Para resolver um tal problema, podemos aplicar o seguinte método:
• se a instância em questão for pequena,
resolva-a diretamente (use força bruta se necessário);
• senão
reduza-a a uma instância menor do mesmo problema,
aplique o método à instância menor,
volte à instância original.
[...] A aplicação desse método produz um algoritmo recursivo. (FEOFILOFF, 2017, p. 1, grifo do original)
Portanto, a recursividade usada para indicar quando um problema maior pode ser dividido em instâncias menores do mesmo problema, porém considerando a utilização dos recursos computacionais que cada método empregará.
Não poderíamos falar de funções recursivas sem apresentar o exemplo do cálculo do fatorial, um clássico no estudo dessa técnica. O fatorial de um número qualquer N consiste em multiplicações sucessivas até que N seja igual ao valor unitário, ou seja, , que resulta em 120. Observe o Código 3.20, que implementa essa solução usando uma função recursiva. Em seguida, observe a explicação.
#include<stdio.h>
int fatorial(int valor) {
if(valor != 1) {
//chamada recursiva
return valor * fatorial(valor - 1);
} else {
//critério de parada
return valor;
}
}
int main() {
int n, resultado;
printf("\nDigite um número inteiro positivo: ");
scanf("%d", &n);
resultado = fatorial(n);
printf("\nResultado = %d", resultado);
return 0;
}Teste o Código 3.20 utilizando a ferramenta Paiza.io.
A execução do Código 3.20, inicia pela função principal, a qual solicita um número ao usuário e, na linha 15, invoca a função fatorial(), passando o valor digitado como parâmetro. Dentro da função fatorial(), enquanto o valor for diferente de 1, a função chamará a si própria, criando instâncias na memória, passando a cada vez como parâmetro o valor decrementado de 1. Quando o valor chegar a 1, a função retorna o próprio valor, permitindo assim o retorno da multiplicação dos valores encontrados em cada instância. É importante entender bem o funcionamento. Observe a Figura 3.9, que ilustra as instâncias quando o usuário digita o número 3. Veja que os resultados só são obtidos quando a função chega no caso base e, então, começa a “devolver” o resultado para a instância anterior.
Roteiro para o professor
Uma boa estratégia para se chegar a um algoritmo recursivo é dividir uma grande instância de um problema em instâncias menores, para então resolvê-las.
Proponha aos alunos que façam um programa recursivo para retornar se determinado número inteiro existe ou não em um vetor de números inteiros.
Desenhe um vetor na lousa, com vários números, como segue:
| 3 | 4 | 1 | 2 | 3 | 5 |
Saber se o número 2 existe nesse vetor de 6 elementos é uma instância grande do problema. Que tal reduzirmos esse vetor de 6 para apenas um 1 elemento? Assim, fica fácil sabermos se o número existe ou não.
| 3 | 4 | 1 | 2 | 3 | 5 |
Por exemplo, olhando apenas para o elemento 3, podemos afirmar que o 2 não está no vetor. Contudo, sabemos que o vetor apresenta outros elementos. Podemos, então, levar essa lógica para os outros elementos, até que todos os elementos tenham sido verificados ou até que o valor desejado tenha sido encontrado.
Reúna os alunos em grupos para que discutam a solução desse problema. Perguntas que podem ser usadas para guiar a discussão:
- Qual a condição de parada da recursão?
- Se a condição não for satisfeita, como a função deve ser invocada recursivamente?
- Faz diferença começarmos do início, do fim ou de qualquer posição aleatória do vetor?
Eis uma possível solução para o problema em questão:
#include<stdio.h>
#define VET_TAM 6
int buscaRecursiva(int vet[], int tam, int n) {
if (tam < 0) {
return 0;
} else if (vet[tam] == n) {
return 1;
} else {
return buscaRecursiva(vet, tam - 1, n);
}
}
int main() {
int resultado = 0, n;
int vet[VET_TAM] = {3, 4, 1, 2, 3, 5};
printf("\nDigite o número a ser procurado: ");
scanf("%d", &n);
resultado = buscaRecursiva(vet, VET_TAM, n);
if (resultado == 1) {
printf("\nO número %d foi encontrado!", n);
} else {
printf("\nO número %d não foi encontrado!", n);
}
return 0;
}Recursividade em cauda
Esse mecanismo é custoso para o computador, pois tem que alocar recursos para as variáveis e comandos da função, procedimento chamado de empilhamento, além de ter que armazenar o local onde foi feita a chamada da função (OLIVEIRA, 2018). Para usar a memória de forma mais otimizada, existe uma alternativa chamada recursividade em cauda. Nesse tipo de técnica, a recursividade funcionará como uma função iterativa (OLIVEIRA, 2018).
Uma função é caracterizada como recursiva em cauda quando a chamada a si mesma é a última operação a ser feita no corpo da função. Nesse tipo de função, o caso base costuma ser passado como parâmetro, o que resultará em um comportamento diferente.
Para entender, vamos implementar o cálculo do fatorial usando essa técnica. Veja o Código 3.21. Observe, na linha 8, que a função recursiva em cauda retorna o fatorial, sem nenhuma outra operação matemática, e que passa o número a ser calculado e o critério de parada junto. Foi necessário criar uma função auxiliar para que o usuário possa calcular o fatorial passando apenas um número inteiro.
#include<stdio.h>
int fatorialCauda(int n) {
return fatorialAux(n, 1);
}
int fatorialAux(int n, int parcial) {
if (n != 1) {
return fatorialAux(n - 1, parcial * n);
} else {
return parcial;
}
}
int main() {
int n, resultado;
printf("\nDigite um número inteiro positivo: ");
scanf("%d", &n);
resultado = fatorialCauda(n);
printf("\nResultado do fatorial = %d", resultado);
return 0;
}Teste o Código 3.21 utilizando a ferramenta Paiza.io.
Observe, na Figura 3.21, que o mecanismo de funcionamento da recursividade em cauda é diferente. A função main() invoca a função fatorialCauda(), passando como parâmetro o valor a ser calculado. Esta, por sua vez, invoca a função fatorialAux, passando o valor a ser calculado e o critério de parada. A partir desse ponto, inicia a maior diferença entre as técnicas. Veja que as instâncias vão sendo criadas, porém, quando chega na última (nesse caso a instância 3), o resultado já é obtido e as funções não precisam retornar o valor para “quem” invocou, pois o comando que invoca a função era o último comando da função. Isso gera uma otimização na memória, pois não precisa armazenar nenhum ponto para devolução de valores.
Roteiro para o professor
Quando um compilador moderno encontra uma função recursiva na cauda, ele automaticamente a transforma em um laço durante as otimizações. Isso é feito para tentar evitar um estouro na pilha de chamadas de funções na memória do computador.
Da mesma forma, é importante para o aluno entender como uma função recursiva pode ser escrita de forma iterativa e vice-versa. Assim, ele otimiza seu programa, mesmo quando isso não pode ser feito automaticamente pelo compilador.
A função a seguir calcula recursivamente o n-ésimo termo da sequência de Fibonacci. Trata-se de uma sequência de números inteiros, começando de 1 e 1, em que cada termo posterior corresponde à soma dos dois anteriores. Exemplo: 1, 1, 2, 3, 5, 8, 13...
int fib(int n) {
if (n < 2) {
return n;
} else {
return fib(n - 1) + fib(n - 2);
}
}Proponha aos alunos uma discussão em grupo, para que respondam às seguintes questões:
- Quantas chamadas recursivas seriam feitas para se calcular o Fibonacci de 6?
- Como seria uma possível versão iterativa desta função?
Chegamos, então, a mais um final de seção. Não se esqueça de que quanto mais você exercitar, mais algoritmos implementar, mais desafios solucionar, mais sua lógica se desenvolverá e você terá maior facilidade para desenvolver novos programas. Agora você já tem conhecimento para solucionar seu próximo desafio. Boa sorte!
Faça valer a pena
Questão 1
A recursividade é uma técnica de programação usada para tornar o código mais elegante e organizado, o que pode facilitar a manutenção. Essa técnica, em muitos casos, pode ser usada para substituir uma estrutura de repetição iterativa, como aquelas que usam o for.
Com base no contexto apresentado, avalie as seguintes asserções e a relação proposta entre elas.
- As estruturas de repetição sempre podem ser substituídas por funções recursivas.
PORQUE
- Uma função recursiva funciona como um laço de repetição, o qual será interrompido somente quando o caso base for satisfeito.
A respeito dessas asserções e da relação entre elas, assinale a alternativa correta.
Tente novamente...
Esta alternativa está incorreta, leia novamente a questão e reflita sobre o conteúdo para tentar novamente.
Tente novamente...
Esta alternativa está incorreta, leia novamente a questão e reflita sobre o conteúdo para tentar novamente.
Tente novamente...
Esta alternativa está incorreta, leia novamente a questão e reflita sobre o conteúdo para tentar novamente.
Correto!
O erro na primeira asserção está na palavra “sempre”, pois uma função recursiva pode, sim, substituir uma estrutura de repetição, porém nem sempre é viável, por conta dos recursos computacionais necessários na execução.
Tente novamente...
Esta alternativa está incorreta, leia novamente a questão e reflita sobre o conteúdo para tentar novamente.
Questão 2
Para criar uma função recursiva, a sintaxe nada difere das funções gerais, portanto é necessário informar o tipo de retorno, o nome e se recebe ou não parâmetros. O grande diferencial das funções recursivas e tradicionais é um comando no corpo da função, que invoca a si própria. Analise o código a seguir e escolha a opção que representa o que será impresso na linha 10.
#include<stdio.h>
int somar(int valor) {
if (valor != 0){
return valor + somar(valor - 1);
} else {
return valor;
}
}
int main() {
printf("\nResultado = %d", somar(6));
return 0;
}Com base no contexto apresentado, assinale a alternativa correta.
Correto!
Para a compreensão da resposta, analise o esquema a seguir. Veja que cada chamada da função fica aguardando um valor até que o caso base seja encontrado.
Tente novamente...
Esta alternativa está incorreta, leia novamente a questão e reflita sobre o conteúdo para tentar novamente.
Tente novamente...
Esta alternativa está incorreta, leia novamente a questão e reflita sobre o conteúdo para tentar novamente.
Tente novamente...
Esta alternativa está incorreta, leia novamente a questão e reflita sobre o conteúdo para tentar novamente.
Tente novamente...
Esta alternativa está incorreta, leia novamente a questão e reflita sobre o conteúdo para tentar novamente.
Questão 3
A recursividade é uma técnica de programação que deve ser usada com cautela, pois a cada chamada à função, novos recursos são alocados na memória, em um processo chamado de empilhamento, que cresce rapidamente com as chamadas, podendo acarretar um estouro de memória.
A respeito de funções recursivas, analise as afirmativas a seguir.
- Existe uma classe específica de funções recursivas chamada de recursividade em cauda que, embora tenha a mesma sintaxe no corpo da função, apresenta comportamento diferente das demais funções.
- Uma função é caracterizada como recursiva em cauda quando a chamada a si mesma é a última operação a ser feita no corpo da função.
- Em uma função que implementa a recursividade em cauda, a instância que fez a chamada recursiva depende do resultado da próxima.
- O uso da recursividade em cauda torna opcional o uso do caso base, pois a última instância retornará o valor final esperado.
A respeito das afirmativas apresentadas, é correto o que se afirma apenas em:
Tente novamente...
Esta alternativa está incorreta, leia novamente a questão e reflita sobre o conteúdo para tentar novamente.
Tente novamente...
Esta alternativa está incorreta, leia novamente a questão e reflita sobre o conteúdo para tentar novamente.
Tente novamente...
Esta alternativa está incorreta, leia novamente a questão e reflita sobre o conteúdo para tentar novamente.
Correto!
A afirmativa I é falsa, pois a sintaxe, na criação e no corpo da função, será diferente. Tanto o local onde é feita a chamada da recursividade como o retorno são diferentes.
A afirmativa II é verdadeira, pois o fato de se ter a chamada recursiva como última instrução da função é que caracteriza a recursividade de cauda.
A afirmativa III é falsa, pois a instância que fez a chamada recursiva não depende do resultado da próxima instância.
A afirmativa IV é falsa, pois o caso base é sempre necessário, senão a recursividade entra em um loop infinito de chamadas.
Tente novamente...
Esta alternativa está incorreta, leia novamente a questão e reflita sobre o conteúdo para tentar novamente.
Referências
ALMEIDA, R.; ZANLORENSSI, G. A evolução do número de linhas de telefone fixo e celular no mundo. Nexo Jornal, 2 maio 2018. Disponível em: https://cutt.ly/7jS47V9. Acesso em: 7 jul. 2018.
COUNTER, L. Lines of code of the Linux Kernel Versions. Disponível em: https://cutt.ly/zjSOt0G. Acesso em: 30 jun. 2018.
FEOFILOFF, P. Recursão e algoritmos recursivos. Instituto de Matemática e Estatística da Universidade de São Paulo, 21 maio 2018. Disponível em: https://cutt.ly/OjSOwOH. Acesso em: 2 jan. 2018.
MANZANO, J. A. N. G. Linguagem C: acompanhada de uma xícara de café. São Paulo: Érica, 2015.
MANZANO, J. A. N. G.; MATOS, E.; LOURENÇO, A. E. Algoritmos: técnicas de programação. São Paulo: Érica, 2015.
OLIVEIRA, R. Algoritmos e programação de computadores. Notas de aula. Instituto de Computação da Universidade Estadual de Campinas – UNICAMP, [s. d.]. Disponível em: https://cutt.ly/mjSI75P. Acesso em: 16 jul. 2018.
PIRES, A. A. Cálculo numérico: prática com algoritmos e planilhas. São Paulo: Atlas, 2015.
SOFFNER, R. Algoritmos e programação em linguagem C. São Paulo: Saraiva, 2013.
TORRES, F. Criptografia: o método RSA. Apostila MA553 A – Teoria Aritmética dos Números. IMECC, Unicamp, [s. d.]. Disponível em: https://cutt.ly/JjS7rKs. Acesso em: 10 jan. 2021.