E-book Unidade 1

Prévia do material em texto

unidade 
1
PROGRAMAÇÃO
Laboratório de
unidade 
1
Funções e Recursividade
Prezado estudante,
Estamos começando uma unidade desta disciplina. Os textos que a compõem foram 
organizados com cuidado e atenção, para que você tenha contato com um conteúdo 
completo e atualizado tanto quanto possível. Leia com dedicação, realize as atividades e 
tire suas dúvidas com os tutores. Dessa forma, você, com certeza, alcançará os objetivos 
propostos para essa disciplina.
OBJETIVO GERAL 
Compreender os conceitos de função e procedimento bem como aplicar o conceito de 
recursão na implementação de programas em linguagem C.
OBJETIVOS ESPECÍFICOS 
• Identificar trechos de códigos que podem ser implementados através de rotinas. 
• Diferenciar variáveis globais e locais.
• Definir recursão.
• Aplicar o conceito de recursão na definição recursiva de funções.
• Identificar as características de funções recursivas 
• Reconhecer problemas que podem ser resolvidos através de soluções recursivas.
• 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.
unidade 
1
O conteúdo deste livro é 
disponibilizado por SAGAH.
Parte 1
Introdução à Modularização.
Variáveis locais Vs
Variáveis globais
LABORATÓRIO DE PROGRAMAÇÃO12
236 Algoritmos e Programação com Exemplos em Pascal e C
A arte de programar consiste na arte de organizar e dominar a complexidade dos sistemas.
— Dijkstra, 1972.
Um aspecto fundamental na programação estruturada é a decomposição de um algoritmo 
em módulos, usando a técnica denominada programação modular (Staa, 2000). O objeti-
vo da programação modular é diminuir a complexidade dos programas, usando a estratégia 
de “dividir para conquistar”: dividir problemas complexos em problemas menores.
Usando essa estratégia, um algoritmo é dividido em partes menores, chamadas de módulos. 
Cada módulo tem um único ponto de entrada, e sua execução termina em um único ponto 
de saída, contendo no seu fluxo de execução: sequências de ações (cap. 3), seleções (cap. 4) e 
iterações (cap. 5). Cada módulo é implementado por um subalgoritmo (subprograma) especí-
fico, passível de ser construído e testado de forma independente. Os diferentes subprogramas 
são posteriormente integrados em um só programa. A modularização tem o objetivo de facili-
tar a compreensão, o desenvolvimento, o teste e a manutenção dos sistemas. Programas que 
utilizam subprogramação resultam mais confiáveis e flexíveis.
Considere que o problema a ser resolvido através do computador é a solução da fórmula que 
calcula as combinações de “n” elementos tomados “p” a “p”:
Para obter o resultado dessa fórmula, por meio de um algoritmo, é necessário fazer três vezes 
o cálculo de um fatorial. O cálculo desses três fatoriais é muito semelhante, só mudando o 
valor limite de cada um. Considerando que tanto o fatorial de 0 quanto o de 1 são iguais a 1 e 
utilizando uma variável inteira contador, esses cálculos podem ser realizados pelos seguintes 
trechos de programa:
{CÁLCULO DO FATORIAL DE N}
fatorial ← 1
para contador de 2 incr 1 até n faça
fatorial ← fatorial * contador
...
{CÁLCULO DO FATORIAL DE (N-P)}
fatorial ← 1
para contador de 2 incr 1 até (n-p) faça
fatorial ← fatorial * contador
...
{CÁLCULO DO FATORIAL DE P}
fatorial ← 1
para contador de 2 incr 1 até p faça
 fatorial ← fatorial * contador
O que muda nos três casos é somente o limite superior do comando para/faça. A repeti-
ção quase igual desses códigos pode ser evitada se for definido um trecho de código inde-
pendente, denominado subprograma, em que o fatorial é calculado. Esse subprograma será 
acionado (chamado) pelo programa em execução cada vez que se quiser calcular um fatorial, 
Edelweiss_09.indd 236 12/03/14 09:02
13 Funções e Recursividade UNIDADE 1 Introdução à Modularização. Variáveis locais Vs Variáveis globais PARTE 1
Capítulo 9 Subprogramas 237
informando somente para qual valor se quer que o fatorial seja calculado, conforme mostra 
a Figura 9.1.
Este capítulo discute o conceito de subprogramação, analisando dois tipos de subprogramas: 
procedimentos e funções.
9.1 conceito de subprogramação
Um subprograma (às vezes chamado de sub-rotina) consiste de um trecho de código com 
estrutura semelhante à de um programa, que é executado somente quando acionado por 
outro trecho de código. Esse acionamento costuma-se denominar chamada ao subprograma.
Um subprograma deve executar uma única tarefa, claramente definida. Um programa, ao uti-
lizar um subprograma para executar uma tarefa, não deve se preocupar em como essa tarefa 
será executada. A execução correta de um subprograma deve ser assegurada sempre que esse 
seja adequadamente chamado.
A utilização de subprogramas é uma técnica de programação que visa:
 ■ a definição de trechos de código menores, mais fáceis de serem construídos e testados;
 ■ a diminuição do tamanho dos programas, pela eliminação de redundâncias, ao evitar 
que códigos semelhantes sejam repetidos dentro de um programa;
 ■ a construção mais segura de programas complexos, pela utilização de unidades menores 
(os subprogramas) já construídas e testadas;
 ■ a reutilização de código em um programa ou em programas diferentes.
Todo subprograma é identificado através de um nome. Esse nome deve representar clara-
mente a tarefa a ser executada pelo subprograma. Por exemplo, o nome adequado para o 
subprograma da Figura 9.1 é Fatorial.
A chamada a um subprograma é feita pelo seu nome, por um comando específico ou utili-
zando diretamente seu resultado, conforme será visto mais adiante. Um mesmo subprogra-
Algoritmo Combinações
início
...
execute Fatorial (n)
...
execute Fatorial (n 
...
execute Fatorial (p)
...
fim
Fatorial (valor)
Subprograma que faz o 
cálculo do fatorial de 
“valor”
Programa principal
Subprograma
- p)
figura 9.1 Chamadas ao subprograma que calcula o fatorial.
Edelweiss_09.indd 237 12/03/14 09:02
LABORATÓRIO DE PROGRAMAÇÃO14
238 Algoritmos e Programação com Exemplos em Pascal e C
ma pode ser chamado e executado diversas vezes, em diferentes pontos de um programa. 
Adicionalmente, um subprograma também pode conter chamadas a outros subprogramas.
9.2 implementação de chamadas a subprogramas
Quando um subprograma é chamado, o fluxo de execução do programa ou subprograma 
que o chamou é interrompido e o subprograma passa a ser executado. Terminada a execução 
do subprograma, o fluxo de execução interrompido é retomado, e o processamento segue a 
partir do ponto imediatamente após a chamada concluída. Na Figura 9.2, é mostrado, por 
meio de setas, o fluxo de execução de um programa que chama o subprograma, o qual cal-
cula o fatorial.
Como já mencionado, um subprograma pode chamar outro subprograma. A forma de exe-
cução é sempre a mesma: o que chamou fica suspenso, esperando o término da execução 
do subprograma chamado, continuando depois sua execução a partir da instrução seguinte à 
instrução de chamada do subprograma.
Na Figura 9.3 é mostrado o fluxo de controle, representado simbolicamente por meio de 
setas, entre um programa e diversos subprogramas. O programa principal, durante sua exe-
cução, chama o subprograma A, ficando suspenso à espera do final da execução de A. O 
subprograma A, por sua vez, chama o subprograma B, ficando também suspenso enquanto 
B não terminar. Em seguida, o subprograma B chama o subprograma C. Durante a execução 
de C (Figura 9.3a), o programa principal e os subprogramas A e B estão suspensos. Quando 
a execução de C termina (Figura 9.3b), o fluxo de controle retorna ao subprograma B, que é 
executado até o fim, devolvendo, então, o controle ao subprograma A. Quando esse último 
termina, devolve o controle ao programa principal, que então continua sendo executado. 
Observar que somente um dos módulos (programa principal ousubprograma) estará sendo 
executado a cada momento.
Cada vez que a execução de um código é interrompida, é necessário que os recursos locais 
(ponto em que o programa fez a chamada, valores de variáveis locais, etc.) de quem fez a 
Algoritmo Combinações
Início
...
execute Fatorial (n)
...
fim
Fatorial (valor)
Programa principal
Subprograma
figura 9.2 Fluxo de execução entre programa e subprograma.
Edelweiss_09.indd 238 12/03/14 09:02
15 Funções e Recursividade UNIDADE 1 Introdução à Modularização. Variáveis locais Vs Variáveis globais PARTE 1
Capítulo 9 Subprogramas 239
chamada sejam preservados e permaneçam disponíveis até o momento em que seja possível 
retomar essa execução.
Em consequência, a implementação das sucessivas chamadas a subprogramas nas linguagens 
em discussão neste livro implica na criação, pelo sistema, de uma estrutura de pilha, para ar-
mazenamento dos elementos locais das chamadas interrompidas, assim como dos endereços 
dos pontos a partir de onde as execuções devem ser retomadas. À medida que chamadas vão 
sendo feitas e interrompidas, a pilha vai recebendo valores. Quando a condição de término 
das chamadas é atingida, progressivamente as chamadas suspensas vão sendo concluídas e 
seus elementos locais restaurados, a partir da pilha. Embora não seja usual haver limitação 
para o número de níveis de chamadas a subprogramas nas linguagens, o espaço de armaze-
namento reservado para a pilha de elementos locais é finito e, se ultrapassado, pode determi-
nar a ocorrência de erros de processamento.
A execução de um subprograma, considerando a estrutura da pilha associada, compreende 
os seguintes passos:
a início da execução – criação de elementos locais, declarados no subprograma;
b processamento – tentativa de execução do código do subprograma até o seu final. Se 
a execução for interrompida por uma chamada a um subprograma, empilhamento dos 
elementos locais e do endereço de retorno, antes de ativação de nova chamada;
Execute A
Programa 
principal
Subprograma
A
Execute B
Subprograma
B
Execute C
Subprograma
C
(a)
(b)
Execute A
Programa 
principal
Subprograma
A
Execute B
Subprograma
B
Execute C
Subprograma
C
figura 9.3 Vários níveis de chamadas a subprogramas.
Edelweiss_09.indd 239 12/03/14 09:02
LABORATÓRIO DE PROGRAMAÇÃO16
240 Algoritmos e Programação com Exemplos em Pascal e C
c final da execução de uma chamada do subprograma – liberação das áreas de memória 
locais e retorno ao ponto de onde o subprograma foi chamado. O ponto da chamada 
pode integrar outra chamada em suspenso, que só então poderá ser concluída;
d retomada de uma execução interrompida – elementos locais são restaurados, a partir da 
pilha gerida pelo sistema, e o processamento é retomado a partir do endereço também 
retirado da pilha.
9.3 parâmetros
Os valores que um subprograma necessita receber para poder realizar sua tarefa, ou os valo-
res que produz e que devem ser visíveis externamente após concluída sua execução, devem 
ser sempre armazenados em parâmetros. Parâmetros são espaços de armazenamento que 
permitem a comunicação do subprograma com o mundo externo. No subprograma que cal-
cula o fatorial, tanto o número para o qual deve ser realizado esse cálculo, quanto o resulta-
do produzido, são valores que potencialmente devem ser armazenados em parâmetros. Um 
subprograma que não utiliza parâmetros e não utiliza informação do mundo exterior para 
seu acionamento, produzirá sempre o mesmo resultado, não importa de onde seja chamado.
9.3.1 parâmetros formais e reais
Todos os elementos utilizados em um subprograma devem ser nele declarados. As declara-
ções de parâmetros, além de nomeá-los para uso interno no subprograma, definem seu tipo. 
Os parâmetros que aparecem na declaração dos subprogramas são chamados de parâme-
tros formais porque, durante a execução, na chamada dos subprogramas, são substituídos 
por variáveis ou valores do mesmo tipo, muitas vezes com nomes totalmente diferentes.
Como exemplo, vamos considerar um subprograma que calcula o fatorial de um número:
Subprograma Fatorial
 Parâmetro: número (inteiro)
