Aula 5 - Recursividade-Soluções de problemas

Prévia do material em texto

estrutura de dados II – 60 horas
Prof: Juliano Ratusznei.
Email: juliano.ratusznei@unicid.edu.br
Recursividade
Aprendendo recursividade com código.
RELEMBRANDO
A ideia básica de um algoritmo recursivo consiste em diminuir sucessivamente o problema em um problema menor ou mais simples, até que o tamanho ou a simplicidade do problema reduzido permita resolvê-lo de forma direta, sem recorrer a si mesmo.
Esta deve-se ser a condição de parada
2
Recursividade – condição de parada
Quando isso ocorre, diz-se que o algoritmo atingiu uma condição de parada, a qual deve estar presente em pelo menos um local dentro algoritmo. Sem esta condição o algoritmo não “para” de chamar a si mesmo, até estourar a capacidade da pilha, o que geralmente causa efeitos colaterais e até mesmo o término indesejável do programa
3
Recursividade
Para todo algoritmo recursivo existe um outro correspondente iterativo (não recursivo), que executa a mesma tarefa. 
Implementar um algoritmo recursivo, partindo de uma definição recursiva do problema, em uma linguagem de programação é simples e quase imediato, pois o seu código é praticamente transcrito para a sintaxe da linguagem. 
Por essa razão, em geral, os algoritmos recursivos possuem código mais claro (legível) e mais compacto do que os correspondentes iterativos.
4
Aprendendo recursividade
Segue o exercício abaixo:
Escreva um programa que imprima na tela os números de 1 a 500 que são múltiplos de 5.
Para escrever um algoritmo recursivo devemos identificar a condição de parada. Então nesse caso Qual é a condição de parada?
5
Aprendendo recursividade
Segue o exercício abaixo:
Escreva um programa que imprima na tela os números de 1 a 500 que são múltiplos de 5.
Além dessa informação nesse caso uma das obrigatoriedades é não utilizar laço de repetição apenas a recursividade irá fazer esse tipo de execução de repetição.
6
Aprendendo recursividade
7
Escreva um programa que some os números de 1 a 100.
Escreva um programa que calcule a soma dos números pares entre 25 e 200.
Qual a condição de parada? Para os exercícios abaixo?
Aprendendo recursividade
8
Qual a condição de parada? Para os exercícios abaixo?
Faça um programa que calcule a multiplicação de dois números através de somas sucessivas.
Aprendendo recursividade
9
Vamos implementar os exercícios de 1 até 4.
É hora de codificar!!!
Aprendendo recursividade
10
Escreva um programa que possui entrada 10 números e imprimir a metade de cada um deles.
Crie um programa que o usuário diga qual a tabuada deseja imprimir.
Escreva um programa que some todos números de 1 a 500 que são múltiplos de 5 ou de 3.
Escreva um programa que dado um número, ele diz se é primo ou não.
Escreva um programa que verifique se um número digitado é primo.
Aprendendo recursividade
11
Faça um programa que imprima a progressão aritmética de dois números. 
	As entradas são: razão, primeiro elemento e o limite superior.
	Ex: limite=20/ razão=5 -> 0 5 10 15 20
Escreva um programa onde o usuário diz quantos números quer digitar, em seguida solicite a ele 
	que digite todos os números e diga qual o maior número daqueles digitados.
Criar um programa que recebe vários números e imprima o produto dos ímpares e a soma dos pares.
Uma das maneiras de se conseguir a raiz quadrada de um número é subtrair do número os ímpares consecutivos 
	a partir de 1, até que o resultado da subtração seja menor ou igual a zero. 
	O número de vezes que se conseguir fazer a subtração é a raiz quadrada exata (resultado 0) 
	ou aproximada do número (resultado negativo).
		Ex.: 	Raiz de 16		16-1 = 15-3 = 12-5 = 7-7 = 0
	Faça um programa que calcule a raiz quadrada de um número usando este método.
Exercícios para fixação
1. ) Implemente recursivamente uma função Max que retorne o maior valor armazenado em um vetor V, contendo n números inteiros.
12
Exercícios para Fixação
2. 
13
Exercícios para Fixação
3. 
14
image2.png
image3.png
image4.png
image5.png