Funções e Recursividade em C

Prévia do material em texto

1
Algoritmos e Técnicas 
de Programação
Funções e recursividade
Unidade de Ensino: Funções e recursividade
Competência da Unidade: Apresentar métodos para tornar o processamento de 
programas em C mais otimizados.
Resumo: São apresentados métodos para tornar os programas otimizados como 
modularização do programa com a criação de funções e procedimentos e o método de 
recursividade.
Palavras-chave: funções, procedimentos, sub-rotinas, recursividade.
Título da Teleaula: Funções e recursividade
Teleaula nº: 04
É o emprego de técnicas
para seleção das melhores 
alternativas, com o 
propósito de alcançar os 
objetivos.
Fonte: https://cutt.ly/lfXXis4
Otimização Reflita
• Computadores, smartphones, tablets precisam de um sistema
que faça o gerenciamento dos recursos sistema operacional 
(SO); 
• SOs 4 destacam-se no mercado o Android, o iOS, o Windows
e o Linux. 
• Linux o núcleo (Kernel) do código fonte possui 
mais de 20 milhões de linhas de comandos. 
Como os programadores 
conseguem manter tudo isso 
organizado? 
Como conseguem encontrar 
certas funcionalidades?
Fonte: https://cutt.ly/EfFOiyK
Sub-rotinas
• Em várias ocasiões utilizamos algumas funções e procedimentos
para o auxílio operacional, além do uso de arquivos de cabeçalho 
para acesso a diversos recursos; 
• Desenvolvimento e manutenção de um sistema só é possível de 
ser realizado porque as funcionalidades são 
divididas em “blocos” funções ou 
procedimentos; 
2
• Software deve ser construído seguindo o princípio de 
organização cada funcionalidade deve ser colocada em um 
“local” com uma respectiva identificação, para que o requisitante 
possa encontrar.
Manutenção de 
softwares!
Fonte: https://cutt.ly/EfFOiyK
Reutilização de 
código!
Procedimentos e 
funções
Escopo e 
passagem de 
parâmetros 
Recursividade
Nossa teleaula
Dividir para 
conquistar
Dividir para conquistar – Modularização 
• Criar programas com blocos de funcionalidades sub-rotinas
bloco de programa que pode realizar operações computacionais de 
entrada processamento e saída;
• Abstração abstrair um algoritmo significa considerar 
isoladamente um ou mais elementos de seu todo;
• Solucionar pequenos problemas, em vez de um 
grande problema, é supostamente mais fácil!
Programa Inicial
Subproblema 
1
Subproblema 
2
Subproblema 
N
Solução 1 Solução 2 Solução N
Solução Completa
⋯
Vantagens
• Possibilidade de dividir um problema complexo em partes menores;
• Possibilidade de criar rotinas de trechos de programa que se 
repetem ao longo do programa, proporcionando certo grau de 
economia de trabalho e reaproveitamento de código.
Método do 
refinamento sucessivo!
Fonte: https://cutt.ly/EfFOiyK
3
Três passos
(1) Dividir quebrar um problema em subproblemas menores; 
(2) Conquistar usar uma sequência de instruções separada para 
resolver cada subproblema;
(3) Combinar juntar a solução de cada subproblema para alcançar a 
solução completa do problema original.
Observação
• Há programadores que estabelecem o número máximo de linhas
de programa que uma sub-rotina deve possuir; 
• Se o número de linhas ultrapassa o limite preestabelecido a 
rotina em desenvolvimento é dividida em outra sub-rotina.
Sub-rotinas
• As bibliotecas das linguagens de programação disponibilizam sub-
rotinas que executam certas operações raiz quadrada, potência, 
geração de um número aleatório,... o que precisamos é apenas 
solicitar a execução dessas sub-rotinas dentro do nosso código; 
• As sub-rotinas podem ser do tipo função ou 
procedimento.
Função – function
• Utilizada para a realização de ações de processamento matemático 
e/ou lógico;
• Sempre retorna alguma resposta da ação que processou 
geralmente é necessário uma variável para receber a resposta da 
função raiz = sqrt(x);
• Um dos grandes benefícios não precisar copiar o código todas 
as vezes que precisar executar a mesma operação;
• Exemplo: caso precisássemos descobrir a raiz quadrada de 10 
números, bastaria chamar a função que calcula a raiz quadrada 
10 vezes.
Procedimento - procedure
• Normalmente utilizado para a realização de ações relacionadas a 
entrada e saída; 
• Pode ter seu uso direcionado a ações de processamento não é 
muito recomendado!
• Difere das funções apenas por não retornar 
resultado;
• Exemplo: procedimento que envia e-mail 
precisa retornar resultado? 
4
• Já utilizamos muitos procedimentos:
• Ler o valor digitado por um usuário procedimento leia (scanf);
• Mostrar um texto na tela procedimento escreva (printf). Métodos top-
down e bottom-
up
Métodos top-down e bottom-up
• Procedimentos de trabalho que podem facilitar a construção de 
programas de computador;
• TOP-DOWN de cima para baixo descreve de forma resumida 
as ações de um programa não se preocupa com detalhes 
específicos;
• BOTTOM-UP de baixo para cima descreve de 
forma detalhada as operações de um programa 
com o objetivo de apresentá-lo como um todo.
Método top-down
• Antes de iniciar a construção de um programa devemos ter em 
mente as tarefas principais que o programa deve executar não é 
necessário saber como vão funcionar, somente quantas são;
• Conhecidas todas as tarefas a serem executadas devemos 
especificar como deve ser o programa principal 
vai controlar todas as outras tarefas distribuídas 
em suas sub-rotinas;
Definido o programa principal 
inicia-se o processo de 
detalhamento estrutural para 
cada sub-rotina.
Fonte: https://cutt.ly/EfFOiyK
Método bottom-up
• O programa é escrito a partir de suas sub-rotinas inferiores;
• Deixa-se por último as rotinas de nível mais alto;
• O programa principal é o último a ser codificado.
5
Observações 
• Projeto físico de um programa deve ser baseado no método 
top-down;
• Desenvolvimento do programa em si (projeto lógico) deve ser 
feito com o método bottom-up.
Sub-rotinas na 
linguagem C
Você utilizou funções e 
procedimentos desde a primeira 
implementação, mesmo sem 
conhecê-las, pois é uma exigência 
da linguagem.
Fonte: https://cutt.ly/EfFOiyK
Sub-rotinas
• “Conjunto de 
instruções 
que efetuam 
uma tarefa 
específica”!
Sub-rotinas na linguagem C
• Uma sub-rotina pode assumir 3 tipos de comportamentos:
• Procedimento é executada e não retorna valor ao módulo de 
programa que fez a sua chamada;
• Função é capaz de retornar apenas um valor ao módulo do 
programa que fez a sua chamada;
• Procedimento ou Função trabalha com a
passagem de parâmetros por valor e por 
referência.
Sintaxe
<tipo> <nome> ([<tipo de parâmetros>][<parâmetros>]);
{
//variáveis locais;
//instruções;
<return> <valor do retorno>;
}
• <tipo> obrigatório. 
• tipo de valor que será retornado int, float ou double, char, 
etc; 
• quando não retorna nenhum valor void chamado de 
procedimento;
• <nome> obrigatório; 
• Identificará a função não pode ter acento, 
caractere especial e ser nome composto;
6
• <parênteses depois do nome> obrigatório; 
• main(), printf(), somar(), etc;
• <parâmetros> opcional; 
• <variáveis> lista de variáveis locais (opcional);
• <instruções> obrigatório só faz sentido criar 
uma função se ela tiver um conjunto de 
comandos para realizar;
• <return> <parâmetro> 
• void não precisa ser usado; 
• quando não for void obrigatório; 
• valor a ser retornado tem que ser compatível com o tipo de 
retorno, senão o problema dará um erro de compilação em 
algumas linguagens, em outras retornará um 
valor errôneo. 
Exemplo 01 – Soma entre dois números int resultado = 0;
resultado = somar();
printf("O resultado da 
funcao e = %d",resultado);
return 0;
}
#include<stdio.h>
int somar()
{
int x = 0;
x = 2 + 3;
return x;
}
int main()
{
Exemplo 02 – Soma entre dois números printf("O resultado da 
funcao e = %d",resultado);
return 0;
}
#include<stdio.h>
int somar()
{
return 2+3;
}
int main()
{
int resultado = 0;
resultado = somar();
Duas linhas e uma 
variável a menos!
7
Fatorial de um 
número inteiro
Atividade
• Programa calcular o fatorial de um número através de um 
procedimento,utilizando a estrutura de repetição determinística 
(for).
• Entrada: numero inteiro positivo;
• Processamento: cálculo do fatorial;
• Saída: valor do fatorial.
#include <stdio.h>
#include <math.h>
//criando um procedimento
fatorial(int n)
{
//declarando e inicializando variáveis locais
int j=1;
int fat=1;
j=n;
if (n == 0)
{
printf(“0! = 1!”);
}
else
{
printf("\n %d",n);
printf("!= ");
//loop for
for (fat=1; j>0; j--)
{
fat=fat*j;
printf("%d",j);
printf(".");
}
printf(" = %d",fat);
printf("\n\n");
}
}
//iniciando o programa principal em C
int main (void) 
{
//declarando as variáveis
int n=0;
//obtendo e armazenando dados
printf("\n Informe o número inteiro que deseja 
obter o fatorial: ");
scanf("%d",&n);
8
//chamando o procedimento
fatorial(n);
//finalizando o programa
printf("\n Pressione a tecla enter para finalizar o 
programa!");
return 0;
}
Fatorial de números grandes
• O que acontece se eu digitar um valor de n muito grande?
• Tente calcular o fatorial do número 100 na sua calculadora?
• O que aconteceu?
• Math error? O que é isto?
Fonte: https://bit.ly/3aLma1D
• Esse fenômeno é chamado de overflow e acontece quando a 
máquina digital não consegue representar o número porque ele é 
muito grande;
• Devido a esse problema, é interessante declarar a variável n e o 
tipo da função fat(n) como float:
float fat(n)
float n;
Bibliotecas de 
funções e 
procedimentos na 
linguagem C
É possível ao 
programador criar 
uma biblioteca?
Fonte: https://cutt.ly/EfFOiyK Fonte: https://bit.ly/3aLma1D
Bibliotecas de funções e procedimentos predefinidas
• Coleção de funções/procedimentos, constantes, estrutura de 
dados, etc. que ficam disponíveis em arquivos específicos;
• Uma biblioteca pode ser 
• interna acompanha o compilador da linguagem #include; 
• externa desenvolvida pelo programador
#include ” ”; 
9
Biblioteca Função/Procedimento Descrição 
<stdio.h>
printf() imprime na tela
scanf() lê um dado digitado
<math.h>
pow(base, potência) potenciação
sqrt(numero) raiz quadrada
sin(ângulo) seno
cos(ângulo) cosseno
22 funções matemáticas funções 
trigonométricas, hiperbólicas, exponenciais, 
logarítmicas, etc.
Biblioteca Descrição 
<stdbool.h> definição de tipo de dado booleano
<complex.h> manipulação de números complexos
<string.h> tratamento de cadeia de caracteres
Escopo de 
variáveis
Variáveis – Escopo e visibilidade
• Variáveis armazenam dados temporariamente na memória;
• O local onde esse recurso é definido no código de um programa 
determina seu escopo e sua visibilidade.
#include<stdio.h>
int testar()
{
int x = 10;
return x;
}
int main()
{
int x = 20;
printf("\n Valor de x na funcao main() = %d",x);
printf("\n Valor de x na funcao testar() = %d", 
testar());
return 0;
}
Temos duas variáveis 
chamadas “x”, isso 
acarretará em erro?
Fonte: https://cutt.ly/EfFOiyK
• As variáveis possuem o mesmo nome, mas estão definidas em 
lugares diferentes uma está dentro da função main() e outra 
dentro da testar();
• Cada função usa um espaço na memória de forma 
independente;
• Na memória as variáveis são localizadas pelo seu 
endereço mesmo sendo declaradas com o 
mesmo nome, seus endereços são distintos.
10
#include<stdio.h>
int testar()
{
int x = 10;
return x;
}
int main(){
int x = 20;
printf("\n Valor de x na funcao main() = %d",x);
printf("\n Valor de x na funcao testar() = 
%d",testar());
return 0;
}
20
10
Escopo de variáveis
• Duas categorias de variáveis: 
• Locais existem e são “enxergadas” somente dentro do corpo 
da função onde foram definidas;
• Globais visíveis por todas as funções do programa criadas 
fora da função após a inclusão das 
bibliotecas. 
Vamos criar as variáveis 
globais após a inclusão 
das bibliotecas.
Fonte: https://cutt.ly/EfFOiyK
#include<stdio.h>
int x = 10;
int testar()
{
return 2*x;
}
int main()
{
printf("\n Valor de x global = %d",x);
printf("\n Valor de x global alterado na 
função testar() = %d",testar());
return 0;
}
10
20
Variáveis locais versus variáveis globais
• Variáveis Globais permitem otimizar a alocação de memória
em vários casos o desenvolvedor não precisará criar variáveis locais.
• Cautela!!!
• Variáveis locais são criadas e destruídas ao fim da função. 
• Variáveis globais permanecem na memória 
durante todo o tempo de execução. 
Passagem de 
parâmetros
11
Passagem de parâmetros para funções
<tipo> <nome> ([<tipo de parâmetros>][<parâmetros>]);
{
//variáveis locais;
//instruções;
<return> <valor do retorno>;
}
Ao definir uma função, 
podemos estabelecer se ela 
receberá informações “de 
quem” a invocou.
Fonte: https://cutt.ly/EfFOiyK
Passagem por valor
• A função cria variáveis locais automaticamente para armazenar 
esses valores e, após a execução da função, essas variáveis são 
liberadas.
#include<stdio.h>
int somar(int a, int b)
{
return a + b;
}
int main() 
{
int result;
result = somar(10,15);
Função somar() definida para receber
dois valores inteiros. Internamente serão 
criadas as variáveis “a” e “b” 
para guardar os valores 
até o final da função.
printf(“\n Resultado da soma =%d”,result);
return 0;
}
Passagem por referência
• Ligada aos conceitos de ponteiro e endereço de memória; 
• Função definida de modo a receber certos parâmetros não
será criada uma cópia dos argumentos será passado o endereço 
da variável e função trabalhará diretamente com os valores ali 
armazenados.
• Sintaxe usa-se os operadores * e &; 
• Parâmetros a serem recebidos declarados com *:
int testar(int* parametro1, int* parametro2)
• Parâmetros a serem passados na chamada da função declarados
com o &:
resultado = testar(&n1,&n2)
12
Funções 
recursivas
Funções recursivas
• Categoria especial função que chama a si própria;
• Sintaxe não difere das funções gerais deverá ter um tipo de 
retorno o nome da função, os parênteses e os parâmetros
quando necessário;
• Diferença corpo da função a função será 
invocada dentro dela mesma. 
<tipo> função_recursiva()
{
//comandos
função_recursiva();
}
void main()
{
//comandos
função_recursiva();
//comando
}
• Embora a sintaxe da função recursiva seja similar às das não 
recursivas, o funcionamento de ambas é bastante distinto e o mau
uso dessa técnica pode acarretar em uso indevido de memória, 
muitas vezes chegando a travar a aplicação e o sistema. 
Pontos de atenção
(1) A função recursiva chama a si própria até que um ponto de parada
seja estabelecido; 
• Ponto de parada uma estrutura condicional ou um valor 
informado pelo usuário;
(2) Uma função possui seu corpo de variáveis e 
de comandos alocados na memória de trabalho; 
• Para cada chamada da função novos espaços 
são destinados a execução do programa;
(3) As variáveis criadas em cada instância da função na memória são 
independentes;
• Mesmo as variáveis tendo nomes iguais cada uma tem seu 
próprio endereço de memória e a alteração do valor em uma não 
afetará na outra.
13
Observação
• Toda função recursiva, obrigatoriamente, tem que ter uma 
instância com um caso que interromperá a chamada a novas 
instâncias; 
• Essa instância é chamada de caso base, pois representa o caso 
mais simples, que resultará na interrupção.
Exemplo
• Função recursiva que faz a somatória dos antecessores de um 
número inteiro positivo, informado pelo usuário;
• Se o usuário digitar 5, o programa deverá retornar o resultado da 
soma 5 + 4 + 3 + 2 + 1 + 0; 
• A função deverá somar até o valor zero esse é o 
critério de parada. 
#include<stdio.h>
int somar(int valor)
{
if(valor != 0)
return valor + somar(valor-1);
else
return valor;
}
int main() 
{
int n, resultado;
printf(“\n Digite um numero inteiro positivo : “);
scanf(“%d”,&n);
//primeira chamada da função com passagem de 
parâmetro
resultado = somar(n);
printf(“\n Resultado da soma = %d”,resultado);
return 0;
}
Exemplificando o funcionamento na memória de trabalho da função 
somar() n = 2:
Memória de trabalho
return 2 + ?; return 1 + ?; return 0;
Instância1
somar(2)
Instância 2
somar(1)
Instância 3
somar(0)
main
013
14
Análise 
combinatória
Atividade
• Programa para ser utilizado em exercícios sobre Análise 
Combinatória deve calcular: fatorial, permutação simples, 
arranjo simples e combinação simples com a utilização de funções.
𝑃 = 𝑛!
𝐴 , =
𝑛!
𝑛 − 𝑝 !
𝐶 , =
!
! !
Programa
• Entrada: números 𝑛 e 𝑝; 
• Processamento: cálculo do fatorial, da permutação simples 𝑃 , do
arranjo simples 𝐴 , e da combinação simples 𝐶 , ;
• Saída: valores calculados para a permutação, para o arranjo e para 
a combinação.
#include <stdio.h>
#include <math.h>
//declarando as variáveis globais
int n, p;
//função para cálculo do fatorial
int fatorial(int n)
{
int fat,j;
fat=1;
if (n > 0)
{
//iniciando o loop for
for (fat = 1; j > 0; j--)
fat=fat*j;
return fat;
}
else
return 1;
}
15
//função para cálculo da permutação
int permutacao(int n)
{
return fatorial(n);
}
//função para cálculo do arranjo
int arranjo(int n, int p)
{
if (p > 1)
return n*arranjo(n – 1,p – 1);
else
return n;
}
//função para cálculo da combinação
int combinacao(int n, int p)
{
return arranjo(n,p) / fatorial(p);
}
//iniciando o programa principal em C
int main ()
{
//lendo e armazenando dados
printf("\n\n Digite o numero inteiro n: ");
scanf("%d”, &n); 
printf("\n Digite o numero inteiro p: ");
scanf(“%d”, &p); 
//chamando as funções e imprimindo resultados
printf("\n P(n) = %d",permutacao(n));
printf("\n A(n,p) = %d",arranjo(n,p));
printf("\n C(n,p) = %d",combinacao(n,p));
//finalizando o programa
printf("\n Pressione a tecla enter para finalizar o 
programa!");
return 0;
}
Recursividade e 
estruturas de 
repetição
16
• Uma das grandes dúvidas dos programadores é quando utilizar a 
recursividade em vez de uma estrutura de repetição. 
• Considere a função recursiva somar(). 
int somar(int valor)
{
if(valor != 0)
return valor + somar(valor-1);
else
return valor;
}
A recursividade poderia ser 
substituída por uma estrutura 
de repetição usando for? 
Fonte: https://bit.ly/3aLma1D
• A verdade é que poderia sim ser substituído por: 
for (x=0; x<=n; x++)
{
resultado = resultado + x;
}
• A técnica de recursividade pode substituir o uso de estruturas de
repetição, tornando o código mais elegante, do ponto de vista das 
boas práticas de programação; 
• Entretanto, funções recursivas podem consumir mais memória 
que as estruturas iterativas. 
Recapitulando
Dividir para conquistar
17
Método top-down Método bottom-up
Antes de iniciar a construção 
de um programa, deve-se ter 
em mente as tarefas 
principais que devem ser 
executadas 
O programa é escrito a 
partir de suas sub-rotinas
inferiores; deixa-se por 
último as rotinas de nível 
mais alto.
Conhecidas todas as tarefas 
a serem executadas, 
especifica-se como deve ser 
o programa principal.
O programa principal é o 
último a ser codificado.
Projeto físico de um 
programa.
Desenvolvimento do 
programa em si.
Função Procedimento
Utilizada para a realização de ações 
de processamento matemático 
e/ou lógico.
Normalmente utilizado para a 
realização de ações relacionadas a 
entrada e saída; 
Sempre retornam alguma resposta
da ação que processou.
Difere das funções apenas por não 
retornar resultado.
<tipo> <nome> ([<tipo de parâmetros>][<parâmetros>]);
{
//variáveis locais;
//instruções;
<return> <valor do retorno>;
}
Função Procedimento
<tipo>
Int, float, char...
<tipo>
void
<valor do retorno>
Obrigatório
<valor do retorno>
Não é necessário
São opcionais, 
mas, quando 
necessários, 
serão passados 
por valor.
Variáveis – Escopo e visibilidade
O local onde esse recurso é definido no código de um 
programa determina seu escopo e sua visibilidade.
Locais Globais
Existem e são “enxergadas” 
somente dentro do corpo 
da função onde foram 
definidas.
Visíveis por todas as 
funções do programa;
criadas fora da função, após
a inclusão das bibliotecas. 
São criadas e destruídas ao 
fim da função.
Permanecem na memória 
durante todo o tempo de 
execução. 
Função recursiva
<tipo> função_recursiva();
{
//variáveis locais;
//instruções;
função_recursiva();
}
A recursividade pode substituir o uso de estruturas de
repetição, tornando o código mais elegante.
Funções recursivas podem consumir mais memória que 
as estruturas iterativas. 
Algoritmos e Técnicas 
de Programação
Funções e recursividade