O parâmetro formal número não provoca a reserva de espaço na memória. Ele simplesmente 
indica que, ao ser chamado o subprograma Fatorial, deve ser fornecido um número inteiro 
para sua execução.
Os parâmetros utilizados na chamada de um subprograma, chamados de parâmetros reais, 
substituem os formais durante sua execução. Os parâmetros reais devem sempre concordar 
em quantidade e tipo com os respectivos parâmetros formais, na ordem em que esses foram 
definidos. Podem ser fornecidos como parâmetros reais nomes de variáveis, valores literais ou 
resultados de expressões. As variáveis utilizadas como parâmetros reais devem ter sido decla-
radas no programa que chama o subprograma.
No exemplo anterior do subprograma Fatorial, o parâmetro real que vai substituir número 
pode ser fornecido por meio de um valor literal inteiro, do conteúdo de uma variável inteira 
ou de uma expressão que resulte em um valor inteiro. Se, no programa principal, estiverem 
Edelweiss_09.indd 240 12/03/14 09:02
17 Funções e Recursividade UNIDADE 1 Introdução à Modularização. Variáveis locais Vs Variáveis globais PARTE 1
Capítulo 9 Subprogramas 241
declaradas as variáveis inteiras int1 e int2, os seguintes comandos podem ser utilizados para 
chamar o subprograma Fatorial:
execute Fatorial (5)
execute Fatorial (int1)
execute Fatorial (int1 + int2)
Na primeira chamada, o parâmetro formal número é substituído pelo valor 5; na segunda 
chamada, número é substituído pela variável int1; e, na última chamada, número é substi-
tuído pelo resultado da expressão int1 + int2.
9.3.2 parâmetros de entrada e de saída
A utilização de um subprograma só é efetiva se for claramente definida a tarefa que será 
executada e qual sua interação com o programa que o acionou. Para que isso seja possível, 
é importante que toda a interação seja feita somente através dos parâmetros, identificando 
quais os parâmetros de entrada (que recebem variáveis ou valores para executar a tarefa) 
e quais os parâmetros de saída (que devolvem os valores calculados ao programa que 
acionou o subprograma).
No exemplo anterior, do subprograma que calcula o fatorial, não foi definido como o resulta-
do deveria ser devolvido ao programa. Um segundo parâmetro deve ser definido, por meio do 
qual será informado o valor calculado para o fatorial. No cabeçalho da declaração do subpro-
grama devem ser identificados os parâmetros de entrada (que recebem variáveis ou valores 
para a execução) e os de saída (que devolvem valores):
Subprograma Fatorial
 Parâmetro de entrada: número (inteiro)
 Parâmetro de saída: fat (inteiro)
As chamadas a Fatorial devem fornecer agora dois parâmetros reais, sendo o primeiro 
parâmetro o número para o qual se quer calcular o fatorial, e o segundo, o nome de uma 
variável na qual será devolvido o resultado:
execute Fatorial (4, int1)
execute Fatorial (int1 + 7, int1)
Na primeira chamada, o resultado do cálculo do fatorial de 4 é devolvido através da variável 
int1; na segunda chamada, o conteúdo da variável int1 é alterado após a execução, pas-
sando a conter o valor do fatorial do valor que armazenava anteriormente somado com a 
constante 7.
9.3.3 parâmetros por valor ou por referência
A passagem de valores a subprogramas pode acontecer por valor ou por referência.
A passagem por valor indica que somente o valor interessa ao subprograma. Se esse valor for 
passado por meio do nome de uma variável, somente o valor da variável é transferido para o 
Edelweiss_09.indd 241 12/03/14 09:02
LABORATÓRIO DE PROGRAMAÇÃO18
242 Algoritmos e Programação com Exemplos em Pascal e C
parâmetro. Uma cópia do conteúdo da variável é carregadaem uma variável auxiliar, que será 
utilizada durante a execução do subprograma. Dessa forma, qualquer modificação no valor 
da variável auxiliar não se refletirá na variável utilizada como parâmetro real. A passagem de 
valores para parâmetros definidos por valor pode ser feita ainda por meio de um valor literal e 
do resultado de uma expressão. Na execução da chamada a um subprograma, os parâmetros 
passados por valor também são incluídos na pilha de execução, preservando seus valores para 
a continuação posterior da execução.
Na passagem de um parâmetro por referência, o endereço físico da variável utilizada como 
parâmetro real é passado ao subprograma, sendo essa variável utilizada durante a execução. 
Alterações no valor do parâmetro são feitas diretamente nessa variável. Na chamada de um 
subprograma, os parâmetros definidos por referência recebem nomes de variáveis existentes 
no programa principal. É importante observar que, na execução de uma chamada ao subpro-
grama, os parâmetros por referência não sofrem empilhamento, já que não são locais aos 
subprogramas.
No exemplo anterior do subprograma Fatorial, o primeiro parâmetro – de entrada – é pas-
sado por valor. O segundo, que devolve o valor calculado, deve ser definido por referência. 
Na pseudolinguagem, um parâmetro passado por referência é identificado pela palavra ref 
antes de seu nome:
Subprograma Fatorial
 Parâmetro de entrada: número (inteiro)
 Parâmetro de saída: ref fat (inteiro)
