EDA 5

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
Recursividade
Remis Balaniuk
*
Introdução	
A linguagem C permite que um programador escreva sub-rotinas e funções que chamem a sí mesmas.
Tais rotinas são chamadas de recursivas 
*
Introdução
A recursividade é uma técnica de programação que se contrapõe à iteração (loops)
Programas iterativos normalmente podem ser implementados de forma recursiva e vice-versa.
Exemplo: a somatória de um vetor de inteiros.
*
Solução iterativa:
int soma(int a[],int n) {
	 int ret=0;
 for(int i=0;i<n;i++)
		ret+=a[i];
 return ret;
}
	
*
Solução recursiva
int soma(int a[],int size) {
		if(size==1) 
			return a[0];
 else
			return(a[size-1]+
 soma(a,size-1));
}
*
Solução recursiva
A solução recursiva normalmente quebra um problema em sub-problemas que podem ser resolvidos com a mesma rotina que esta sendo executada para resolver o problema maior.
*
Exemplo 
Fatorial 
5! = 5*4*3*2*1 = 120
Versão iterativa
fact(n) {
 int prod=1;
 for(int i=n;i>0;i--)
	 prod *=i;
 return prod;
}
*
Exemplo
Algoritmo recursivo para computar n! 
0! = 1
n!= n*(n-1)!
int fact(int n) {
	if(n==0)
		return(1);
	return(n* fact(n-1));
}
*
Recursividade 
O sistema operacional empilha as chamadas recursivas, criando contextos independentes.
Cada contexto tem suas próprias variáveis.
*
Recursividade
A implementação recursiva é uma técnica que não necessariamente resulta num programa mais rápido, mas pode simplificar a solução de certos problemas.
O uso da recursividade pressupõe duas condições: 	
A condição de parada, que retorna uma solução sem chamada recursiva.
Uma ou mais chamadas recursivas que definem a solução do problema como sendo a solução de um problema similar mais simples (ou mais próximo da condição de parada).
*
Recursividade
É imperativo que a rotina tenha uma condição de parada para não empilhar os contextos indefinidamente.
*
Exercício
Escreva rotinas que façam a multiplicação de dois números naturais de forma iterativa e recursiva (usando só a adição). 
*
Exercício 
Dada a seguinte rotina recursiva
func(int n) {
	 int x,y;
	 if(n<=1)
			return(1);
		 x = func(n-1);
 y = func(n-2);
 return(x+y);
}
o que essa rotina faz?
escreva um rotina iterativa que faça a mesma coisa. 
*
Algoritmo de Euclides
O algoritmo geral funciona em divisões sucessivas que reduzem o problema de encontrar o mdc de dois inteiros positivos ao mesmo problema com inteiros menores, até que um dos inteiros chegue a zero.
*
Algoritmo de Euclides
Começando por um exemplo:
Para encontrar o mdc(91,287) começamos dividindo o maior dos inteiros, 287, pelo menor, 287/91=91.3+14
Todo divisor de 91 e 287 tem de ser também um divisor de 287-91.3=14 
Também, todo divisor de 91 e 14 tem de ser um divisor de 287=91.3+14. 
Então, o mdc de 91 e 287 é o mesmo que o mdc de 91 e 14.
Isso significa que o problema de encontrar o mdc(91,287) foi reduzido ao problema de encontrar o mdc(91,14).
Em seguida dividimos 91 por 14 para obter: 91=14.6+7
Um vez que todo divisor comum de 91 e 14 também divide 91-14.6=7 e todo divisor comum de 14 e 7 divide 91, segue-se que mdc(91,14)=mdc(14,7)
Em seguida dividimos 14 por 7 para obter: 14=7.2
Um vez que 7 divide 14, conclue-se que mdc(14,7)=7 e uma vez que mdc(287,91)=mdc(91,14)=mdc(14,7) o problema original foi resolvido.
*
Algoritmo de Euclides
Versão iterativa
procedure mdc(a,b: inteiros positivos) {
	x:=a
 y:=b
 while y0
 begin
 r:= x mod y
 x:=y
 y:=r
 end 
 return x;
}
*
Exercício
Implemente a versão recursiva do algoritmo de Euclides.
*
Busca binária
A busca numa lista ordenada de valores é um dos problemas mais comuns em computação.
A busca mais simples é a sequencial, onde todas as posições da lista são visitadas uma a uma até encontrar o valor.
Essa busca é necessária se os valores não estão ordenados.
A busca sequencial obviamente não é otimizada e, na média, vai precisar de n/2 leituras chegar no dado procurado.
*
Busca binária
A busca binária divide a lista de busca ao meio e considera 3 possibilidades:
Se o valor central é o procurado, achou.
Se o valor central é maior que o valor procurado recomece a busca considerando somente a meia lista inferior. Se essa tiver tamanho 0 o elemento não existe.
Se o valor central é menor que o valor procurado recomece a busca considerando somente a meia lista superior. Se essa tiver tamanho 0 o elemento não existe.
Cada passo do algoritmo reduz o espaço de busca pela metade.
*
Busca binária em C
int binsrch(int a[], int x, int low, int high)
{
	int mid;
	if(low>high)
		return(-1);
 mid = (low+high) / 2;
	if(x==a[mid])
		return(mid);
	if(x<a[mid])
		return(binsrch(a,x,low,mid-1));
	return(binsrch(a,x,mid+1,high));
}
*
Busca binária em C
exemplo:
a=[1,3,6,8,11,24,32]
binsrch(a,3,0,6):
mid = 3, a[3]=8 3
binsrch(a,3,0,2)
mid = 1, a[1]=3 = 3 retorna(1)
binsrch(a,32,0,6):
mid = 3, a[3]=8 32
binsrch(a,32,4,6)
mid=5, a[5]=24 32
binsrch(a,32,6,6)
 mid=6, a[6]=32=32 retorna(6)
*
binsrch(a,31,0,6):
mid = 3, a[3]=8 31
binsrch(a,31,4,6)
mid=5, a[5]=24 31
binsrch(a,31,6,6)
 mid=6, a[6]=32 31
binsrch(a,31,6,5 ) retorna(-1)
 
_________________________
Exercício 
Escreva um versão iterativa da busca binária. 
*
Exercício
Adapte o algoritmo de busca binária para localizar o nome de uma pessoa numa tabela dada sua matrícula. 
Considere que o cadastro de pessoas é um vetor onde cada posição é uma estrutura do tipo “registro” definido abaixo. 
Esse vetor não esta ordenado. 
Uma estrutura de indice, constituída de um vetor do tipo “pessoa” deve ser usado para obter a posição do registro no cadastro. 
O índice esta ordenado por matrícula.
typedef struct dado {
		int matricula;
		int posicao;
} pessoa;
typedef struct reg {
		int matricula;
		char nome[50];
} registro;