Baixe o app para aproveitar ainda mais
Prévia do material em texto
ECT1203 Linguagem de Programação 2014.2 Prof. Caroline Rocha Aula 13 – Funções Recursivas Universidade Federal do Rio Grande do Norte Escola de Ciências e Tecnologia Hora de silenciar o celular • Manter o celular sempre desligado/silencioso quando estiver em sala de aula • Nunca atender o celular em sala de aula Objetivo da aula • Responde as seguintes perguntas: ▫ Vimos que a função main() chama uma função, mas essa função que foi chamada pela main() pode chamar outra função? ▫ Uma função pode chamar a si mesmo? Objetivo da aula • Definição • Elementos • Exemplos • Exercícios em Sala • Torre de Hanoi Recursão Em uma abordagem recursiva, a solução de um problema depende das soluções de instâncias menores do mesmo problema. Funções Recursivas Uma função recursiva é uma função que se refere a si própria. A idéia consiste em utilizar a própria função que estamos a definir na sua definição. int funcao(int a){ int x = a-1; if(x == 0) return 1; else return funcao(x); } Fatorial 𝑛! = 1 𝑠𝑒 𝑛 = 0 𝑛 ∗ 𝑛 − 1 ! 𝑠𝑒 𝑛 > 0 𝑓𝑎𝑡𝑜𝑟𝑖𝑎𝑙(𝑛) = 1 𝑠𝑒 𝑛 = 0 𝑛 ∗ 𝑓𝑎𝑡𝑜𝑟𝑖𝑎𝑙 𝑛 − 1 𝑠𝑒 𝑛 > 0 Função Fatorial Recursiva #include <iostream> using namespace std; int fatorial (int n){ if (n == 0) return 1; else return n * fatorial(n-1); } int main(){ int n; cout <<"Entre com um numero positivo: "; cin >> n; cout <<"Fatorial de "<< n <<" = "<< fatorial(n); return 0; } Função Fatorial Recursiva 1a chamada: fatorial(6) 2a chamada: 6 * fatorial(5) 3a chamada: 6 * 5 * fatorial(4) 4a chamada: 6 * 5 * 4 * fatorial(3) 5a chamada: 6 * 5 * 4 * 3 * fatorial(2) 6a chamada: 6 * 5 * 4 * 3 * 2 * fatorial(1) 1o retorno: 6 * 5 * 4 * 3 * 2 * 1 2o retorno: 6 * 5 * 4 * 3 * 2 3o retorno: 6 * 5 * 4 * 6 4o retorno: 6 * 5 * 24 5o retorno: 6 * 120 6o retorno: 720 Função Fatorial Iterativa #include <iostream> using namespace std; int fatorial (int); int main(){ int n; cout <<"Entre com um numero positivo: "; cin >> n; cout <<"Fatorial de "<< n <<" = "<< fatorial(n); return 0; } int fatorial (int n){ int fat = 1; for(int i=2; i<=n; i++) fat = fat * i; return fat; } Funções Recursivas • Em todas as funções recursivas existe: ▫ Um passo básico (ou mais) cujo resultado é imediatamente conhecido. Por exemplo: fatorial(0) = 1 ▫ Um passo recursivo em que se tenta resolver um sub-problema do problema inicial. Por exemplo: fatorial(n) = n * fatorial(n-1) Potência 𝑥𝑦 = 1 𝑠𝑒 𝑦 = 0 𝑥 ∗ 𝑥𝑦−1 𝑠𝑒 𝑦 > 0 𝑝𝑜𝑡𝑒𝑛𝑐𝑖𝑎(𝑥, 𝑦) = 1 𝑠𝑒 𝑦 = 0 𝑥 ∗ 𝑝𝑜𝑡𝑒𝑛𝑐𝑖𝑎 𝑥, 𝑦 − 1 𝑠𝑒 𝑦 > 0 Função Potência Recursiva #include <iostream> using namespace std; int pot(int x, int y){ if (y == 0) return 1; else return x * pot(x, y-1); } int main(){ cout << pot(3, 4) << endl; return 0; } Função Potência Iterativa #include <iostream> using namespace std; int pot(int x, int y){ int res = 1; while(y > 0){ res = res * x; y--; } return fat; } int main(){ cout << pot(3, 4) << endl; return 0; } Série de Fibonacci • É uma sequência de números naturais, na qual os dois primeiros termos são 1 e 1 e cada termo subsequente corresponde à soma dos dois precedentes: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... • Em termos matemáticos, a sequência é definida recursivamente pela fórmula abaixo: 2 para),2fib()1fib( 2 para,1 1 para,1 )fib( nnn n n n Série de Fibonacci: função iterativa int fib (int n){ int num1 = 0, num2 = 1, num3; for(int i=2; i<=n; i++){ num3 = num2+num1; num1 = num2; num2 = num3; } if(n==0) return num1; else if(n==1) return num2; else return num3; } Série de Fibonacci: função recursiva int fib (int n){ if (n==0) return 0; else if (n==1) return 1; else return fib(n-1) + fib(n-2); } Par ou ímpar • Como seria uma solução recursiva pra determinar se um número natural é par ou ímpar? Par ou ímpar bool par(int n){ if (n == 0) return true; else return impar(n-1); } bool impar(int n){ if (n == 0) return false; else return par(n-1); } Alocação de memória • Quando uma função é chamada, memória é alocada para todos os seus parâmetros e variáveis locais. • Toda função ativa tem memória na pilha (com a função atual no topo). • Quando uma função termina a memória é desalocada. • Exemplo: main() chama f() f() chama g() g() chama recursivamente g() main() f() g() g() Funções recursivas x iterativas • Em geral, a todo procedimento recursivo corresponde um outro não-recursivo (iterativo). • Vantagens da recursão: ▫ algoritmos mais concisos; ▫ simplifica a solução de alguns problemas; ▫ facilidade de implementação e compreensão; ▫ algoritmos de divisão e conquista (Quicksort, etc) • Desvantagens: ▫ tendem a ser mais lentos e consumir mais memória ▫ erros de implementação podem levar a estouro de memória. Jogo da Torre de Hanoi Consiste de três posições (A, B e C) e N discos de diferentes tamanhos. Inicialmente, todos os discos se encontram empilhados na posição A em ordem decrescente de tamanho, de baixo para cima. O objetivo é empilhar todos os discos na posição C, atendendo às seguintes restrições: apenas um disco pode ser movido de cada vez; nenhum disco pode ser jamais colocado sobre outro de tamanho menor Faça um programa para resolver o problema da Torre de Hanoi, dado o número de discos N.
Compartilhar