9.4 declarações locais e globais
Dentro de um subprograma, podem ser feitas declarações de constantes, tipo e variáveis. As 
declarações feitas internamente aos subprogramas são declarações locais ao subprograma, 
e só são visíveis dentro do subprograma. As áreas de memória associadas às variáveis locais 
são alocadas no momento em que o subprograma é acionado e são liberadas ao final de sua 
execução, quando deixam de existir. Todo esse processo de criação e destruição de variáveis 
locais ocorre novamente a cada nova chamada ao subprograma.
Como exemplo de utilização de uma variável local, será considerado um subprograma que 
permuta o conteúdo de duas variáveis inteiras. Os parâmetros formais A e B representam 
as duas variáveis e, neste exemplo, desempenham o papel tanto de parâmetros de entrada 
quanto de saída. Para fazer a permuta é necessário uma terceira variável para guardar um 
dos valores durante o processamento. Essa será definida como uma variável local, pois sua 
existência não é relevante para o programa principal:
Subprograma Permuta
{TROCA O CONTEÚDO DE DUAS VARIÁVEIS}
 Parâmetros entrada e saída: ref A, ref B (inteiro)
 Variável: aux (inteiro) {VARIÁVEL LOCAL}
Edelweiss_09.indd 242 12/03/14 09:02
19 Funções e Recursividade UNIDADE 1 Introdução à Modularização. Variáveis locais Vs Variáveis globais PARTE 1
Capítulo 9 Subprogramas 243
início
 aux ← A
 A ← B
 B ← aux
fim {TrocaDois}
No fim da execução do subprograma Permuta, a variável aux é liberada e não está mais dis-
ponível.
Tipos, constantes e variáveis declarados em um programa, visíveis aos subprogramas que 
estiverem nele declarados, são consideradas declarações globais ao programa.
Embora elementos globais possam ser utilizados dentro de subprogramas, essa prática não é 
recomendável, pois dificulta o entendimento e a depuração dos códigos, podendo facilmente 
ocasionar erros. Toda interação de um subprograma com o programa que o chama, no limite 
das possibilidades de cada linguagem, deve ser feita através de parâmetros, devendo os de-
mais elementos necessários à execução de sua tarefa ser declarados localmente.
Segue um quadro resumo das características das declarações locais e globais.
Locais Globais
Declaradas internamente aos subpro-
gramas que as acessam.
Declaradas externamente aos subpro-
gramas que as acessam.
Só são reconhecidas e só podem ser 
referenciadas nos subprogramas em 
que estão declaradas.
São reconhecidas e podem ser refe-
renciadas até mesmo em subprogramas 
em que não foram declaradas.
Existem apenas enquanto os subpro-
gramas em que foram declaradas es-
tiverem em execução.
Sua existência independe dos sub-
programas que as acessam. Existem 
antes, durante e após a ativação 
deles.
Internamente a um subprograma, 
quando têm o mesmo nome que uma glo-
bal, bloqueiam o acesso à global.
9.4.1 escopo de identificadores
A possibilidade de fazer declarações em diferentes pontos de um programa (no programa 
principal e em subprogramas) requer que seja claramente identificado o escopo de cada iden-
tificador. Por escopo entende-se a área de validade de um determinado identificador. O es-
copo de um identificador é definido pela localização de sua declaração. Declarações feitas 
no programa principal valem em todo o programa, inclusive, por vezes, nos subprogramas 
que o compõem. Declarações feitas dentro de um subprograma valem somente dentro desse 
subprograma. Exemplo:
Edelweiss_09.indd 243 12/03/14 09:02
LABORATÓRIO DE PROGRAMAÇÃO20
244 Algoritmos e Programação com Exemplos em Pascal e C
Programa Exemplo
 Variáveis:
 um (inteiro)
 dois (real)
{------------------------------------------------}
Subprograma Sub
 Parâmetro de entrada: valor (inteiro)
 Parâmetro de saída: ref result (real)
 Variáveis locais:
 loc1, loc2 (inteiro)
início
 {AQUI PODEM SER UTILIZADOS:
 – os parâmetros valor e result
 – as variáveis globais um e dois
 – as variáveis locais loc1 e loc2 }
...
fim {Sub}
{------------------------------------------------}
início
 { AQUI PODEM SER UTILIZADAS:
 – as variáveis um e dois
 – chamadas ao subprograma Sub}
fim {PROGRAMA PRINCIPAL}
Nas declarações feitas dentro dos subprogramas, podem ser utilizados nomes iguais a outros 
elementos (constantes, tipos ou variáveis) já existentes no programa principal. No exemplo a 
seguir, no programa principal é declarada uma variável item, do tipo inteiro. No subprogra-
ma, é definida uma variável local com o mesmo nome (item), do tipo caractere. Dentro do 
subprograma, qualquer referência ao identificador item se refere à variável local, ficando a 
global de mesmo nome inacessível.
Programa Exemplo
 Variáveis:
 item (inteiro)
 glob (real)
{------------------------------------------------}
Subprograma Sub
 Parâmetro de entrada: valor (inteiro)
 Parâmetro de saída: ref result (real)
 Variável local:
 item (caractere)
início
 {AQUI PODEM SER UTILIZADOS:
Edelweiss_09.indd 244 12/03/14 09:02
21 Funções e Recursividade UNIDADE 1 Introdução à Modularização. Variáveis locais Vs Variáveis globais PARTE 1
Capítulo 9 Subprogramas 245
 – os parâmetros valor e result
 – a variável global glob
 – a variável local item (caractere) }
...
fim {Sub}
{------------------------------------------------}
início
 { AQUI PODEM SER UTILIZADAS:
 – as variáveis item (inteiro) e glob
 – chamadas ao subprograma Sub}
fim {PROGRAMA PRINCIPAL}
O escopo dos identificadores deve ser atentamente observado quando existirem declarações 
de subprogramas dentro de subprogramas, todos com declarações locais. A Figura 9.4 
mostra graficamente essa situação, considerando um programa principal dentro do qual 
está declarado um subprograma A. Dentro do subprograma A, está declarado outro sub-
programa B. À direita na figura estão representadas as variáveis que podem ser utilizadas 
por comandos dentro de cada um desses blocos – programa principal, subprograma A e 
subprograma B.
Programa
principal 
Subprograma A
Subprograma B
Variáveis
pp1, pp2
Variáveis
a1, a2, a3
Variáveis
b1, b2
< comandos de A >
< comandos de B >
< comandos do
Programa principal > 
pp1,
pp2 
pp1, pp2,
a1, a2, a3 
pp1, pp2, a1, a2,
a3, b1, b2 
figura 9.4 Escopo dos identificadores.
Edelweiss_09.indd 245 12/03/14 09:02
LABORATÓRIODE PROGRAMAÇÃO22
246 Algoritmos e Programação com Exemplos em Pascal e C
Cabe lembrar mais uma vez que não é aconselhável utilizar variáveis globais dentro dos sub-
programas. Sempre que possível, toda a comunicação dos subprogramas com os programas 
que os acionam deverá ser feita através de parâmetros.
9.5 tipos de subprogramas
Dois tipos de subprogramas podem ser utilizados, diferenciados pela forma como são aciona-
dos e o modo como devolvem seus resultados: procedimentos e funções.
9.5.1 procedimentos
Um procedimento é um subprograma que executa uma determinada tarefa com ou sem 
a utilização de parâmetros. Na pseudolinguagem, a declaração de um procedimento é feita 
como segue:
Procedimento <nome do procedimento>
{ <Descrição da tarefa executada pelo procedimento> }
 <Lista de parâmetros formais, cada um com seu tipo,
 identificando os de entrada e os de saída>
 <Lista de constantes, tipos e variáveis locais>
início
 <Comandos do procedimento>
fim {<nome do procedimento>}
Na lista de parâmetros formais, os parâmetros por referência devem ser identificados 
pela sigla ref antes do seu nome. Os parâmetros de saída devem sempre ser definidos por 
referência.
Por exemplo, a declaração de um procedimento que calcula o fatorial de um número é:
Procedimento Fatorial
{CALCULA O FATORIAL DE UM NÚMERO}
 Parâmetro entrada: número (inteiro)
 Parâmetro de saída: ref fat (inteiro)
 Variável local: contador (inteiro)
início
 fat ← 1
 para contador de 1 incr 1 até número faça
 fat ← fat * contador
