Embed Size (px)
Citation preview
ANHANGUERA – 2016.1
ALGORITMOS E ESTRUTURA DE DADOSAULA 04 – RECURSÃO
Prof. Thomás da [email protected]
ALGORITMOS E ESTRUTURA DE DADOS – Prof. Thomás da Costa
RECURSÃO
RECURSÃO
ALGORITMOS E ESTRUTURA DE DADOS – Prof. Thomás da Costa
O que é:
É quando uma função, invoca a si mesma para resolver um problema em uma instância menor.
RECURSÃO
Recursividade
ALGORITMOS E ESTRUTURA DE DADOS – Prof. Thomás da Costa
Mais detalhes:
- É quando uma função invoca a si mesmo.- As chamadas devem possuir um fim.- O programa pode ficar em um loop infinito.- Dependendo da sua forma de utilização, pode ser lento.- Existe uma pilha de execução.- Simplifica algumas lógicas de programação.- Programas recursivos são complexos.- Possuem grande semelhança com instruções de laços.- Muito cuidado: existe um limite para uma função chamar a si próprio.- Esse limite é definido por cada compilador e linguagem.
Vamos ver um exemplo !!!
RECURSÃO
Recursividade
ALGORITMOS E ESTRUTURA DE DADOS – Prof. Thomás da Costa
Exemplo de Fatorial:
No nosso exemplo vamos utilizar fatorial !!!
O que é fatorial?
É o produto de todos os seus antecessores, incluindo si próprio e excluindo o zero
Exemplo: 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720
FATORIAL DE 6 É 720 !!!
RECURSÃO
Recursividade
ALGORITMOS E ESTRUTURA DE DADOS – Prof. Thomás da Costa
#include <iostream> using namespace std; int calcular_fatorial(int valor); int main(){
cout << "Valor do fatorial:" << calcular_fatorial(6);} int calcular_fatorial(int valor){
if (valor == 0)return 1;
else {
valor = (valor * calcular_fatorial(valor - 1));
cout << valor << endl;return valor;
}}
Chamada recursiva
Vamos ver o programa passo-a-passo, analisando a
pilha de execução
ALGORITMOS E ESTRUTURA DE DADOS – Prof. Thomás da Costa
... int calcular_fatorial(int valor){
if (valor == 0)return 1;
else {
valor = (valor * calcular_fatorial(valor - 1));
cout << valor << endl;return valor;
}}
calcular_fatorial(6) -> valor = (6 * calcular_fatorial(5));
calcular_fatorial(5) -> valor = (5 * calcular_fatorial(4));
calcular_fatorial(4) -> valor = (4 * calcular_fatorial(3));
calcular_fatorial(3) -> valor = (3 * calcular_fatorial(2));
calcular_fatorial(2) -> valor = (2 * calcular_fatorial(1));
calcular_fatorial(1) -> valor = (1 * calcular_fatorial(0));
calcular_fatorial(0)
-> return 1;
Pilha de execuçãoFim da recursividade
ALGORITMOS E ESTRUTURA DE DADOS – Prof. Thomás da Costa
... int calcular_fatorial(int valor){
if (valor == 0)return 1;
else {
valor = (valor * calcular_fatorial(valor - 1));
cout << valor << endl;return valor;
}}
calcular_fatorial(6) -> valor = (6 * 5 * 4 * 3 * 2 * 1 * 1);
calcular_fatorial(5) -> valor = (5 * 4 * 3 * 2 * 1 * 1);
calcular_fatorial(4) -> valor = (4 * 3 * 2 * 1 * 1);
calcular_fatorial(3) -> valor = (3 * 2 * 1 * 1);
calcular_fatorial(2) -> valor = (2 * 1 * 1);
calcular_fatorial(1) -> valor = (1 * 1);
calcular_fatorial(0)
-> return 1;
ALGORITMOS E ESTRUTURA DE DADOS – Prof. Thomás da Costa
Exemplo de Potenciação:
No próximo exemplo, vamos ver como criar um programa de potenciação.
O que é potenciação?
É o produto de um número por ele mesmo, em uma quantidade de vezes definida.
Exemplo: 5³ = 5 * 5 * 5 = 125
POTÊNCIA DE 5 É 125 !!!
RECURSÃO
Recursividade
ALGORITMOS E ESTRUTURA DE DADOS – Prof. Thomás da Costa
#include <iostream> using namespace std; int potencia(int base, int expoente); int main(){
int base = 5;int expoente = 3;cout << "Potencia:" << potencia(base, expoente);
} int potencia(int base, int expoente){
if (expoente == 0)return 1;
else{
int valor = base * potencia(base, expoente - 1);cout << valor << endl;return valor;
}
}
Chamada recursiva
ALGORITMOS E ESTRUTURA DE DADOS – Prof. Thomás da Costa
Exemplos:• Analisamos alguns exemplos estudados em Programação Estruturada II.• Vamos praticar um pouco mais. • Vamos começar !!!
RECURSÃO
Recursividade
ALGORITMOS E ESTRUTURA DE DADOS – Prof. Thomás da Costa
RECURSÃO
Exercícios
Encontrar o valor máximo de um elemento de um vetor com N posições.
ALGORITMOS E ESTRUTURA DE DADOS – Prof. Thomás da Costa
#include <iostream> using namespace std; int maximo_vetor(int v[], int n); int main(){
int vetor[10] = { 2, 1, 10, 6, 1, 9, 1, 1, 0, 3 };cout << maximo_vetor(vetor, 10);
} int maximo_vetor(int v[], int n){
if (n == 1)return v[0];else{
int x;x = maximo_vetor(v, n-1);if (x > v[n-1])
return x;else
return v[n-1];}
}
ALGORITMOS E ESTRUTURA DE DADOS – Prof. Thomás da Costa
RECURSÃO
Exercícios
Efetuar a soma de um vetor utilizando recursão.
ALGORITMOS E ESTRUTURA DE DADOS – Prof. Thomás da Costa
#include <iostream> using namespace std; int soma(int v[], int n); int main(){
int soma_vetor[5] = { 8, 0, 1, 3, 5};cout << soma(soma_vetor, 5);
} int soma(int v[], int n){
if (n == 0)return 0;else{int s = soma(v, n-1);if (v[n-1] > 0)
s += v[n-1];return s;}
}
ALGORITMOS E ESTRUTURA DE DADOS – Prof. Thomás da Costa
- É quando uma função invoca a si mesmo.- As chamadas devem possuir um fim.- O programa pode ficar em um loop infinito.- Dependendo da sua forma de utilização, pode ser lento.- Existe uma pilha de execução.- Simplifica algumas lógicas de programação.- Programas recursivos são complexos.- Possuem grande semelhança com instruções de laços.- Muito cuidado: existe um limite para uma função chamar a si próprio.
RECURSÃO
Resumo
Obrigado !!!
ANHANGUERA – 2016.1
