Recursividade em C

Prévia do material em texto

ALGORITMOS E 
PROGRAMAÇÃO 
Marcos Paulo Lobo de Candia 
Recursividade em C
Objetivos de aprendizagem
Ao final deste texto, você deve apresentar os seguintes aprendizados:
 � Reconhecer a recursividade e os problemas que podem ser resolvidos 
por meio de soluções recursivas.
 � Definir a construção de funções recursivas e as condições de parada.
 � Desenvolver funções recursivas.
Introdução
De modo genérico, o termo “recursividade” é utilizado para descrever o 
processo de repetição de um objeto ou evento de um modo semelhante 
ao que já tenha ocorrido. Em computação, recursão é um método de 
programação utilizado para solucionar uma classe específica de proble-
mas, dividindo-os em problemas menores de mesma natureza.
Neste capítulo, você aprenderá o conceito de recursividade e como ele 
é empregado na ciência da computação, mais especificamente na progra-
mação. Você também compreenderá melhor quais tipos de problemas 
podem ser resolvidos por meio desta técnica e entenderá a estrutura, a 
sintaxe e o funcionamento das funções recursivas. Por fim, aprenderá a 
implementar computacionalmente esse tipo de função em linguagem C. 
O que é recursividade?
As funções em linguagem C melhoram a organização do código, permitem 
a reutilização de trechos de código e evitam a repetição de comandos. Existe 
uma categoria especial de funções, denominada funções recursivas. Mas 
antes de detalhar essa técnica de programação, você aprenderá o significado 
da palavra recursão. Recursão ou recursividade é um termo usado de maneira 
genérica para descrever o processo de repetição de um objeto de modo similar 
ao que já fora mostrado. 
Diversas situações do seu dia a dia podem ser definidas recursivamente, 
como por exemplo, quando você lê um livro. Um livro normalmente é dividido 
em capítulos. A leitura de um livro consiste em ler o primeiro capítulo e, 
depois, repetir o processo para ler o restante do livro. Um outro exemplo é a 
fila de pessoas no caixa de uma loja. É atendida em primeiro lugar a pessoa 
que está no início da fila. Uma vez terminado o atendimento, essa pessoa sai 
da fila, e a que estava em segundo lugar passa a encabeçar a fila das restantes. 
O processo é repetido para a fila restante até que a última pessoa seja atendida 
pelo caixa. Observe, nestes dois exemplos, que existem condições que fazem 
com que os processos recursivos parem em algum momento. E isso também 
ocorre quando a recursividade é aplicada à programação.
Na ciência da computação, o conceito de recursividade está relacionado 
com o universo da programação, de onde surge uma nova técnica: as funções 
recursivas. Essa técnica é utilizada para solucionar um grupo específico de 
problemas, também com estrutura recursiva. 
Um problema é dito recursivo se é definível em termos de si mesmo. Um 
exemplo disso é a definição de números naturais (EDELWEISS; LIVI, 2014):
 � o primeiro número natural é zero;
 � o sucessor de um número natural é um número natural.