fim {Fatorial}
Os procedimentos são acionados por meio de um comando especial. Na pseudolinguagem, 
esse comando é:
execute <nome do procedimento> (< lista de parâmetros reais >)
Edelweiss_09.indd 246 12/03/14 09:02
23 Funções e Recursividade UNIDADE 1 Introdução à Modularização. Variáveis locais Vs Variáveis globais PARTE 1
Capítulo 9 Subprogramas 247
Na chamada ao procedimento Fatorial, devem ser fornecidos dois parâmetros: o primeiro 
deve ser o valor para o qual se quer calcular o fatorial, que pode ser um valor literal, o con-
teúdo de uma variável ou o resultado de uma expressão aritmética; o segundo deve ser o 
nome da variável na qual será devolvido o resultado do cálculo efetuado.
Se a1, a2 e a3 forem variáveis inteiras, podem ser feitas as seguintes chamadas ao procedi-
mento Fatorial:
execute Fatorial (a1, a2) {a2 DEVOLVE FATORIAL DE a1}
execute Fatorial (a2, a3) {a3 DEVOLVE FATORIAL DE a2}
execute Fatorial (7, a2) {a2 DEVOLVE FATORIAL DE 7}
execute Fatorial (a1+2,a3){a3 DEVOLVE FATORIAL DE (a1+2)}
9.5.2 funções
Uma função é um subprograma que devolve um valor, resultante de um cálculo ou da exe-
cução de uma determinada tarefa, ao programa que o chamou por meio de seu nome. Uma 
função tem sempre associado a ela um tipo, que é o tipo do valor que ela devolve.
Na pseudolinguagem, a declaração de uma função é feita como segue:
Função <nome da função> : <tipo do resultado>
{ <Descrição do que é calculado pela função> }
 <Lista de parâmetros formais, cada um com seu tipo>
 <Lista de constantes, tipos e variáveis locais>
início
 <Comandos>
fim {<nome da função>}
Em algum lugar do corpo da função, o valor calculado pela função deve ser atribuído ao seu 
nome, para ser devolvido ao programa que a chamou. O nome da função deve, portanto, 
aparecer pelo menos uma vez, no corpo da função, à esquerda de uma atribuição:
<nome da função > ← <valor|variável|expressão|função|constante>
Uma função não é chamada através de um comando especial, como no caso dos procedi-
mentos. A chamada é feita escrevendo seu nome, com os parâmetros reais, no ponto do có-
digo onde se deseja que o seu valor seja utilizado. Como exemplo, segue o cálculo do fatorial 
feito por meio de uma função e não de um procedimento, como mostrado na seção anterior:
Função Fatorial: inteiro
{CALCULA O FATORIAL DE UM VALOR INTEIRO}
 Parâmetro de entrada:
 número (inteiro) {NÚMERO PARA O QUAL SE QUER O FATORIAL}
 Variáveis locais:
 índice (inteiro)
 fat (inteiro)
início
Edelweiss_09.indd 247 12/03/14 09:02
LABORATÓRIO DE PROGRAMAÇÃO24
248 Algoritmos e Programação com Exemplos em Pascal e C
 fat ← 1
 para índice de 1 incr 1 até número faça
 fat ← fat * índice
 Fatorial ← fat {DEVOLUÇÃO DE UM VALOR PELA FUNÇÃO}
fim {Fatorial}
Sendo fat1, n, p e comb variáveis inteiras, as chamadas à função Fatorial a seguir são válidas:
fat1 ← Fatorial(7) {fat1 RECEBE O VALOR DO FATORIAL DE 7}
escrever (Fatorial(n)) {INFORMA FATORIAL DO VALOR CONTIDO EM n}
comb ← Fatorial(n) / (Fatorial (n-p) * Fatorial(p))
 {comb RECEBE CÁCULO DAS COMBINAÇÕES DE n ELEMENTOS p A p}
A execução de uma função termina quando seu final lógico é encontrado, ou seja, quando 
a execução atinge o ponto final da função. No caso da função Fatorial, por exemplo, isso 
ocorre quando fim {Fatorial}é atingido.
Embora, pelo conceito fundamental de função, deva ser devolvido somente um valor por 
meio de seu nome, sintaticamente parâmetros de saída também podem ser utilizados, devol-
vendo também valores ao programa que a aciona. Essa prática não é aconselhada porque, 
além de contrariar o conceito de função, torna os códigos mais complexos, favorecendo a 
ocorrência de erros. Assim, aconselha-se: sempre que uma função for utilizada, devolver ape-
nas o valor em seu nome.
As chamadas a funções podem ocorrer em qualquer ponto do código em que o uso de um 
valor seja sintaticamente correto. Isso significa que funções podem ser usadas, por exemplo, 
em atribuições, em expressões, em comandos de saída, na chamada de outras funções e em 
testes.
9.6 refinamentos sucessivos e programação modular
O uso de subprogramação com o objetivo de facilitar a construção de programas deve ser 
feito seguindo técnicas apropriadas, de acordo com a programação estruturada, conforme 
visto na Seção 1.4, no Capítulo 1.
Uma das técnicas aconselhadas pela programação estruturada é o desenvolvimento de al-
goritmos por fases ou refinamentos sucessivos. Isso é feito concentrando-se inicialmente nas 
tarefas maiores a serem executadas e no fluxo de controle entre elas. Uma vez essa fase es-
tando bem definida, cada uma das tarefas identificadas é então refinada gradualmente, até 
que se chegue aos algoritmos finais que podem ser codificados em alguma linguagem de 
programação.
Essa técnica, também denominada top down, traz como consequência uma maior clareza no 
entendimento do problema como um todo, por não considerar inicialmente detalhes de im-
plementação. Gera, também, uma documentação mais clara e compreensível dos algoritmos.
Edelweiss_09.indd 248 12/03/14 09:02
LABORATÓRIO DE PROGRAMAÇÃO26
ENCERRA AQUI O TRECHO DO LIVRO DISPONIBILIZADO 
PELA SAGAH PARA ESTA PARTE DA UNIDADE.
PREZADO ESTUDANTE
unidade 
1
O conteúdo deste livro é 
disponibilizado por SAGAH.
Parte 2
Recursão
LABORATÓRIO DE PROGRAMAÇÃO 28
Recursão
Objetivos de aprendizagem
Ao final deste texto, você deve apresentar os seguintes aprendizados:
 � Definir recursão.
 � Aplicar o conceito de recursão na definição recursiva de funções.
 � Implementar a solução de problemas por meio da recursão.
