Funcoes_e_Recursividade

Prévia do material em texto

funções, recursividade
Implementação de funções em C
Blocos de código que realizam ações discretas que o programa deve executar como parte de 
uma ação global para solução de um problema.
Três pontos importantes a respeito de funções em C:
 
Estrutura de um código fonte em C no que esse refere ao uso de funções (existe a 
alternativa clássica)
diretivas de pre-processamento: 
 includes, defines
definições globais: 
 estruturas, uniões, enumerações, campos de bits,... 
protótipos das funções.
declarações de variáveis globais (evite-as).
void main(int argc, char *argv[ ])
{ ............
chamadas a funções
.........
}
blocos de código das funções
1) Protótipo de uma função: 
Não é elemento do C original, tendo sido introduzido pelo padrão ANSI. Consiste em 
uma cópia (finalizada com ‘;’) do cabeçalho da função, sendo necessário em todos os 
arquivos onde houver chamada à respectiva. Serve para uma melhor verificação de 
tipos por parte do compilador. 
Formato geral: tipo_de_retorno nome_da_função (lista de parâmetros);
Onde lista de parâmetros corresponde a uma seqüência de declarações de variáveis: 
tipo var1, tipo var2,...., tipo var n
• O nome_da_função deve ser sugestivo;
• As variáveis declaradas na lista de parâmetros são locais ao corpo da função; 
• Uma função que não retorna nada explicitamente (return) deve ser do tipo void;
• O tipo_de_retorno default é tipo inteiro;
• Para especificar rigorosamente que uma função que não possui lista de parâmetros, 
escreva void no campo reservado a essa lista no protótipo;
• Apesar de pouco utilizado é possível declarar-se um protótipo com uma lista 
variável de parâmetros, como ocorre com o protótipo da função printf, onde as 
reticências significam uma lista variável de parâmetros:
 int printf(const char *format[, argument, ...]);
1
funções, recursividade
2) Definição de uma função
Divide-se em:
 cabeçalho: igual ao protótipo (sem o ponto e vírgula final);
 corpo ou bloco de código: efetivamente o que a função executa quando 
chamada, consiste seqüências de linhas de código não vista pelo resto do 
programa; 
Formato geral:
tipo_de_retorno nome_da_função (lista de parâmetros)
{ 
/* bloco de código */ 
}
ATENÇÃO
• Não é permitido em C, prototipar uma função dentro de outra;
• é possível (mas não recomendável !) utilizar no cabeçalho, declarações com
 identificadores diferentes dos exibidos no protótipo;
• O bloco de código de uma função deve ser o menor possível;
 Quando uma função é chamada, sua execução começa no início do seu corpo e 
termina no final deste ou quando for encontrada o comando return; . 
• O comando return pode também prover o retorno de valor (do mesmo tipo 
declarado para a função) para o ponto onde a função foi chamada, nesse caso sua 
sintaxe será: return (expressão); 
• O valor retornado por return será descartado se não for atribuído a nenhuma 
variável no ponto onde a função foi chamada.
• Uma função pode retornar um endereço de memória, para tanto basta ser declarada 
como um ponteiro para o tipo de retorno
int * func(.....);
.....
void main(void)
{ ........
}
int * func(.....)
{ int *p;
 .....
 return p;
}
3) Chamada a uma função
Consiste na invocação do nome da função com passagem dos parâmetros reais para os 
parâmetros formais declarados no protótipo da função. 
2
funções, recursividade
• Em geral os parâmetros reais, sua quantidade e tipo deve ser compatíveis com os 
parâmetros especificados no protótipo e cabeçalho da função. Além disso há uma 
correspondência entre a ordem dos parâmetros na chamada e a ordem em que foram 
formalmente declarados no protótipo da função.
Passagem de parâmetros reais para “dentro” da função:
Há duas modalidades de passagem de valores para funções (possíveis de serem 
combinadas):
Passagem por valor: nesse método há uma cópia do valor dos parâmetros reais nos 
parâmetros formais da função. Como conseqüência: Alterações feitas nos parâmetros 
formais da função não têm efeito sobre as variáveis utilizadas para chamar a função.
.......
main(void)
{ int x = 10;
 ......
 funcao(int x);
 printf(“x = %i”, x); /* exibe x = 10 */
}
...
void funcao(int x)
{ x= 202;
}
 A declaração de X dentro da função está no 
escopo local à função. 
Durante a chamada, o parâmetro X local à 
função recebe o valor de outra variável X 
externa ao escopo da função.
Alterações feitas na variável X do escopo 
interno à função não afetarão a variável X 
do escopo externo 
 Passagem por referência: há uma cópia do endereço de cada parâmetro real no 
