Recursividade em Estrutura de Dados 2 - Conceitos e Aplicações

ESTRUTURA DE DADOS II 60 HORAS PROF JULIANO RATUSZNEI EMAIL JULIANORATUSZNEIUNICIDEDUBR RECURSIVIDADE A recursão é uma técnica que define um problema em termos de uma ou mais versões menores deste mesmo problema A recursão pode ser utilizada sempre que for possível expressar a solução de um problema em função do próprio problema Uma função é dita recursiva quando dentro do seu código existe uma chamada para si mesma 2 RECURSIVIDADE Por exemplo quando um objeto é colocado entre dois espelhos planos paralelos e frente a frente surge uma imagem recursiva porque a imagem do objeto refletida num espelho passa a ser o objeto a ser refletido no outro espelho e assim sucessivamente 3 RECURSIVIDADE 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 devese ser a condição de parada 4 RECURSIVIDADE CONDIÇÃO DE PARADA Quando isso ocorre dizse 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 5 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 6 RECURSIVIDA DE Além disso muitas vezes é evidente a natureza recursiva do problema a ser resolvido como é o caso de problemas envolvendo árvores estruturas de dados naturalmente recursivas Entretanto também há desvantagens Quase sempre consomem mais recursos especialmente memória devido uso intensivo da pilha do computador logo tendem a apresentar um desempenho inferior aos iterativos Eles são mais difíceis de serem depurados especialmente quando for alta a profundidade de recursão número máximo de chamadas simultâneas 7 RECURSIVIDADE EXEMPLO Exemplo 1 Função Fatorial Esta função é um dos exemplos clássicos de recursividade e por isso de citação quase obrigatória Eis sua definição recursiva Executar o procedimento do cálculo para n 3 8 RECURSIVIDADE EXEMPLO Observe a facilidade em transformar a definição da função para Portugol ou C 𝑛 1𝑠𝑒 𝑛0 𝑛 𝑛1 𝑠𝑒 𝑛0 função Fatn natural natural início se n 0 então retorne 1 senão retorne n Fatn 1 fim PORTUGOL unsigned int Fatunsigned int n if n 0 return 1 else return n Fatn 1 C 9 RECURSIVIDADE EXEMPLO pela definição valor de 4 é calculado como 44 34324321432104321124 Note que função é chamada recursivamente com argumento decrescente até chegar ao caso trivial 0 cujo valor é 1 Este caso trivial condição de parada encerra a seqüência de chamadas recursivas 𝑛 1𝑠𝑒 𝑛0 𝑛 𝑛1 𝑠𝑒 𝑛0 unsigned int Fatunsigned int n if n 0 return 1 else return n Fatn 1 10 RECURSIVIDADE EXEMPLO 𝑛 1𝑠𝑒 𝑛0 𝑛 𝑛1 𝑠𝑒 𝑛0 unsigned int Fatunsigned int n if n 0 return 1 else return n Fatn 1 11 RECURSIVIDADE EXEMPLO Como n nn 1n 2 321 é muito simples implementar um algoritmo iterativo da função fatorial Abaixo são apresentados dois algoritmos iterativos que se equivalem 𝑛 1𝑠𝑒 𝑛0 𝑛 𝑛1 𝑠𝑒 𝑛0 12 RECURSIVIDADE EXEMPLO 2 Exemplo 2 Sequencia de Fibonacci A seqüência 0 1 1 2 3 5 8 13 21 é conhecida como seqüência ou série de Fibonacci e tem aplicações teóricas e práticas na medida em que alguns padrões na natureza parecem seguila Pode ser obtida através da definição recursiva 13 RECURSIVIDADE EXEMPLO 2 a qual pode ser implementada como 14 RECURSIVIDADE EXEMPLO 2 Note que para n 1 cada chamada causa 2 novas chamadas de Fib isto é o número total de chamadas cresce exponencialmente Para Fib5 são feitas 14 chamadas da função Para Fib25 são feitas 242784 chamadas recursivas 15 RECURSIVIDADE EXEMPLO 2 No caso da seqüência de Fibonacci é relativamente simples implementar um algoritmo iterativo com complexidade On que tire proveito dos valores já calculados Eis uma possibilidade iterativa 16 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 17 EXERCÍCIOS PARA FIXAÇÃO 2 18 EXERCÍCIOS PARA FIXAÇÃO 3 19