Introdução
Neste capítulo, aprofundaremos os conhecimentos sobre recursão. 
Verificaremos que há uma relação bem próxima entre indução e recursão. 
Como exemplo, pode-se pensar em quando definimos uma sequência 
recursivamente, especificando como os seus termos são encontrados a 
partir de termos anteriores, e podemos usar a indução para demonstrar 
os resultados dessa sequência. A indução matemática pode ser utilizada 
para demonstrar diversos resultados. Além de recursão ser um conceito 
próximo ao de indução, é de fundamental importância para a ciência 
da computação.
Além disso, quase a totalidade das linguagens de programação 
modernas possui recursão como um construtor básico de programas. 
A maioria dos computadores atuaisconta com facilidades para implemen-
tar recursão, o que faz com que o processamento de recursão alcance 
bons níveis de eficiência.
Neste capítulo, você encontrará conceitos teóricos, teoremas e defi-
nições, e, ao mesmo tempo, serão fornecidos exemplos ilustrativos com 
a finalidade de auxiliar na compreensão do tema em estudo e ampliar 
seus conhecimentos.
29 Funções e Recursividade UNIDADE 1 Recursão PARTE 2
1 Indução e recursão
Para explicar o conceito de indução, Rosen (2009) utiliza o exemplo de uma 
escada infinita. A ideia é verificar se podemos alcançar todos os degraus dessa 
escada. Sabemos duas coisas:
1. podemos alcançar o primeiro degrau da escada;
2. se pudermos alcançar um determinado degrau da escada, então pode-
remos alcançar o próximo degrau. 
Sabemos que, por (1), podemos alcançar o primeiro degrau da escada. Além 
disso, como é possível alcançar o primeiro, por (2), podemos também alcançar 
o segundo degrau, que é o próximo degrau depois do primeiro. Aplicando 
(2) outra vez, como podemos alcançar o segundo degrau, podemos também 
alcançar o terceiro. Continuamos assim e podemos mostrar que será possível 
alcançar o quarto, o quinto degrau, e assim por diante. Depois de usar 100 
vezes (2), sabemos que poderemos alcançar o 101º degrau. Dessa maneira, é 
possível concluir que podemos alcançar todos os degraus dessa escada infi-
nita. Essa verificação também pode ser realizada utilizando uma importante 
técnica de demonstração, chamada de indução matemática. Ou seja, podemos 
mostrar que P(n) é verdadeira para todo número inteiro positivo n, em que 
P(n) é a proposição que afirma que podemos alcançar o n-ésimo degrau da 
escada (ROSEN, 2009).
Rosen (2009) explica que, de modo geral, a indução matemática pode ser 
utilizada para demonstrar proposições que afirmam que P(n) é verdadeira para 
todos os números inteiros positivos n, em que P(n) é uma função proposicional. 
A demonstração é dividida em duas partes, um passo base em que se mostra 
que P(1) é verdadeira, e um passo de indução, em que se mostra que para todos 
os números inteiros k, se P(k) for verdadeira, então P(k + 1) é verdadeira.
Definir um objeto explicitamente nem sempre é fácil, mas é possível 
defini-lo em termos dele próprio, esse processo é chamado de recursão. Para 
ficar mais claro, observe a Figura 1: ela é produzida recursivamente, ou seja, 
primeiro é dada uma ilustração, depois é realizado um processo de sobre-
posições de sucessivas centralizações de fotos menores sobre a ilustração 
anterior (ROSEN, 2009).
Recursão2
LABORATÓRIO DE PROGRAMAÇÃO 30
Figura 1. Uma ilustração definida recursivamente.
Fonte: Rosen (2009, p. 295).
A recursão pode ser usada para definir sequências, funções e conjuntos. 
Podemos pensar em uma sequência que usa uma fórmula explícita, por exemplo, 
a sequência de potências de 2 que é dada por an = 2
n para n = 0,1,2,… Entre-
tanto, essa sequência pode também ser definida a partir do primeiro termo da 
sequência, a0 = 1, e de uma regra para encontrar um termo a partir do anterior, 
an+1 = 2an para n = 0,1,2,… Quando definimos uma sequência recursivamente, 
especificando como os seus termos são encontrados a partir de termos ante-
riores, podemos usar a indução para demonstrar os resultados da sequência. 
Nota-se aqui a relação existente entre indução e recursão (ROSEN, 2009).
Neste contexto, Rosen (2009) destaca que podemos definir um conjunto 
recursivamente, especificando alguns elementos iniciais em um passo e forne-
cendo uma regra para a construção de novos elementos a partir daqueles obtidos 
no passo recursivo, como vimos no caso das sequências. Para demonstrar os 
resultados de recursividade em conjuntos, utiliza-se um método chamado de 
indução estrutural, ou recursão.
3Recursão
31 Funções e Recursividade UNIDADE 1 Recursão PARTE 2
2 Definição recursiva de funções
Nesta seção veremos como as funções são definidas recursivamente. Rosen 
(2009) explica que se utilizam duas etapas para definir uma função com o 
conjunto dos números inteiros não negativos como seu domínio: passo base: 
em que se especifica o valor da função em zero; passo recursivo: em que se 
fornece uma regra para encontrar seu valor em um número inteiro a partir 
dos valores nos números inteiros menores. Essa definição é chamada de re-
cursividade ou definição indutiva. Vejamos alguns exemplos de funções que 
podem ser estudadas usando suas definições recursivas.
Confira a seguir alguns exemplos (ROSEN, 2009, p. 296–297).
Exemplo 1 — Dê uma definição recursiva da função fatorial F(n) = n!.
Solução: podemos definir a função fatorial especificando seu valor inicial, ou seja, F(0) = 1, 
e dando uma regra para encontrar F(n + 1) a partir de F(n). Isso é obtido notando que 
(n + 1)! é computado a partir de n! multiplicado por n + 1. Assim, a regra desejada é:
F(n + 1) = (n + 1)F(n)
Exemplo 2 — Determine um valor de uma função fatorial, tal como F(5) = 5! a partir 
da definição recursiva F(n + 1) = (n + 1)F(n).
Solução: neste caso é necessário usar a regra que mostra como expressar F(n + 1) 
em termos de F(n):
F(5) = 5F(4) = 5 · 4F(3) = 5 · 4 · 3F(2) = 5 . 4 . 3 . 2F(1) = 5 . 4 . 3 . 2 . 1 . F(0) 
= 5 · 4 · 3 · 2 · 1 · 1 = 120
Exemplo 3 — Dê uma definição recursiva de an, em que a é um número real diferente 
de zero e n é um número inteiro não negativo.
Solução: a definição recursiva contém duas partes. Primeiro a0 é determinado, ou 
seja, a0 = 1. Então, é dada a regra para encontrar an+1 a partir de an, ou seja, an+1 = a · 
an, para n = 0,1, 2, 3, … Estas duas equações definem unicamente an para todos os 
números inteiros não negativos n.
Recursão4
LABORATÓRIO DE PROGRAMAÇÃO 32
Exemplo 4 — Dê uma definição recursiva de ∑nk=0 ak.
Solução: a primeira parte da definição recursiva é:
A segunda parte é:
Rosen (2009) afirma que as funções definidas recursivamente são bem 
definidas, isso significa que para todo número inteiro positivo, o valor da 
função neste inteiro é determinado de forma não ambígua. Ou seja, com 
qualquer número inteiro positivo, é possível usar as duas partes da definição 
para encontrar o valor da função naquele inteiro, e significa que obtemos o 
mesmo valor, não importando como aplicamos as duas partes da definição.
Para a ciência da computação, o estudo das funções recursivas e da re-
cursão em geral é de fundamental importância. Ela permite que uma simples 
função represente um algoritmo consideravelmente complexo. Além disso, em 
muitas instituições de ensino, linguagens baseadas em funções recursivas são 
usadas como uma primeira linguagem de programação, sendo que as funções 
recursivas, em particular o cálculo do lambda, possuem importantes aplicações 
em outros contextos da ciência da computação, como por exemplo, lógica e 
linguagens de programação (MENEZES, 2013). Vejamos um exemplo para o 
entendimento da recursão de uma linguagem de programação.
5Recursão
33 Funções e Recursividade UNIDADE 1 Recursão PARTE 2
Definição indutiva: fatorial
Para um dado número natural n, define-se o fatorial n! como segue:
n! = 1, se n = 0
n! = n * (n – 1) ∙ (n – 2) ... * 1, se n > 0
Para o caso n > 0, observe que n! pode ser reescrito como segue:
n * (n – 1)!
Sendo que:
(n – 1)! = (n – 1) * (n – 2) ... * 1
Da mesma forma, (n – 1)! pode ser reescrito como segue:
(n – 1) * (n – 2)!
Sendo que:
(n – 2)! = (n – 2) * (n – 3) * ... *1
E assim sucessivamente. Portanto, o fatorial de um número n pode ser determinado 
multiplicando n pelo fatorial de seu antecessor n – 1. Tal raciocínio pode ser recursiva-
mente aplicado até chegar ao fatorial de zero. Logo, a função fatorial pode ser definida 
em termos dela mesma, até atingir o fatorial de zero, como segue.
a) Base de indução:
0! = 1
b) Passo de indução:
n! = n * (n – 1)!
Exemplificando, o cálculo do fatorial de 4 é como segue:
4! = 4 * (4 – 1)! = 4 * 3! = passo de indução
4 * 3 * (3 – 1)! = 4 * 3 * 2! = passo de indução
4 * 3 * 2 * (2 – 1)! = 4 * 3 *2 * 1! = passo de indução
4 * 3 * 2 * 1 * (1 – 1)! = 4 * 3 * 2 * 1 * 0! = base de indução
4 * 3 * 2 * 1 * 1 = 24
O mesmo princípio pode ser adotado nas linguagens de programação, usando 
o conceito de recursão, ou seja, o de uma função definida em termos dela mesma. 
Essa definição pode ser direta (uma função referencia a si mesma) ou indireta (uma 
função referencia outra função que, por sua vez, direta ou indiretamente, referencia 
a primeira) (MENEZES, 2013, p. 216–217).
Recursão6
LABORATÓRIO DE PROGRAMAÇÃO 34
Outro ponto importante a destacar é que em algumas definições recursivas 
de funções, os valores da função dos primeiros k números inteiros positivos 
são especificados e uma regra é dada para determinar o valor da função para 
números inteiros maiores a partir de seus valores para alguns ou todos os k 
números inteiros precedentes (ROSEN, 2009). Vejamos a definição dos núme-
ros de Fibonacci conforme Rosen (2009, p. 297): “Os números de Fibonacci, 
f0, f1, f2, …, são definidos pelas equações f0 = 0, f1 = 1 e fn = fn–1 + fn–2 para 
n = 2, 3, 4, ...”.
Veja, a seguir, um exemplo utilizando a definição recursiva dos números 
de Fibonacci.
Confira a seguir um exemplo (ROSEN, 2009, p. 297–298).
Mostre que, sempre que n ≥ 3, fn > ∝n–2, em que ∝ = (1 + √5
–)/2.
Solução:
Podemos usar a indução completa para demonstrar esta inequação. Considere P(n) 
como a proposição de que fn > ∝n–2. Queremos mostrar que P(n) é verdadeira sempre 
que n for um número inteiro maior que ou igual a 3.
Passo base: primeiro, note que ∝ < 2 = f3, ∝2 = (3 + √5
–)/2 < 3 = f4, então, P(3) e P(4) 
são verdadeiras.
Passo de indução: assuma que P(j) seja verdadeira, ou seja, que fj > ∝n–2, para 
todos os números inteiros j com 3 ≤ j ≤ k, em que k ≥ 4. Devemos mostrar que P(k + 1) 
é verdadeira, ou seja, que fk+1 > ∝k–1. Como ∝ é uma solução de x2 – x – 1 = 0, temos 
que ∝2 = ∝ + 1. Assim,
∝k–1 = ∝2 ∙ ∝k–3 = (∝ + 1) ∝k–3 = ∝ ∙ ∝k–3 + 1 ∙ ∝k–3 = ∝k–2 + ∝k–3
Pela hipótese indutiva, se k ≥ 4, temos que:
fk–1 > ∝k–3, fk > ∝k–2
Assim, temos:
fk+1 = fk + fk–1 > ∝k–2 + ∝k–3 = ∝k–1
7Recursão
35 Funções e Recursividade UNIDADE 1 Recursão PARTE 2
Temos que P(k + 1) é verdadeira. Isso completa a demonstração.
Lembre-se: O passo de indução mostra que, sempre que k > 4, P(k + 1) é dado 
a partir da hipótese de que P(j) seja verdadeira para 3 ≤ j ≤ k. Assim, esse passo não 
mostra que P(3) → P(4). Além disso, mostramos que P(4) é verdadeira separadamente.
3 Solucionando problemas por recursão
Nesta seção veremos que algumas vezes é possível reduzir a solução de um 
problema com um determinado conjunto de valores iniciais para a solução do 
mesmo problema com valores iniciais menores. A exemplo, podemos mencionar 
o problema para encontrar o máximo divisor comum de dois números inteiros 
positivos a e b, em que b > a, que pode ser reduzido a encontrar o máximo 
divisor comum de um par de números inteiros menores, ou seja, b mod a e a, 
pois mdc (b mod a, a) = mdc (a, b), em que mod significa o resto da divisão 
inteira. Quando essa redução pode ser feita, a solução do problema original 
pode ser encontrada com uma sequência de reduções, até que o problema seja 
reduzido ao caso inicial para qualquer solução conhecida. Para encontrar o 
máximo divisor comum, por exemplo, a redução continua até que o menor dos 
dois números seja zero, porque mdc (a, 0) = a quando a > 0 (ROSEN, 2009).
A seguir, veremos os algoritmos que reduzem sucessivamente um problema 
ao mesmo problema com valores iniciais menores, usados para a resolução de 
vários problemas. Para isso, precisamos conhecer a definição que diz que um 
algoritmo é chamado de recursivo se resolver um problema reduzindo-o a um 
mesmo problema com valores iniciais menores (ROSEN, 2009).
Recursão8
LABORATÓRIO DE PROGRAMAÇÃO 36
Os exemplos a seguir foram propostos por Rosen (2009, p. 312–314).sss
Exemplo 1 — Dê um algoritmo recursivo para computar an, em que a é um número 
real diferente de zero e n é um número inteiro não negativo.
Solução: podemos basear um algoritmo recursivo em uma definição recursiva de 
an. Essa definição afirma que an+1 = a ∙ an para n > 0 e a condição inicial a0 = 1. Para 
encontrar an, usamos sucessivamente o passo recursivo para reduzir o expoente até 
que ele se torne zero, como mostra o procedimento a seguir.
Um algoritmo recursivo para computar an
procedure potencia (a: número diferente de zero, n: número inteiro não negativo)
if n = 0 then potencia (a,n) := 1
else potencia (a,n) := a ∙ potencia (a, n – 1)
Exemplo 2 — Construa um algoritmo recursivo para computar bn mod m, em que b, 
n e m são números inteiros com m ≥ 2, n ≥ 0 e 1 ≤ b < m.
Solução: podemos basear um algoritmo recursivo no fato de que: 
bn mod m = (b ∙ (bn–1 mod m)) mod m
que é mantido com a condição inicial b0 mod m = 1. Entretanto, podemos construir 
algoritmos recursivos muito mais eficientes com base na observação de que: 
bn mod m = (bn/2 mod m)2 mod m
Quando n é par e: 
Quando n é ímpar, como vemos em pseudocódigo no algoritmo a seguir.
Potenciação modular recursiva
procedure mpotencia (b,n,m: números inteiros com m ≥ 2, n ≥ 0)
if n = 0 then 
mpotencia(b,n,m) = 1
9Recursão
37 Funções e Recursividade UNIDADE 1 Recursão PARTE 2
else if n é par then
mpotencia(b,n,m) = mpotencia(b, n/2,m)
2 mod m
else
mpotencia(b,n,m) = (mpotencia (mpotencia(b, |n/2|, m)2 mod m ∙ b mod m) mod m
{mpotencia(b,n,m) = bn mod m}
Podemos rascunhar o algoritmo com a entrada b = 2, n = 5 e m = 3 para ilustrar como 
ele funciona. Primeiro, como n = 5 é ímpar, usamos a cláusula “else” para estabelecer que:
mpotencia(2,5,3) = (mpotencia(2,2,3)2 mod 3 ∙ 2 mod 3) mod 3
Depois, usamos a cláusula “else if” para ver mpotencia(2,2,3) = mpotencia(2,1,3)2 
mod 3. Usando novamente “else”, vemos que:
mpotencia(2,1,3) = (mpotencia(2,0,3)2 mod 3 ∙ 2 mod 3) mod 3
Por fim, usamos a sentença “if”, para ver que mpotencia(2,0,3) = 1. Assim, temos que:
mpotencia(2,1,3) = 12 mod 3 ∙ 2 mod 3) mod 3 = 2
Então mpotencia (2,2,3) = 22 mod 3 = 1 e finalmente, mpotencia(2,5,3) = (12 mod 3 
∙ 2 mod 3) mod 3 = 2.
Exemplo 3 — Dê um algoritmo recursivo para computar o máximo divisor comum 
de dois números inteiros não negativos a e b com a < b.
Solução: podemos basear um algoritmo recursivo na redução mdc(a,b) = mdc(b 
mod a,a) e na condição que mdc(0,b) = b quando b > 0. Ilustramos o funcionamento 
do algoritmo calculando-o quando as entradas são a = 5, b = 8. Com essas entradas, o 
algoritmo usa a sentença “else” para encontrar mdc(5,8) = mdc(8 mod 5,5) = mdc(3,5). 
Ele usa esta sentença novamente para encontrar mdc(3,5) = mdc(5 mod 3,3) = mdc(2,3), 
então para ter mdc(2,3) = mdc(3 mod 2,2) = mdc(1,2), então para ter mdc(1,2) = mdc(2 
mod 1,1) = mdc(0,1). Por fim, para encontrar mdc(0,1) ele usa o primeiro passo com a = 
0 para encontrar mdc(0,1) = 1. Consequentemente, o algoritmo encontra mdc(5,8) = 1.
Um algoritmo recursivo para computar mdc(a,b):
procedure mdc(a,b: números inteiros não negativoscom a < b)
if a = 0 then mdc(a,b) ≔ b
else mdc(a,b) := mdc(b mod a,a)
Recursão10
LABORATÓRIO DE PROGRAMAÇÃO 38
ENCERRA AQUI O TRECHO DO LIVRO DISPONIBILIZADO 
PELA SAGAH PARA ESTA PARTE DA UNIDADE.
PREZADO ESTUDANTE
MENEZES, P. B. Matemática discreta para computação e informática. 4. ed. Porto Alegre: 
Bookman, 2013. (Livros didáticos informática UFRGS, v. 16).
ROSEN, K. H. Matemática discreta e suas aplicações. 6. ed. Porto Alegre: AMGH, 2009.
11Recursão
unidade 
1
O conteúdo deste livro é 
disponibilizado por SAGAH.
Parte 3
Recursividade
LABORATÓRIO DE PROGRAMAÇÃO 40
418 Algoritmos e Programação com Exemplos em Pascal e C
Este capítulo discute a implementação de soluções para problemas utilizando a ativação de 
subprogramas de forma recursiva, ou seja, fazendo os subprogramas chamarem a si mesmos. 
A utilização de recursividade é apropriada para o processamento com determinadas estrutu-
ras de dados.
15.1 conceito de recursividade
Um problema é dito recursivo se é definível em termos de si mesmo. Um exemplo disso é a 
definição dos números naturais:
 ■ o primeiro número natural é zero;
 ■ o sucessor de um número natural é um número natural.
