Aula 5 - Recursividade

Prévia do material em texto

CCT0608 ALGORITMOS AVANÇADOS
Aula 5: Recursividade
Prof. Dr. Roney L. de S. Santos
RONEY.LIRASALE@professores.estacio.br
RECURSIVIDADE
2
• É uma técnica de programação na qual um método chama a si
mesmo.
• Uma função é dita recursiva quando dentro dela é feita uma ou
mais chamadas a ela mesma.
RECURSIVIDADE
3
• A ideia é dividir um problema original um subproblemas
menores de mesma natureza (divisão) e depois combinar as
soluções obtidas para gerar a solução do problema original de
tamanho maior (conquista).
• Os subproblemas são resolvidos recursivamente do mesmo modo
em função de instâncias menores, até se tornarem problemas
triviais que são resolvidos de forma direta, interrompendo a
recursão.
RECURSIVIDADE
4
• As funções recursivas são em sua maioria soluções mais
elegantes e simples, se comparadas a funções tradicionais ou
iterativas,
– já que executam tarefas repetitivas sem utilizar nenhuma estrutura de
repetição
• como for ou while.
• Porém essa elegância e simplicidade têm um preço que requer
muita atenção em sua implementação
RECURSIVIDADE
5
• Uma definição recursiva é constituída de duas partes:
• Parte 1
– Há um ou mais casos base que dizem o que fazer em situações simples
• A resposta pode ser dada de imediato
– Garante que a recursão eventualmente possa parar.
• Parte 2
– Há um ou mais casos recursivos que são mais gerais e definem a função
em termos de uma chamada mais simples a si mesma.
RECURSIVIDADE
6
• Em programação, a recursividade é implementada como uma
função que chama a si mesma, direta ou indiretamente
RECURSIVIDADE
7
• Exemplo 1: Fatorial de um número
CASO BASE
CASO RECURSIVO
RECURSIVIDADE
8
• Exemplo 1: Fatorial de um número
RECURSIVIDADE
9
• Exemplo 1: Fatorial de um número
RECURSIVIDADE
10
• Exemplo 1: Fatorial de um número
RECURSIVIDADE
11
• Exemplo 1: Fatorial de um número
RECURSIVIDADE
12
• Exemplo 1: Fatorial de um número
RECURSIVIDADE
13
• Exemplo 1: Fatorial de um número
RECURSIVIDADE
14
• Exemplo 1: Fatorial de um número
RECURSIVIDADE
15
• Exemplo 1: Fatorial de um número
RECURSIVIDADE
16
• Exemplo 1: Fatorial de um número
RECURSIVIDADE
17
• Exemplo 1: Fatorial de um número
RECURSIVIDADE
18
• Exemplo 1: Fatorial de um número
RECURSIVIDADE
19
• Exemplo 1: Fatorial de um número
RECURSIVIDADE
20
• Exemplo 1: Fatorial de um número
RECURSIVIDADE
21
• Exemplo 1: Fatorial de um número
RECURSIVIDADE
22
• Pilha de Execução: fat(5)
Fonte: Embarcados. Disponível em https://embarcados.com.br/recursividade/
https://embarcados.com.br/recursividade/
RECURSIVIDADE
23
• Exemplo 1: Fatorial de um número: Recursivo vs Iterativo
RECURSIVIDADE
24
• Código RECURSIVO vs Código ITERATIVO
• Tanto recursão quanto iteração usam repetição
– Iteração: comandos de repetição (for, while, do while, ...)
– Recursão: chamadas repetitivas a uma rotina
• Ambas precisam de um teste de terminação
– Iteração: quando uma expressão lógica de teste é falsa
– Recursão: quando se atinge o caso trivial
– Ambas podem entrar em loop...
• no caso da iteração se o teste nunca se tornar falso e no caso da recursão se o
problema não for reduzido de forma que convirja para o caso trivial
RECURSIVIDADE
25
• Código RECURSIVO vs Código ITERATIVO
• Gasto computacional (complexidade) da recursão é maior na
maioria das vezes!
– Vale a pena?
– É menos custoso implementar a mesma função de forma iterativa?
RECURSIVIDADE
26
• Código RECURSIVO vs Código ITERATIVO
• Gasto computacional (complexidade) da recursão é maior na
maioria das vezes!
– Vale a pena?
– É menos custoso implementar a mesma função de forma iterativa?
• BORA TESTAR? Implementar os algoritmos do Slide 23 e
verificar o tempo de execução de cada um usando como
entrada os números 5, 10 e 20!
RECURSIVIDADE
27
• Exemplo 2: Sequencia de Fibonacci
CASOS BASE
CASO RECURSIVO
RECURSIVIDADE
28
• Exemplo 2: Sequencia de Fibonacci
RECURSIVIDADE
29
• Exemplo 2: Sequencia de Fibonacci
• Implementem esse algoritmo em uma linguagem de
programação real!
RECURSIVIDADE
30
• Exemplo 2: Sequencia de Fibonacci
– Note que, para n > 1, cada chamada
causa 2 novas chamadas de Fib
• Número total de chamadas cresce
exponencialmente
– Para Fib(5), são feitas 14 chamadas
da função
• Fib(0) e Fib(2) são chamadas 3 vezes
• Fib(1) é chamada 5 vezes
– Para Fib(25), são feitas 242.784
chamadas recursivas (!!!)
RECURSIVIDADE
31
• Exemplo 2: Sequencia de Fibonacci
• E uma versão iterativa dessa sequência, como vocês pensariam?
RECURSIVIDADE
32
PRÁTICA
33
• Implemente soluções recursivas e iterativas para resolver os
problemas a seguir:
• Calcular xn, sendo n > 0
• Imprimir todos os elementos de um vetor
• Somar os elementos de uma lista de inteiros
• Transformar um número n >= 0 em binário
CCT0608 ALGORITMOS AVANÇADOS
34
• Dúvidas?
• Fiquem à vontade para entrar em contato no 
RONEY.LIRASALE@professores.estacio.br
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35