3. Algoritmos Recursivos

1 Introdução à Computação II - 5952011

Introdução à Computação II 5952011

3. Algoritmos Recursivos

Prof. Renato Tinós

Depto. de Computação e Matemática

(FFCLRP/USP)


3. Algoritmos Recursivos

3.1. Recursão

3.1. Princípios de Recursão

Principais Tópicos


• Recursão é o nome dado para o caso em que

uma função invoca ela mesma

uma seqüência de funções, as quais uma pode eventualmente chamar a primeira função novamente

3.1. Recursão


• Exemplo de recorrência

Cálculo do fatorial

n! = n ( n -1 ) ... 2 1

O que significa “...” para um computador?

Uma definição mais precisa

0se,1

0se,!1!

n

nnnn

3.1. Recursão


Exemplo: Cálculo do fatorial do número 4

4 ! = 4 3 !

4 ! = 4 ( 3 2 ! )

4 ! = 4 ( 3 ( 2 1 ! ) )

4 ! = 4 ( 3 ( 2 ( 1 0 ! ) ) )

4 ! = 4 ( 3 ( 2 ( 1 1 ) ) )

4 ! = 4 ( 3 ( 2 1 ) )

4 ! = 4 ( 3 2 )

4 ! = 4 6

4 ! = 24

3.1. Recursão


• Este cálculo ilustra a essência do modo como recursão funciona

Para obter a resposta para um problema grande, um método geral é utilizado para reduzir o problema em um ou mais problemas de natureza similar, mas com tamanho menor

• C, como a maioria das linguagens modernas, aceita recursão

3.1. Recursão


• Todo processo recursivo consiste de duas partes

i. Um caso base de tamanho mínimo que é processado sem recursão

ii. Um método geral que reduz o caso particular em um ou mais casos menores, fazendo o processo progredir até eventualmente reduzir o problema até o caso base

3.1. Recursão


Exercício 3.1. Desenvolva em pseudo-código e implemente em C um algoritmo para calcular o fatorial de um número inteiro não-negativo digitado pelo usuário através de

a. Um programa iterativo

b. Um programa recursivo

3.1. Recursão


// Versão Iterativa

Algoritmo iteFatorial( n ):

Entrada: número inteiro não negativo n

Saída: valor do fatorial de n

produto 1

para i 1 até n faça

produto produto * i

fim para

retorne ( produto )

3.1. Recursão


3.1. Recursão

// Versão Recursiva

Algoritmo recFatorial( n ):



se n = 0

retorne ( 1 )

senão

retorne ( n * recFatorial ( n-1 ) )

fim se


3.1. Recursão

• Considere o que acontece quando uma função é chamada dentro de um programa

A posição em que a chamada foi feita dentro do programa deve ser lembrada

As variáveis locais, registros, etc.. correntes não devem ser perdidos

• Toda esta informação pode ser armazenada em uma estrutura de dados


• Exemplo de chamadas de função

M M M M M M M M M

A A A A

B B B

C

A C C

C

M

C

C

C

M

C

C

M

C

tempo

Espaço da pilha

para dados

3.1. Recursão


• Exemplo de chamadas de função

Árvore de chamadas de função

A altura da árvore tem relação com a quantidade de memória que o programa necessita

M

A

B

C

C

C

C

3.1. Recursão


• Árvore de recursão

Árvore de chamadas de função que mostram apenas as chamadas recursivas

Exemplo 3.1. Qual a árvore de recursão do programa recursivo desenvolvido no Exercício 3.1?

3.1. Recursão



3.2.1. Projeto de Algoritmos Recursivos

Alguns dos principais aspectos no projeto de algoritmos recursivos são

i. Ache o método geral (passo chave)

Como o programa pode ser dividido em partes menores?

Uma vez que um passo pequeno e simples em direção à solução é encontrado, pergunte se o restante do problema pode ser resolvido do mesmo modo ou de modo similar


ii. Ache o caso base (ou regra de parada)

A regra de parada é geralmente o caso especial (pequeno) que é trivial ou fácil de se resolver sem a necessidade de recursão

iii. Escreva o algoritmo

Combine o passo chave e a regra de parada usando um comando condicional (se)



iv. Verifique se o algoritmo termina

Comece com uma situação geral e verifique se, depois de um número finito de passos, a regra de parada será satisfeita

Considere também os casos extremos

Exemplo: Se for pedido para fazer nada, o algoritmo não deve retornar nenhum valor (e não, como fazem muitos programas, uma mensagem)

v. Desenhe a árvore de recursão

Utilize um ou dois exemplos para gerar a árvore

Lembre-se que o tamanho da árvore é relacionado com a quantidade de memória que o programa necessita

O tamanho total da árvore reflete o número de vezes que o passo chave será executado

Tempo total do programa



3.2.2. Análise de Algoritmos Recursivos

Desenhe a árvore de recursão

Associe uma função de complexidade f (n) para cada procedimento (nó da árvore)

Multiplique o número de nós por f (n)

Exercício 3.2. Faça a análise assintótica (notação O) do algoritmo recursivo desenvolvido no Exercício 3.1.?



3.2.3. Como Recursão Funciona

Na fase de projeto, recursão é um dos mais flexíveis e poderosos métodos para a resolução de problemas

No entanto, na fase de implementação, deve-se questionar se recursão é o método mais adequado para a resolução do problema dado



Quando recursão é eficiente?