Diversas situações do nosso dia a dia podem ser definidas recursivamente. A seguir, são anali-
sados dois casos muito comuns em que a recursividade é tratada naturalmente.
ler 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. O restan-
te do livro tem a mesma estrutura do livro original, sem o capítulo lido, podendo ser tam-
bém encarado como um livro. Se o livro tem 12 capítulos, o processo inicia com a leitura 
do capítulo 1, seguida da leitura do restante do livro, ou seja, dos 11 capítulos restantes. A 
leitura desses 11 capítulos, por sua vez, consiste em ler o primeiro (no caso, o capítulo 2) 
e seguir lendo os 10 capítulos restantes. O processo recursivo se repete até que seja lido o 
último capítulo, ou seja, até não existir o “restante do livro”. Então, a definição recursiva da 
leitura de um livro é:
 ■ ler o primeiro capítulo;
 ■ se houver capítulos depois dele, lê-los.
fila de pessoas no caixa de uma loja. 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. As pessoas que estão 
atrás da pessoa atendida também estão formando uma fila. O processo é então repetido para 
a fila restante até que a última pessoa seja atendida. Assim, o atendimento das pessoas de 
uma fila é como segue:
 ■ atender a primeira pessoa da fila;
 ■ se houver alguém atrás da primeira pessoa, repetir o processo para o restante da fila.