respectivo parâmetro formal. Dessa forma o endereço pode ser usado para acesso 
indireto às variáveis utilizadas na chamada, permitindo alterações sobre estas.
3
funções, recursividade
Ponteiros para funções
Maneira mais flexível para chamar funções através do endereço de suas instruções 
na memória. Sintaxe: tipo_da_função (* nome_ponteiro_para_funcao) ( );
Exemplo: int (* ptr) ( );
não confunda a declaração acima com int *ptr (intx); que corresponde a uma 
declaração de função chamada ptr que devolve ponteiro para inteiro.
void check (char *a, char *b, int (* cmp)() );
int numcmp(char *a, char *b);
main(void)
{ int (* p )( ); /* ponteiro para uma função que retorna inteiro */
 char s1[M], s2[N];
 puts("entre com a primeira string");
 gets(s1);
 puts("entre com a segunda string");
 gets(s2);
 p = strcmp;
 check(s1,s2,p);
 getche();
 return 0;
}
void check (char *a, char *b, int (* cmp)( ) )
{ printf(" As cadeias sao: \n\n");
 if(! (*cmp)(a,b))
 puts("iguais");
 else
 puts("diferentes");
}
4
funções, recursividade
Recursividade ou “dividir para conquistar”
Diz-se que um problema é recursivo (recorrente) se ele pode ser definido em termos dele 
mesmo. 
Em termos de implementação computacional uma solução recursiva é aquela onde a função 
chama a si própria, de forma que a cada chamada a nova execução (da função) lida com 
casos cada vez mais simples do problema original. Portanto, para haver solução recursiva 
deve existir uma determinada instância do problema com solução imediata trivial que 
finalizará as chamadas recursivas à função. 
As definições recursivas são compostas de duas partes:
1. parada da recursividade, onde um ou mais casos simples possuem solução explícita
2. passo recursivo, onde outros casos são dados em termos dos casos anteriores.
Ex1: o produto de dois inteiros a e b positivos pode ser definido pela expressão recursiva
a * b = a se b = 1;
a * b = a* (b-1) + a se b >1.
Perceba que nessa expressão a operação produto é definida em termos dela mesma.
A função produto P(a,b) chama a si própria ciclicamente, e cada nova chamada trata uma 
instância mais simples do problema, até encontrar a solução do caso mais simples possível 
P(a,1) = 1. 
As chamadas recursivas são empilhadas, de forma que uma instância da função aguarda 
pelo retorno de valor que a próxima instância invocada (empilhada acima) deve devolver.
 
Vantagem da recursividade: propicia versões muito mais claras e simples, do que as 
soluções iterativas (com estruturas de repetição – for, while...). Apesar disso uma solução 
recursiva pode ser mais lenta que sua equivalente iterativa, devido à necessidade do uso da 
pilha de recursão para guardar o contexto de execução entre as chamadas recursivas.
5
funções, recursividade
Ex2: soma dos n naturais para n >= 1
Definição: soma(1) = 1
 soma(n) = soma(n-1) + n
int soma(int n)
{ if (n <= 1)
return(1);
 else
return(soma(n-1) + n);
}
Uma pilha de execução para a chamada soma(4):
6
funções, recursividade
Ex3: cálculo do mdc
Definição: 
mdc(x,y) = y; se x >= y e x mod y = 0 (resto da divisão de x por y) 
mdc(x,y) = mdc(y,x)
 mdc(x,y) = mdc(y,x mod y) 
mdc(int x,y)
{ if(x%y = = 0 && x >= y)return(y);
 else
if(x<y)
return(mdc(y,x));
else
return(mdc(y,(x%y)));
}
Ex4: Seqüência de Fibonacci. 
Seqüência de números f0, f1, f2, f3, f4, ..., fi, ..., fm
Onde: f0 = 0, f1 = 1 
 e fi = fi-1 + fi-2 , para i ≥ 2.
