Baixe Estruturas de dados: Recursividade e outras Slides em PDF para Estruturas de Dados e Algoritmos, somente na Docsity! Estruturas de Dados
DR
Re ade
Prof. Alex Sandro
alexscunha(Dyahoo.com.br NEED!
2 Recursividade Conceito Uma função é dita recursiva se ela faz chamada a si mesmo (direta ou indiretamente) dentro de sua implementação Possuem um critério de parada, caso contrário, seria uma recursividade infinita. Um exemplo clássico: cálculo do fatorial Se n =0, fatorial = 1 3! = 3x2x1 = 6 4! = 4x3x2x1 = 24 (e assim por diante) 5 Recursividade Solução recursiva: int fatorial(int num){ int x,y; if (num==0) return 1; x = num – 1; y = fatorial(x); return( num * y ); } No comando y=fatorial(x), a função fatorial chama a si mesma Cada vez que for executado, sua entrada será um a menos que na vez anterior Devemos verificar se o algoritmo sempre tem uma parada 6 Recursividade Como funciona a recursividade? Na primeira chamada da função, n=4 e x=3 Toda vez que fatorial é chamada recursivamente, um novo conjunto de variáveis locais e de parâmetros é alocado. Apenas a cópia mais recente das variáveis são referenciadas Quando ocorre o retorno de fatorial, o fluxo é retomado ao ponto de chamada anterior A alocação mais recente das variáveis é liberada 7 Recursividade Uso da pilha para fazer o controle das variáveis: A pilha mantém as sucessivas gerações de variáveis locais e parâmetros Toda vez que uma função recursiva é iniciada, uma nova alocação de suas variáveis é introduzida no topo da pilha Quando a função retorna ao ponto de chamada anterior, a alocação do topo é liberada e é executado um desvio para o endereço de retorno A função de chamada recupera o valor, prossegue a execução e recorre à sua própria área de dados que, agora, está no topo da pilha Suponha a execução da seguinte instrução: printf(“%d”,fatorial(4)); 10 Recursividade Considerações Devemos verificar a validade dos parâmetros de entrada numa rotina recursiva printf(“%d”, fatorial(-1)); Resultado: Você acha que a função vai ser executada corretamente? Quando ela vai parar? Alguma mensagem de erro é produzida? 11 Recursividade Revisão da função fatorial() int fatorial(int num){ int x,y; if (num < 0) { printf(“%s”,”Parametro negativo na funcao fatorial”); exit(1); } if (num==0) return 1; x = num – 1; y = fatorial(x); return( n * y ); } 12 Recursividade Outro Exemplo: Sequência de Fibonacci. 0, 1, 1, 2, 3, 5, 8, 13, 21, ... Começa com 0 e 1, cada número posterior é a soma de dois anteriores: Fibonacci(0) = 0; Fibonacci(1) = 1; Fibonacci(2) = Fibonacci(0) + Fibonacci(1); Fibonacci(3) = Fibonacci(1) + Fibonacci(2); Fibonacci(4) = Fibonacci(2) + Fibonacci(3); Fibonacci(5) = Fibonacci(3) + Fibonacci(4); 15 Recursividade Atenção ! Qualquer problema que pode ser resolvido recursivamente também pode ser resolvido iterativamente, mesmo que o resultado não seja aparente; Evite usar a recursividade onde o desempenho é fundamental. Recursividade aumenta “overhead” de chamadas de funções, ou seja, são demoradas (tempo do processador) e consomem memória adicional. 16 Recursividade Desenvolver soluções recursivas não é uma tarefa fácil As definições e algoritmos originais precisam ser desenvolvidos. A maioria dos problemas pode ser solucionada de maneira simples (sem recursividade) Porém, alguns problemas podem ser resolvidos em termos lógicos e com mais elegância por meio de recursividade. 17 Recursividade Exercício: Determine o que a seguinte função recursiva em C calcula. Escreva uma função iterativa para atingir o mesmo objetivo. func(int n) { if (n==0) return 0; return (n + func(n-1)); } /* fim da função func */