Nesses dois exemplos, pode ser observado que as definições recursivas são condicionadas, no 
primeiro caso, a que exista algum capítulo ainda não lido e, no segundo, a que ainda haja 
alguma pessoa na fila. Pode ser observado ainda que as condições fazem que os processos 
recursivos parem em algum momento.
Edelweiss_15.indd 418Edelweiss_15.indd 418 12/03/14 09:0012/03/14 09:00
41 Funções e Recursividade UNIDADE 1 Recursividade PARTE 3Capítulo 15 Recursividade 419
15.2 subprograma recursivo
O cálculo do fatorial de um número inteiro positivo é utilizado aqui para introduzir a utiliza-
ção de recursividade em subprogramas. Como estudado em aritmética, o cálculo do fatorial 
de um número n, inteiro positivo, é realizado por sucessivas multiplicações:
n! = n · (n-1) · (n-2) · ... · 3 · 2 · 1
Esse cálculo pode ser efetuado por meio de uma função, passando o número para o qual se 
quer calcular o fatorial como parâmetro. Na função Fat, a seguir, o fatorial é calculado por 
meio de um comando de repetição que acumula as multiplicações sucessivas necessárias ao 
cálculo.
Função Fat: inteiro
{CALCULA O FATORIAL DE UM INTEIRO N, PASSADO COMO PARÂMETRO}
 Parâmetro de entrada: N (inteiro)
 Variáveis locais:
 número (inteiro) {USADO COMO ÍNDICE PARA AS REPETIÇÕES}
 val_fat (inteiro) {VALOR CALCULADO POR MEIO DE
 MULTIPLICAÇÕES SUCESSIVAS}
início
 val_fat ← 1 {INICIALIZA ACUMULADOR DE PRODUTOS}
 {REPETIÇÕES NAS QUAIS O FATORIAL É CALCULADO}
 para número de N incr -1 até 1 faça
 val_fat ← val_fat * número
 {VALOR CALCULADO É DEVOLVIDO POR MEIO DO NOME DA FUNÇÃO}
 Fat ← val_fat
fim {Fatorial}
Caso o parâmetro passado seja 3, a função efetua o cálculo de 3! da seguinte maneira:
3! = 3 * 2 * 1
Analisando esse exemplo mais detalhadamente, observa-se que, como o fatorial de 2 é dado 
por 2 * 1, o cálculo do fatorial de 3 também pode ser expresso como:
3! = 3 * 2!
De forma análoga, tem-se que:
2! = 2 * 1!
1! = 1 * 0!
Por definição, o fatorial de zero é 1.
Edelweiss_15.indd 419Edelweiss_15.indd 419 12/03/14 09:0012/03/14 09:00
LABORATÓRIO DE PROGRAMAÇÃO 42 420 Algoritmos e Programação com Exemplos em Pascal e C
Assim, o cálculo do fatorial de um número inteiro N pode ser realizado com base na seguinte 
definição recursiva:
se N = 0 então fatorial(N) = 1
se N > 0 então fatorial(N) = N * fatorial(N-1)
A função recursiva Fatorial, a seguir, implementa essa definição. É uma função recursiva 
porque no seu código há uma chamada para ela mesma.
Função Fatorial: inteiro
{CALCULA O FATORIAL DE UM INTEIRO N, PASSADO COMO PARÂMETRO, DE FORMA 
RECURSIVA}
 Parâmetro de entrada: N (inteiro)
início
 se N = 0
 então Fatorial ← 1
 senão Fatorial ← N * Fatorial (N-1)
fim {Fatorial}
15.3 implementação de subprogramas recursivos
Na função mostrada na seção anterior, a chamada à função Fatorial(N-1) é o que se de-
nomina chamada recursiva, ou seja, é uma chamada da função a si mesma. Conforme visto 
no Capítulo 9, o programa ou subprograma que faz uma chamada a outro subprograma fica 
com sua execução suspensa até que termine a execução do subprograma acionado. Quando 
isso acontece, a execução do programa ou subprograma que chamou é retomada a partir do 
ponto em que foi feita a chamada. O mesmo acontece quando a chamada for recursiva: o 
subprograma que faz uma chamada recursiva é suspenso e é iniciada uma nova execução do 
mesmo subprograma de forma totalmente independente. Caso o subprograma possua variá-
veis locais, aí incluídos os parâmetros passados por valor, são alocadas novas variáveis, que 
existirão somente durante essa nova execução. Somente quando o subprograma acionado na 
chamada recursiva terminar sua execução é que o anterior retoma sua execução.
A implementação de chamadas recursivas segue o mesmo mecanismo das chamadas a sub-
programas apresentado na Seção 9.2, mesmo quando o subprograma chamado é o mesmo 
que faz a chamada. A cada chamada recursiva, os recursos locais deverão ser preservados, 
desde o momento em que sua execução é interrompida até o momento em que seja possível 
retomar essa execução para tentar concluí-la, quando então esses recursos locais deverão 
novamente ficar disponíveis. A implementação é feita por meio de uma estrutura de pilha, 
em que vão sendo colocados os elementos locais das chamadas interrompidas, bem como os 
endereços dos pontos a partir de onde as execuções dos subprogramas devem ser retomadas 
para serem concluídas. À medida que as execuções vão sendo concluídas, os elementos locais 
vão sendo restaurados a partir da pilha.
Quando um subprograma é chamado sucessivas vezes por si mesmo, cada nova execução 
gera uma nova entrada na pilha para armazenar seus recursos locais. É muito comum, quan-
Edelweiss_15.indd 420Edelweiss_15.indd 420 12/03/14 09:0012/03/14 09:00
43 Funções e Recursividade UNIDADE 1Recursividade PARTE 3
Capítulo 15 Recursividade 421
do utilizada recursividade, que as chamadas recursivas sejam muito numerosas, ocasionando 
falta de espaço físico para armazenar os valores das chamadas na pilha de execução, o que, 
em algumas linguagens de programação, gera uma mensagem de “stack overflow” (trans-
bordamento da pilha) e a interrupção do processo de execução.
A Figura 15.1 ilustra a execução das chamadas recursivas feitas quando é utilizada uma cha-
mada Fatorial(3). A primeira chamada resulta em três chamadas recursivas. No momen-
to da execução da última, Fatorial(0), todas as anteriores estão suspensas, esperando o 
término daquela que a chamou (Figura 15.1a). Fatorial(0) é a primeira a terminar sua 
execução, devolvendo seu resultado (1) à anterior, Fatorial(1), sendo então liberado seu 
espaço de execução (Figura 15.1b). Ao término da execução de Fatorial(1), seu resultado 
(1) é passado à anterior e seu espaço de execução é liberado (Figura 15.1c). E assim sucessi-
vamente, até que o resultado da primeira chamada seja devolvido.
parada de chamadas recursivas. Nos subprogramas recursivos sempre deve haver uma con-
dição que leve ao término da execução do subprograma. Por exemplo, seja a função a seguir:
Função X: inteiro
 Parâmetro de entrada: N (inteiro)
início
 escrever(N)
