02 Recursividade

Universidade Estadual de Mato Grosso do Sul
Bacharelado em Ciência da Computação
Algoritmos e Estruturas de Dados II
Prof. Fabrício Sérgio de Paula

Tópicos
 Conceitos
 Exemplos
 Exercícios

Conceitos
 Procedimento recursivo: possui em sua descrição uma ou

mais chamadas a si mesmo
 Chamada recursiva: realizada a partir do próprio

procedimento
 Chamada externa: realizada de um local externo ao procedimento  Procedimento não recursivo: todas as chamadas são

externas, ou seja, não há chamada recursiva

Conceitos
 Para todo procedimento recursivo, existe um

correspondente não recursivo
 Nem sempre é fácil eliminar recursões

 Vantagens da recursividade
 Procedimentos mais concisos: objetivos, curtos


Para alguns problemas o uso da recursão é natural: fatorial,
Fibonacci, Torre de Hanói

 Demonstração da corretude/correção mais fácil


Indução matemática

 Desvantagem: pode ser menos eficiente
 Empilhamento/desempilhamento

Exemplos
1
𝑠𝑒 𝑛 ≤ 1
1. Cálculo de 𝑛! =
𝑛 𝑛 − 1 ! 𝑠𝑒 𝑛 > 1

versão equivalente:

Fat(i) se i ≤ 1 então retorne 1; senão retorne i*Fat(i-1);

Exemplos
1. (cont.)
Condição de parada

Fat(i) se i ≤ 1 então retorne 1; senão retorne i*Fat(i-1);

Chamada externa

Chamada recursiva

FunçãoXYZ(...)
...
Leia n; fat_n :=Fat(n);

soma := fat_n + .... ;
Imprima soma;
....

Exemplos
1. (cont.)
 Exemplo de execução de Fat(3)
Fat(3)

Fat(2)
Fat(1)
retorne 1 retorne 2*1 retorne 3*2

Exemplos
2. Cálculo do 𝑛-ésimo número de Fibonacci, onde 𝑛 ∈ ℕ.

𝑛
F(𝑛) =
𝐹 𝑛 − 1 + 𝐹(𝑛 − 2)

𝑠𝑒 𝑛 ≤ 1
𝑠𝑒 𝑛 > 1

Fib(n) se n ≤ 1 então retorne n; senão retorne Fib(n-1) + Fib(n-2);

Exemplos
2. (cont.)
 Exemplo de execução de Fib(3)
Fib(3)
Fib(2)
Fib(1)
retorne 1
Fib(0)
retorne 0 retorne 1+0
Fib(1)
retorne 1 retorne 1+1

Exemplos
3. O Problema da Torre de Hanói com 𝑛 discos.

Exemplos
3. (cont.)

Exercícios
1. Desenvolva

algoritmos recursivos seguintes situações a seguir:

a.
b.
c.
d.
e.
f.

para

as

Inverter uma seqüência com n