Ex: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.... 
f0 f1 f2 f3 f4 f5 f6 f7 ...
0 1 1 2 3 5 8 13 ...
Considerando o parâmetro n como o índice do número de fibonacci, dentro da 
seqüência. A seguinte função retorna o fn-ésimo número de Fibonacci:
unsigned long int fib(int n)
{ if (n ≤ 1)
 return n;
 else
 return (fib(n-1) + fib(n-2));
}
7
funções, recursividade
Árvore de execução para solução recursiva de fib(4):
Solução iterativa para o número de Fibonacci:
unsigned long int fib_i(int n)
{ unsigned long int a,b,x,i;
 if (n <= 1) return n;
 a = 0;
 b = 1;
 for( i = 2; i <= n; i ++)
 { x = a;
 a = b;
 b = x + a; 
 }
 return b;
} 
8
funções, recursividade
Para comparar os tempos de execução da solução recursiva em relação à iterativa. 
Execute o seguinte código:
#include “time.h”
........
main( )
{ int n;
 clock_t start, end;
 printf(“entre com n: “);
 scanf(“%i”, &n);
 start = clock( );
 printf(“Recursivo, f%i = = %li\n”, n,fib(n)); 
 end = clock( );
 printf(“tempo do calculo recursivo: %f\n\n”, (end-start)/CLK_TCK); 
 
 start = clock( );
 printf(“Iterativo, f%i = = %li\n”,n, fib_i(n)); 
 end = clock( );
 printf(“tempo do calculo iterativo: %f\n\n”, (end-start)/CLK_TCK);
 getche( );
}
9
funções, recursividade
Ex5: torres de Hanói
O problema das Torres de Hanói: dados três pinos (a, b, c) e cinco discos de diâmetros 
diferentes, conforme figura abaixo. O objetivo é mover os cinco discos para C 
utilizando B como auxiliar e garantindo que em C o maior disco ficará abaixo. 
Apenas o disco do topo poderá ser movido, além disso um disco maior nunca poderá ser 
colocado sobre um menor.
chamada :
hanoi(5, ‘A’, ‘B’,’C’);
hanoi(int n, char x, char y, char z)
{ if (n < 1)
 printf( “não há discos para remover ! \n”);
 else
 if(n = = 1)
 printf(“move disco da torre %c para a torre %c\n”, x,y);
 else
{ hanoi(n-1, x, z, y);
 printf(“move disco da torre %c para a torre %c\n”, x,y);
 hanoi(n-1, z, y, x);
 }
}
10
funções, recursividade
EX6 : Busca binária
Método de busca sobre uma coleção ordenada de dados. Simula a maneira como 
pesquisamos informações em um catálogo telefônico: abrimos em uma página 
intermediária e tentamos identificar ali o número procurado, caso ele não seja encontrado, 
procuramos em uma das outras metades do catalogo em função do número procurado e dos 
valores exibidos na posição atual do catalogo. Este procedimento se repete até 
localizarmos o número procurado ou deduzirmos que ele não se encontra catalogado.
BUSCA BINÁRIA RECURSIVA
/* Aqui, retorna a posição do registro procurado ou –1 (insucesso). O vetor A é a coleção 
ordenada de dados. Onde busca-se o elemento x (campo chave), low e high são os limites 
do intervalo de busca, que aqui funcionarão como índices do vetor */
int BuscaBin(int A[ ],int x,int low, int high) 
{
 int mid, ret; /*mid corresponderá sempre à posição de pesquisa entre low e high */
 
 if (low > high) /* se chegar nesse ponto, o item x não existe na coleção */
return(-1); 
 mid = (low+high)/2; /*cálculo de mid: aproximadamente metade da coleção considerada */
 if(x == A[mid]) /*sucesso na pesquisa item encontrado na posição mid. Fim da busca */
return(mid);
 else /* como a coleção é ordenada, o registro procurado deve encontrar-se na partição à 
esquerda ou naquela à direita de mid */
{ if(x < A[mid])
ret = BuscaBin(A, x,low,mid-1); /* continua busca na primeira partição, precisa 
ajustar high para mid-1 */
 else
 ret = BuscaBin(A,x,mid+1,high); /* continua busca na segunda partição, precisa 
ajustar low para mid+1 */
 return(ret);
}
}
11
funções, recursividade
Dado o vetor A ordenado conforme segue: [0,2,5,7,8]
 Simulação:
BuscaBin(A,8,0,4)
....
mid = 2;
if(8 < A[2])
..........
else
ret = BuscaBin(A,8,mid + 1,4)
Return (ret);
BUSCA BINÁRIA ITERATIVA (sem recursão)
int BuscaBin(int A[ ],int x,int low, int high) 
{ int mid;
 while(low <= high)
{ mid = (low+high)/2; 
 if(x<A[mid])
high = mid-1;
 else 
if(x>A[mid])
low = mid+1;
 else
return(mid);
}
 return(-1);
}
12
ret = BuscaBin(A,8,3,4)
mid = 3;
if(8<A[3])
...
else
ret = BuscaBin(A,8,3+1,4)
 
 Return(ret);
BuscaBin(A,8,4,4)
mid = 4;
...
if(8==A[4])
return(mid);
	Implementação de funções em C
	2) Definição de uma função
	ATENÇÃO
	Recursividade ou “dividir para conquistar”
	Ex3: cálculo do mdc
	EX6 : Busca binária