Para responder esta questão, o problema do armazenamento de informações quando uma função é chamada deve ser tratado

Quando uma função é chamada

Ela deve ter uma área de armazenamento para

– Variáveis locais

– Endereço de retorno

– Etc...

Assim, as chamadas de funções são implementadas através de mudanças de áreas de armazenamento



Quando recursão é eficiente?

Quanto mais funções são chamadas em cadeia (ou seja, uma dentro da outra), mais espaço é utilizado

Ou seja, o espaço criado pela função não é liberado

Assim,

No caso recursivo, diversas áreas de armazenamento são utilizadas

No caso não-recursivo, as informações podem ocupar uma mesma área de armazenamento



No entanto, existem casos em que recursão deve ser utilizada

Exemplo: Torres de Hanói


1 2 3


Recursão pode ser utilizado para resolver o problema das Torres de Hanói

De fato, o uso de recursão para este problema não só produz uma solução elegante e simples, mas também produz a melhor solução possível

Algoritmo recHanoi( discos , inicio , fim , temporario ):

Entrada: número do disco, torres inicial, final e temporária

se discos > 0

recHanoi ( discos-1 , inicio , temporario , fim )

escreva (“Mova disco ” , discos , ” da torre “ , inicio , “ para a torre “, fim )

recHanoi ( discos-1 , temporario , fim , inicio )

fim se

retorne



Exemplo com dois discos

recHanoi ( 2 , 1 , 3 , 2 )

recHanoi ( 1 , 1 , 2 , 3 )

recHanoi ( 0 , 1 , 3 , 2 )

“Mova disco 1 da torre 1 para a torre 2”

recHanoi ( 0 , 3 , 2 , 1 )


recHanoi ( 1 , 2 , 3 , 1 )

recHanoi ( 0 , 2 , 1 , 3 )


recHanoi ( 0 , 3 , 1 , 2 )



Exercício 3.3. Faça a análise assintótica (notação O) do algoritmo recursivo apresentado para o problema das Torres de Hanói?



3.2.4. Comparações Entre Recursão e Iteração

Considere os algoritmos para cálculo do fatorial apresentados na Seção 3.1.

Qual destes programas, o iterativo e o recursivo, utiliza menos espaço de armazenamento de memória?



Considere primeiro o algoritmo iterativo que calcula o fatorial

Exemplo: Fatorial de n=5


Algoritmo iteFatorial( n ):



produto 1

para i 1 até n faça

produto produto * i

fim para

retorne ( produto )



Considere agora o algoritmo recursivo que calcula o fatorial

Exemplo: Fatorial de n=5


Algoritmo recFatorial( n ):



se n = 0

retorne ( 1 )

senão

retorne ( n * recFatorial ( n-1 ) )

fim se



A versão recursiva

Cria uma pilha e a preenche com n números

Assim, necessita de mais espaço de memória

Um outro exemplo em que a versão iterativa é menos interessante que a versão recursiva é a computação dos números de Fibonacci, que são definidos através da seguinte relação recursiva

0se,0

1se,1

1se,21

n

n

nnFnF

nF



Exercício 3.4. Desenvolva em pseudo-código e implemente em C um algoritmo para calcular o n-ésimo número de Fibonacci, sendo que n é um número inteiro não-negativo digitado pelo usuário, através de

a. Um programa iterativo

b. Um programa recursivo




Algoritmo iteFibonacci( n ):


Saída: valor do n-ésimo número de Fibonacci

se ( n ≤ 0 ) retorne ( 0 )

senão se ( n = 1 ) retorne ( 1 )

senão

valor_penultimo 0

valor_ultimo 1

para i 2 até n faça valor_corrente valor_penultimo + valor_ultimo

valor_penultimo valor_ultimo

valor_ultimo valor_corrente

fim para

retorne ( corrente )

fim se




Algoritmo recFibonacci( n ):


Saída: valor do n-ésimo número de Fibonacci

se ( n ≤ 0 ) retorne ( 0 )

senão se ( n = 1 ) retorne ( 1 )

senão

retorne ( recFibonacci( n-1 ) + recFibonacci( n-2 ) )

fim se



F (5)

F (4)

F (3) F (2)

F (2) F (1) F (1) F (0)

F (1) F (0)

F (3)

F (2) F (1)

F (1) F (0)

Exemplo: n=5

Observe que F(2) é computado 3 vezes !!!!!!!!

Apesar de computar os valores corretamente, o algoritmo não é eficiente pois requer muito tempo de computação



O que é diferente do último exemplo e o uso apropriado de recursão?

A resposta está na análise da árvore de recursão

Quando cada vértice da árvore tem apenas um filho (ou seja, faz apenas uma chamada de função)

A árvore é fácil de entender

O programa iterativo pode ser imediatamente obtido através do programa recursivo

Os dados são mantidos em uma pilha

Caso contrário

Se a pilha é utilizada, alguns dados são descartados

Uma boa idéia é utilizar outra estrutura de dados

No entanto, em geral, os problemas ficam complicados



Recursão pode ser vista como

Um enfoque de cima para baixo (top-down)

Iteração pode ser vista como

Um enfoque de baixo para cima (bottom-up)

Se a pilha para resolver recursão pode ser entendida como uma lista de tarefas a serem cumpridas pelo programa, então

Se a lista pode ser facilmente construída, então iteração provavelmente é melhor

Caso contrário, recursão é provavelmente melhor


Documents

3. Algoritmos Recursivos