==u=← X(N-1) {CHAMADA RECURSIVA}
fim
Fatorial(2)
2*Fatorial(1)
Fatorial(1)
)c()b()a(
1*Fatorial(0)
Fatorial(0)
Fatorial(3)
3*Fatorial(2)
Fatorial(2)
2*Fatorial(1)
Fatorial(1)
1*Fatorial(0)
Fatorial(3)
3*Fatorial(2)
Fatorial(2)
2*Fatorial(1)
Fatorial(3)
3*Fatorial(2)
Fatorial(0)
Fatorial(1)
Fatorial N
Fatorial 
Fatorial 
Fatorial 
Fatorial 
Fatorial 
Fatorial 
Fatorial 
Fatorial 
figura 15.1 Chamadas recursivas no cálculo de Fatorial (3).
Edelweiss_15.indd 421 12/03/14 09:00
LABORATÓRIO DE PROGRAMAÇÃO 44 422 Algoritmos e Programação com Exemplos em Pascal e C
Observa-se que a chamada recursiva será sempre executada, fazendo que a execução nunca 
termine! A chamada recursiva sempre deve ser condicional, garantindo a finalização da exe-
cução do subprograma. No exemplo da função Fatorial, a parada das chamadas recursivas 
se dará quando o parâmetro recebido for zero.
Além de atrelar a chamada recursiva a alguma condição, todo cuidado deve ser tomado para 
que essa condição realmente se torne verdadeira em algum momento, uma vez que ela pode 
envolver valores lidos ou calculados durante o processamento. Por exemplo, as chamadas 
recursivas da função K, a seguir, jamais cessarão se a função receber, na primeira chamada, 
um parâmetro menor do que 1:
Função K: inteiro
 Parâmetro de entrada: N (inteiro)
início
 se N = 1 {CONDIÇÃO DE TÉRMINO DAS CHAMADAS RECURSIVAS}
 então K ← 1 {DEVOLVE O VALOR 1}
 senão K ← K(N-1)
fim
solução recursiva e iterativa. Duas formas foram utilizadas para solucionar o problema 
do fatorial neste livro: inicialmente, foi dada a solução utilizando um comando iterativo e, em 
seguida, a solução recursiva. É importante lembrar que todo problema passível de solução re-
cursiva pode ser resolvido também de forma iterativa, mesmo que os problemas apresentem 
claramente uma estrutura recursiva.
15.4 recursividade indireta
Existem casos em que dois subprogramas fazem chamadas recíprocas, ou seja, cada um faz 
alguma chamada ao outro – por exemplo, supondo dois subprogramas A e B, A faz uma 
chamada a B que, por sua vez, faz uma chamada a A. Essa situação caracteriza uma recursi-
vidade indireta.
Sempre que dois subprogramas apresentarem recursividade indireta, pelo menos em um de-
les a chamada ao outro deve ser condicionada a alguma situação para garantir que, em 
algum momento, as chamadas recíprocas terminem.
A declaração de um subprograma deve sempre ser feita antes de sua utilização em algum 
comando, para que o compilador consiga identificar o significado do nome do subprograma 
e para que possa ser feita a verificação dos parâmetros atuais, que devem corresponder, em 
quantidade e tipos, aos parâmetros formais. No caso citado, em que dois subprogramas se 
chamam mutuamente, não é possível declarar os dois antes de serem utilizados. Algumas 
linguagens de programação permitem informar ao compilador que a declaração de um de-
terminado subprograma será feita mais adiante, permitindo dessa maneira sua utilização 
antes da declaração. Para isso, definem somente o nome do subprograma e seus parâmetros 
Edelweiss_15.indd 422Edelweiss_15.indd 422 12/03/14 09:0012/03/14 09:00
45 Funções e Recursividade UNIDADE 1 Recursividade PARTE 3
Capítulo 15 Recursividade 423
formais (nome e tipo). Na pseudolinguagem utilizada nesse texto, a sintaxe dessa declaração 
é:
Declaração adiante : <cabeçalho da declaração do procedimento_1>
<declaração do procedimento_2>
<declaração do procedimento_1>
O exemplo a seguir ilustra a chamada recíproca de dois procedimentos. No programa princi-
pal, é lido um valor inteiro e, em seguida, chamado o procedimento A. Os dois procedimentos 
passam a se chamar mutuamente, até que o procedimento A receba um valor superior a 100 
como parâmetro, que é a condição de parada das chamadas recursivas. A Figura 15.2 ilustra a 
sequência de chamadas recursivas no caso do valor lido para a primeira chamada de A ser 97.
Subprograma A
{finaliza}
Subprograma B
execute A(101)
Subprograma A
execute B(99,2)
Subprograma B
execute A(99)
Subprograma A
execute B(97,2)
Programa principal
execute A(97)
figura 15.2 Exemplo de recursividade indireta.
Edelweiss_15.indd 423Edelweiss_15.indd 423 12/03/14 09:0012/03/14 09:00
LABORATÓRIO DE PROGRAMAÇÃO 46 424 Algoritmos e Programação com Exemplos em Pascal e C
Algoritmo ExemploMutuo
{-------------------------------------------------------------}
Declaração adiante: Procedimento B (ref v1:inteiro; v2:inteiro)
{-------------------------------------------------------------}
Procedimento A (ref x: inteiro)
início
 se x ≤ 100
 então executar B(x, 2){CHAMADA CONDICIONAL AO PROCEDIMENTO B}
fim {A}
{-------------------------------------------------------------}
Procedimento B (ref v1: inteiro; v2: inteiro)
início
 v1 ← v1 + v2
 executar A(v1) {CHAMADA AO PROCEDIMENTO A}
fim {B}
{-------------------------------------------------------------}
{DECLARAÇÃO DE VARIÁVEL GLOBAL}
 Variável: valor (inteiro)
{-------------------------------------------------------------}
início {PROGRAMA PRINCIPAL}
 ler (valor)
 executar A (valor)
 escrever (valor)
fim {PROGRAMA PRINCIPAL}
15.5 vantagens e desvantagens da recursividade
O uso da recursividade apresenta algumas vantagens:
 ■ um código recursivo é a forma mais simples e direta de solução de problemas que têm 
uma definição recursiva;
 ■ é especialmente conveniente para acessar estruturas de dados implicitamente recursivas, 
como árvores;
 ■ quando bem utilizado, facilita a compreensão da lógica do subprograma;
 ■ o código recursivo tende a ser mais enxuto que o código não recursivo.
Entretanto, sua utilização também traz algumas desvantagens:
 ■ necessidade de memória extra durante a execução das chamadas recursivas para armaze-
namento dos itens locais às chamadas e respectivos endereços de retorno;
 ■ aumento do tempo de processamento, devido ao acionamento das diversas chamadas 
recursivas;
 ■ é inviável em problemas que exijam um número muito elevado de chamadas e, consequen-
temente, um grande espaço de armazenamento para a pilha de execução.
Edelweiss_15.indd 424Edelweiss_15.indd 424 12/03/14 09:0012/03/14 09:00
47 Funções e Recursividade UNIDADE 1 RecursividadePARTE 3
Capítulo 15 Recursividade 425
Observar, portanto, que a utilização de recursividade nem sempre é apropriada, devendo 
sempre ser avaliada sua real utilidade.
15.6 exercícios de fixação
exercício 15.1 A posição em que é feita uma chamada recursiva influi diretamente nas ações 
executadas. Por exemplo, os valores apresentados são substancialmente alterados quando a 
saída de valores for feita antes ou depois de uma chamada recursiva. Neste exercício são 
mostradas duas versões para um procedimento, mudando somente o momento em que é 
mostrada uma informação.
O procedimento MostraVersão1 recebe dois parâmetros inteiros, i e n. O parâmetro i é 
alterado e o parâmetro n nunca sofre alteração.
Procedimento MostraVersão1
{CÓDIGO RECURSIVO COM COMANDO APÓS A CHAMADA}
 Parâmetros de entrada:
 i, n (inteiro)
início
 se i ≥ n
 então início
 escrever('Chamadas recursivas concluídas');
 escrever(i)
 fim
 senão início
 executar MostraVersão1 (i+2, n)
 escrever (i)
 fim
fim {MostraVersão1}
Nessa versão, o valor de i está sendo apresentado na fase do desempilhamento, ou seja, 
após a finalização da execução da chamada recursiva. Caso os parâmetros recebidos valham 
respectivamente 2 e 8, a execução desse código produzirá o seguinte resultado na tela:
Chamadas recursivas concluídas
8
6
4
2
Observar agora o código do procedimento MostraVersão2, que recebe os mesmos dois pa-
râmetros inteiros, i e n, e em que, igualmente, o parâmetro i é alterado e o parâmetro n 
nunca sofre alteração:
Procedimento MostraVersão2
{CÓDIGO RECURSIVO COM COMANDO ANTES DA CHAMADA}
Edelweiss_15.indd 425Edelweiss_15.indd 425 12/03/14 09:0012/03/14 09:00
LABORATÓRIO DE PROGRAMAÇÃO 48
ENCERRA AQUI O TRECHO DO LIVRO DISPONIBILIZADO 
PELA SAGAH PARA ESTA PARTE DA UNIDADE.
PREZADO ESTUDANTE
unidade 
1
O conteúdo deste livro é 
disponibilizado por SAGAH.
Parte 4
Recursividade em C
LABORATÓRIO DE PROGRAMAÇÃO 50
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. 
51 Funções e Recursividade UNIDADE 1 Recursividade em C PARTE 4
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
LABORATÓRIO DE PROGRAMAÇÃO 52
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
53 Funções e Recursividade UNIDADE 1 Recursividade em C PARTE 4
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 sintaxeda 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
LABORATÓRIO DE PROGRAMAÇÃO 54
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 retornar seus 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
55 Funções e Recursividade UNIDADE 1 Recursividade em C PARTE 4
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
LABORATÓRIO DE PROGRAMAÇÃO 56
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
57 Funções e Recursividade UNIDADE 1 Recursividade em C PARTE 4
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
LABORATÓRIO DE PROGRAMAÇÃO 58
A técnica de recursividade pode substituir o uso de estruturas de repetição, 
tornando o código mais simples e elegante do ponto