MC102 – Aula 26
Recursão
Instituto de Computação Unicamp
02 de Junho de 2015
Recursão
Uma função é dita recursiva quando dentro do seu código existe
uma chamada para si mesma
Exemplo
Cálculo do fatorial de um número:
1
𝑓𝑎𝑡𝑜𝑟𝑖𝑎𝑙 𝑛 =
𝑛 ∗ 𝑓𝑎𝑡𝑜𝑟𝑖𝑎𝑙 𝑛 − 1
𝑠𝑒 𝑛 = 0
𝑠𝑒 𝑛 > 0
Fatorial
1
𝑓𝑎𝑡𝑜𝑟𝑖𝑎𝑙 𝑛 =
𝑛 ∗ 𝑓𝑎𝑡𝑜𝑟𝑖𝑎𝑙 𝑛 − 1
0! = 1
1! = 1 * 1
2! = 2 * 1
3! = 3 * 2 * 1
4! = 4 * 3 * 2 * 1
5! = 5 * 4 * 3 * 2 * 1
𝑠𝑒 𝑛 = 0
𝑠𝑒 𝑛 > 0
Função Iterativa
Função Iterativa
Fatorial
1
𝑓𝑎𝑡𝑜𝑟𝑖𝑎𝑙 𝑛 =
𝑛 ∗ 𝑓𝑎𝑡𝑜𝑟𝑖𝑎𝑙 𝑛 − 1
0! = 1
1! = 1 * 1
2! = 2 * 1
3! = 3 * 2 * 1
4! = 4 * 3 * 2 * 1
5! = 5 * 4 * 3 * 2 * 1
𝑠𝑒 𝑛 = 0
𝑠𝑒 𝑛 > 0
0! = 1
1! = 1 * 0!
2! = 2 * 1!
3! = 3 * 2!
4! = 4 * 3!
5! = 5 * 4!
Fatorial
1 5! = 5 * 4!
2
4! = 4 * 3!
3
3! = 3 * 2!
4
2! = 2 * 1!
5
1! = 1 * 0!
6
0! = 1
6’
5’
4’
3’
2’
1’
0! = 1
1! = 1 * 0!
2! = 2 * 1!
3! = 3 * 2!
4! = 4 * 3!
5! = 5 * 4!
=
=
=
=
=
1*1 = 1
2*1 = 2
3*2 = 6
4 * 6 = 24
5 * 24 = 120
Fatorial
1 5! = 5 * 4!
2
4! = 4 * 3!
3
3! = 3 * 2!
4
2! = 2 * 1!
5
1! = 1 * 0!
6
0! = 1
120
Fatorial
1
𝑓𝑎𝑡𝑜𝑟𝑖𝑎𝑙 𝑛 =
𝑛 ∗ 𝑓𝑎𝑡𝑜𝑟𝑖𝑎𝑙 𝑛 − 1
0! = 1
1! = 1 * 0!
2! = 2 * 1!
3! = 3 * 2!
4! = 4 * 3!
5! = 5 * 4!
𝑠𝑒 𝑛 = 0
𝑠𝑒 𝑛 > 0
Função Iterativa
Função Recursiva
Recursão e a Pilha de Execução (stack)
Supõe que façamos
• int x = fatorial(4);
Função Recursiva
X
Recursão e a Pilha de Execução (stack)
fatorial(4)
n
Retorno
X
4
Recursão e a Pilha de Execução (stack)
fatorial(4)
fatorial(3)
n
3
Retorno
n
Retorno
X
4
Recursão e a Pilha de Execução (stack)
fatorial(4)
fatorial(3)
fatorial(2)
n
2
Retorno
n
3
Retorno
n
Retorno
X
4
Recursão e a Pilha de Execução (stack)
fatorial(4)
fatorial(3)
fatorial(2)
fatorial(1)
n
1
Retorno
n
2
Retorno
n
3
Retorno
n
Retorno
X
4
Recursão e a Pilha de Execução (stack)
n
fatorial(4)
fatorial(3)
fatorial(2)
fatorial(1)
fatorial(0)
0
Retorno
n
1
Retorno
n
2
Retorno
n
3
Retorno
n
Retorno
X
4
Recursão e a Pilha de Execução (stack)
fatorial(4)
fatorial(3)
fatorial(2)
fatorial(1)
Retorno
n
1
1
Retorno
n
2
Retorno
n
3
Retorno
n
Retorno
X
4
Recursão e a Pilha de Execução (stack)
fatorial(4)
fatorial(3)
fatorial(2)
Retorno
n
1
2
Retorno
n
3
Retorno
n
Retorno
X
4
Recursão e a Pilha de Execução (stack)
fatorial(4)
fatorial(3)
Retorno
n
2
3
Retorno
n
Retorno
X
4
Recursão e a Pilha de Execução (stack)
fatorial(4)
Retorno
n
Retorno
X
6
4
Recursão e a Pilha de Execução (stack)
Supõe que façamos
• int x = fatorial(4);
Função Recursiva
Retorno
X
24
Recursão e a Pilha de Execução (stack)
Supõe que façamos
• int x = fatorial(4);
Função Recursiva
X
24
Elementos de uma função recursiva
• Condição de parada ou caso base ou caso trivial:
• É a parte da definição da função que não faz chamada recursiva
• Chamada recursiva propriamente dita ou passo de recursão:
• Deve resolver uma instância menor do mesmo problema
• Processamento de apoio ou processamento complementar:
• Demais processamentos que acompanham e/ou utilizam o que resulta
da chamada recursiva
Elementos de uma função recursiva
Exemplo: Condição de Parada
Elementos de uma função recursiva
Exemplo: Chamada recursiva a uma
instância menor
Elementos de uma função recursiva
Exemplo: Processamento de apoio
Importante
• Se não existir o caso base (condição de parada), o programa
entra em loop infinito
• Se a chamada recursiva não for aplicada a uma instância menor
do problema, o programa entra em um loop infinito
• Se um função recursiva ficar chamando a si mesma
indefinidamente (num loop infinito) o programa rapidamente
para por “estouro da pilha” (stack overflow)
Fibonacci
• O número de Fibonacci Fn para n>=0 é definido da seguinte maneira:
Fibonacci
• O número de Fibonacci Fn para n>=0 é definido da seguinte maneira:
Exercício 01 – Faça uma função recursiva para calcular o número de Fibonacci.
Função Recursiva
Fibonacci
• O número de Fibonacci Fn para n>=0 é definido da seguinte maneira:
Exercício 01
Faça um programa para imprimir a sequência de Fibonacci.
Função Recursiva
Sequência de Fibonacci
Exercício 2
O que faz o programa abaixo? Justifique!
Processamento de apoio?
Torre de Hanói
• A lenda diz que num templo perdido na Ásia uns monges estão
tentando mover 64 discos de tamanhos diferentes de um pino
para outro, usando um terceiro como auxiliar, de tal forma que:
• Nunca um disco maior é colocado sobre um menor
• De acordo com a lenda o mundo se acaba no momento que esta
tarefa é completada.
Torre de Hanói
• Estado inicial:
• pilha de discos ordenados pelo raio
• Objetivo:
• transferir a pilha de discos para uma das outras pilhas vazias
• Restrição:
• Mover um disco por vez
• Um disco de raio maior não pode estar sobre um disco de raio menor
Torre de Hanói
• Se o valor fornecido para o programa for 3, então a sequência de chamadas
e as saídas geradas são:
1
2
3
A
C
B
Torre de Hanói
• Se o valor fornecido para o programa for 3, então a sequência de chamadas
e as saídas geradas são:
3
1
2
A
C
B
Torre de Hanói
• Se o valor fornecido para o programa for 3, então a sequência de chamadas
e as saídas geradas são:
A
1
2
3
C
B
Torre de Hanói
• Se o valor fornecido para o programa for 3, então a sequência de chamadas
e as saídas geradas são:
1
2
3
A
C
B
• Ok, mas só podemos mover um disco por vez
• Como a pilha com os 2 discos menores foi parar no pino C, e depois no
pino B?
Torre de Hanói
• Se o valor fornecido para o programa for 3, então a sequência de chamadas
e as saídas geradas são:
1
2
3
A
C
B
Torre de Hanói
• Se o valor fornecido para o programa for 3, então a sequência de chamadas
e as saídas geradas são:
2
3
A
1
C
B
Movimento = 1
Mova o disco 1 do pino A para o pino B
Torre de Hanói
• Se o valor fornecido para o programa for 3, então a sequência de chamadas
e as saídas geradas são:
3
2
1
A
C
B
Movimento = 2
Mova o disco 2 do pino A para o pino C
Torre de Hanói
• Se o valor fornecido para o programa for 3, então a sequência de chamadas
e as saídas geradas são:
3
1
2
A
C
B
Movimento = 3
Mova o disco 1 do pino B para o pino C
Torre de Hanói
• Se o valor fornecido para o programa for 3, então a sequência de chamadas
e as saídas geradas são:
A
1
2
3
C
B
Movimento = 4
Mova o disco 3 do pino A para o pino B
Torre de Hanói
• Se o valor fornecido para o programa for 3, então a sequência de chamadas
e as saídas geradas são:
1
2
3
A
C
B
Movimento = 5
Mova o disco 1 do pino C para o pino A
Torre de Hanói
• Se o valor fornecido para o programa for 3, então a sequência de chamadas
e as saídas geradas são:
2
3
1
A
C
B
Movimento = 6
Mova o disco 2 do pino C para o pino B
Torre de Hanói
• Se o valor fornecido para o programa for 3, então a sequência de chamadas
e as saídas geradas são:
Quantidade mínima
de movimentos
1
2
3
A
C
M = 𝟐𝒏 − 𝟏
B
Movimento = 7
PARABÉNS!
Conseguiu mover os 3 discos com o mínimo de movimentos
Mova o disco 1 do pino A para o pino B
Número de
discos
Torre de Hanói
Para solucionar um Hanói de 3 discos, são necessários 7 movimentos
Para solucionar um Hanói de 4 discos, são necessários 15 movimentos
Para solucionar um Hanói de 5 discos, são necessários 31 movimentos
Para solucionar um Hanói de 6 discos, são necessários 63 movimentos
Para solucionar um Hanói de 7 discos, são necessários 127 movimentos
Para solucionar um Hanói de 15 discos, são necessários 32.767 movimentos
Para solucionar um Hanói de 64 discos, como diz a lenda, são necessários
18.446.744.073.709.551.615 movimentos.
Tarefa
• Torre de Hanói
Escrever um programa em C que calcula o movimento de n discos de
acordo com as regras estabelecidas
Material Baseado em:
• Estrutura de Dados Usando C (Livro)
• Slides do Prof. Daniel M. Martin