Recursividade

Prévia do material em texto

Recursividade
Raphael Winckler de Bettio
 
Recursividade
● Qual o valor da 
variável i impressa 
na linha printf?
● Porque?
 
Recursividade
I = 0
Pilha de Execução
 
Recursividade
I = 0
I = 1
Pilha de Execução
 
Recursividade
● Uma função 
recursiva é uma 
função que chama 
a sí própria.
● O que acontece 
nesse caso?
● Executem um teste 
de mesa para chegar 
a uma conclusão!
 
Recursividade
● Toda função 
recursiva deve ter 
uma condição de 
parada.
 
Recursividade
● Construir a pilha de 
execução desse 
algoritmo.
● Função 
Instrumentada;
 
Recursividade
● Função recursiva: Função que chama a sí 
própria;
● Condição de parada: Condição que faz com 
que a função recursiva tenha um fim;
● Função instrumentada: Método que pode ser 
utilizado para facilitar a visualização da pilha 
de execução;
● Existem diversos problemas computacionais 
que podem ser resolvidos com funções 
recursivas.
 
Recursividade
● Fatorial (!)
n! =
n(n-1)!, se n >= 1
1, se n = 0
 
Recursividade
● Fatorial ● Construa a pilha de 
execução para o 
algoritmo.
● Qual o resultado?
 
Recursividade
● Fatorial
Fatorial 4 = 24
Fat = 4 * fatorial (3) = 6
Fat = 3 * fatorial (2) = 2
Fat = 2 * fatorial (1)
 
Recursividade
● Fibonacci
– Descrita inicialmente por Leonardo de Pisa
– Utilizada em
● Mercado Financeiro;
● Teoria dos jogos;
● Etc..
● Construa um algoritmo recursivo que calcule o 
valor de fibonacci
f(n) =
0, se n = 0;
1, se n = 1;
f(n-1) + f(n-2)
 
Recursividade
● Fibonacci ● Para cada 
chamada existem 
duas chamadas;
● Pilha execução → 
Árvore de recursão
● Construa a Árvore 
de recursão
 
Recursividade
f(3)
f(2) + f(1) = 2
F(1) + f(0) = 1
f(3)
 
Bibliografia
● Roteiro Prático número 13 – Recursividade – 
Universidade Federal de Itajubá: Claudia, 
Denílson, Fabiana, Fernando, Juliano, Natália, 
Raquel, Rodrigo, Sandro e Walter;
● Guimarães, A. de M., Lages, N. A. de C. 
Algoritmos e Estruturas de Dados. 1 ed. Rio 
de Janeiro: LTC, 2008.
	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