Nesta classe de problemas, um problema é dividido em subproblemas de 
mesma natureza, onde cada instância contém uma instância menor do mesmo 
problema. Na definição de números naturais, cada antecessor de um número 
natural, por exemplo o 5, é também um número natural (4, 3, 2, 1), até chegar 
ao zero (que é o primeiro número natural). 
Para resolver uma instância de um problema recursivo, você pode aplicar 
o seguinte método (FEOFILOFF, 2018):
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.
Recursividade em C2
Logo, a solução de um problema recursivo consiste em resolver subpro-
blemas mais simples, sucessivamente, até se atingir o caso mais simples de 
todos, cujo resultado é imediato. Muitos problemas podem ser identificados e 
resolvidos assim, desde que possam ser divididos em subproblemas do mesmo 
tipo. Esse paradigma também é conhecido como divisão e conquista, e é 
empregado nos mais variados algoritmos, dentre eles: ordenação de valores, 
busca binária, programação dinâmica, etc.
Agora que você já sabe identificar quais tipos de problemas podem ser 
resolvidos por meio das funções recursivas, vamos entender mais sobre elas.
Uma função é dita recursiva quando ela chama a si mesma durante a 
execução de um programa ou algoritmo (SOFFNER, 2013). A sintaxe para 
implementação de uma função recursiva é semelhante à sintaxe para im-
plementação das funções gerais, ou seja, deverá ter um tipo de retorno, um 
nome, os parênteses e os parâmetros de entrada, quando necessário. A única 
diferença está no corpo da função, pois a função recursiva será invocada 
dentro dela mesma. A Figura 1 mostra a sintaxe de uma função recursiva. 
É possível observar a construção da função, bem como a chamada dela; 
primeiro na função principal (função main) e depois dentro dela mesma.
Figura 1. Sintaxe de uma função recursiva.
<tipo> nomeFuncaoRecursiva(){
// comandos
//comandos
//comandos
nomeFuncaoRecursiva();
}
}
void main(){
nomeFuncaoRecursiva();
Chamando a si mesma
2
1
3Recursividade em C
Portanto, para você criar uma função recursiva, basta fazer uma chamada 
da função dentro dela própria. Embora a sintaxe seja simples, é necessário 
que você entenda seu funcionamento e saiba quando se pode utilizar essa 
técnica, pois, se mal estruturada, a função recursiva poderá entrar em um 
laço de repetição infinito. 
Estrutura das funções recursivas
Apesar de a sintaxe da função recursiva ser similar à sintaxe das funções não 
recursivas, o funcionamento é bastante distinto, e o mau uso dessa técnica 
pode acarretar utilização indevida de memória, chegando muitas vezes a travar 
a aplicação e o sistema (MANZANO, 2015). Para que você entenda todo o 
processo de construção e funcionamento das funções recursivas, é necessário 
estabelecer alguns pontos de atenção, como os listados a seguir.
 � Ponto de parada: por definição a função recursiva chama a si mesma, 
portanto é preciso estabelecer quando parar esse laço de repetição. 
O ponto de parada poderá ser alcançado por meio de uma estrutura 
condicional ou por meio de um valor informado pelo usuário.
 � Instâncias: uma função possui 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 
devido a esse ponto que o critério de parada é crucial. 
 � Variáveis independentes: as variáveis criadas na memória em cada 
instância da função recursiva são independentes, ou seja, mesmo as 
variáveis tendo nomes iguais, cada uma tem seu próprio endereço de 
memória, de modo que a alteração do valor em uma não afetará na outra. 
Recursividade em C4
Para auxiliá-lo na compreensão deste esquema, observe a Figura 2.
Figura 2. Esquema de funcionamento de uma função recursiva.
Instância 1 Instância 2 Instância 3
nomeFuncaoRecursiva(){ nomeFuncaoRecursiva(){ nomeFuncaoRecursiva(){
//comandos
nomeFuncaoRecursiva();
//comandos
return valor;
//comandos
nomeFuncaoRecursiva();
//comandos
return valor;
//comandos
//ponto de parada
return valor;
} }
}
A instância 1 representa a primeira chamada da função nomeFuncaoRe-
cursiva(), que, por sua vez, possui em seu corpo um comando que invoca a si 
mesma. Neste 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. Dentro da terceira instância, uma determinada condição 
de parada é satisfeita. Neste caso a função deixa de ser instanciada e passa 
a retornar valores.
A partir do momento que a função recursiva atinge o ponto de parada, cada 
instância da função passa a retornarseus resultados para a instância anterior (a 
que fez a chamada). No caso da Figura 2, a instância 3 retornará para a 2, e a 
instância 2, para a 1. Note 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 precisa ter, obrigatoriamente, uma instância com um caso que 
interromperá a chamada a novas instâncias. Essa instância é chamada de caso base, 
porque representa o caso mais simples, que resultará na interrupção. 
5Recursividade em C
Desenvolvendo funções recursivas
Agora, você verá a implementação de uma função recursiva que faz a somatória 
dos antecessores de um número inteiro positivo. Neste programa, esse número 
deve ser informado como dado de entrada pelo usuário. 
Supondo que o usuário digite 4, então o programa deverá retornar o resul-
tado da soma 4 + 3 + 2 + 1 + 0, que é 10, como informação de saída.
A partir desse exemplo, você̂ consegue identificar qual é o ponto de parada 
da função recursiva, isto é, quando a função recursiva deverá interromper a 
execução? Pois bem, a função recursiva deverá somar os antecessores de um 
número positivo até́ o valor zero. Então, quando se “alcançar” o valor zero, 
o critério de parada da função será satisfeito. Mas veja bem: ao identificar o 
critério de parada, você também estará determinando o passo básico da solução 
do problema recursivo, cujo resultado é imediatamente conhecido. Na soma, 
há uma propriedade na qual o zero é considerado neutro. Assim, o resultado 
de um número somado com zero é o próprio número. Então este será o retorno 
da função quando a condição de parada for satisfeita. 
As demais somatórias correspondem ao passo recursivo da solução do 
problema, em que se tenta resolver um subproblema do problema inicial. Neste 
exemplo, se o valor for diferente de zero, o passo recursivo é executado; caso 
contrário, o passo básico é realizado. O passo recursivo e o passo básico são 
dados respectivamente por:
A Figura 3 mostra a implementação da solução escrita em linguagem C.
Recursividade em C6
Figura 3. Implementação recursiva para soma.
A execução do programa da Figura 3 inicia na linha 9, ou seja, pela fun-
ção principal. Na linha 13 a função recursiva soma() é invocada, passando 
como parâmetro o número inteiro digitado pelo usuário (n). Neste momento, 
a execução “salta” para a linha 2, onde a função recursiva soma() é criada. 
Observe que ela foi criada para retornar e receber um valor inteiro. 
Na linha 3, a estrutura condicional foi usada como critério de parada. 
Observe que, se o valor for diferente de zero (!=0), a execução do programa 
passará para a linha 4, na qual a função recursiva soma() é invocada nova-
mente, com parâmetro de valor menos 1. Caso contrário — isto é, quando o 
valor for zero —, as instâncias passam a retornar o valor para a que chamou. 
A Figura 4 exemplifica o funcionamento na memória de trabalho da função 
recursiva soma(). Neste exemplo, o usuário digitou o número 2, então a função 
main() invocará a função soma(2), criando a primeira instância e passando 
esse valor. Na primeira instância, a estrutura condicional é testada e retorna o 
valor verdadeiro, ou seja, 2 é diferente de zero. Então, o critério de parada não 
é satisfeito e a função soma() chama a si mesma criando a segunda instância. 
Agora, o valor 1 é passado como parâmetro, isto é, soma(1). 
Note 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 (1) também 
é diferente de zero, portanto a função chama a si mesma novamente, agora 
passando como parâmetro 0 (1 – 1). Observe que o retorno fica como 1 + ?, 
pois também não se conhece ainda o resultado da função. 
7Recursividade em C
Na terceira instância o critério de parada é satisfeito. Neste caso a função 
retorna o valor 0. 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, encerrando o ciclo de recursividade. 
Figura 4. Memória de trabalho da função recursiva soma().
Instância 1 Instância 2 Instância 3
soma(2) soma(1) soma(0)
return 2 + ?; return 1 + ?; return 0;
3 1 0
main
Uma das principais dúvidas dos programadores é quando utilizar a recursi-
vidade em vez de uma estrutura de repetição. Você consegue dizer se a função 
soma(), criada na Figura 3, poderia ser substituída por alguma estrutura de 
repetição, por exemplo a estrutura for? 
A resposta é “sim”. No exemplo dado, você poderia escrever algo parecido 
com o que é mostrado na Figura 5 para resolver este mesmo problema da 
somatória, utilizando a estrutura de repetição for.
Figura 5. Soma utilizando a estrutura de repetição for.
Recursividade em C8
A técnica de recursividade pode substituir o uso de estruturas de repetição, 
tornando o código mais simples e elegante do ponto de vista das boas práticas 
de programação. Consequentemente, o entendimento e a manutenção também 
se tornam mais fáceis. Todavia, funções recursivas podem consumir mais 
memória do que as estruturas iterativas (MANZANO, 2015). 
Você deve usar a recursividade quando um problema maior puder ser 
dividido em instâncias menores do mesmo problema, porém considerando a 
utilização dos recursos computacionais que cada método empregará. 
Um exemplo clássico no estudo da recursividade é o cálculo do fatorial de um número 
inteiro N. Este problema consiste em realizar a multiplicação de N por todos os seus 
antecessores até chegar ao número 1. 
Para exemplificar, suponha que você queira calcular o fatorial de 5, o qual é repre-
sentado por 5!. Neste caso, teríamos:
5! = 5 × 4 × 3 × 2 × 1 = 120
Portanto, o fatorial de 5 é 120.
Observe o código na Figura 6, que implementa uma solução para o cálculo do 
fatorial utilizando uma função recursiva.
Figura 6. Função recursiva para fatorial.
9Recursividade em C
EDELWEISS, N.; LIVI, M. A. C. Algoritmos e programação: com exemplos em Pascal e C. 
Porto Alegre: Bookman, 2014. 
FEOFILOFF, P. Recursão e algoritmos recursivos. 2018. Disponível em: https:// www.ime.
usp.br/~pf/algoritmos/aulas/recu.html. Acesso em: 15 abr. 2019.
MANZANO, J. A. N. G. Linguagem C: acompanhada de uma xícara de café. São Paulo: 
Érica, 2015. 
SOFFNER, R. Algoritmos e programação em linguagem C. São Paulo: Saraiva, 2013. 
Você pode facilmente identificar o critério de parada da função recursiva fatorial() 
ao analisar o código mostrado na Figura 6. Como o problema envolve sucessivas 
multiplicações, é necessário estabelecer até quando elas ocorrerão. Neste caso, até 
alcançar o número 1. Este número é um elemento neutro na multiplicação, ou seja, 
qualquer número multiplicado por 1 é o próprio número. Esse será o retorno da 
função ao atingir o ponto de parada (veja na linha 6). Portanto, o caso base da função 
fatorial() é o teste do valor igual a 1, que retorna o resultado imediato valor, e o passo 
recursivo é valor * fatorial(valor – 1).
A execução do programa da Figura 6 inicia pela função principal, a qual solicita ao 
usuário um número a ser digitado. Na linha 12, a função recursiva fatorial() é invocada, 
passando o valor digitado como parâmetro. Dentro desta função, enquanto o valor for 
diferente de 1, ela chamará a si mesma, criando novas instâncias na memória, e cada 
vez passando como parâmetro o valor decrementado em 1. Quando o valor chega 
a 1, a função recursiva fatorial() retorna à multiplicação dos valores encontrados em 
cada instância. 
Observe a Figura 7, que ilustra as instâncias quando o usuário entra com o número 3. 
Note que os resultados só são obtidos quando a função chega no caso base e, então, 
começa a retornar o resultado para a instância anterior. Por fim, o valor 6 é retornado 
para a função main(), finalizando as recursões.
Instância 1 Instância 2 Instância 3
main()
fatorial (3) fatorial (2) fatorial (1)
6 2 1
return 3 * fatorial(3-1); return2 * fatorial(2-1); return 1;
Figura 7. Memória de trabalho da função recursiva fatorial().
Recursividade em C10