In [1]:
# Ignore esse código inicial, é apenas para preparar a página!
from IPython.display import YouTubeVideo, HTML, Image, display
css_file = 'http://professor.ufabc.edu.br/~fernando.teubl/resources/css/ipython-notebook.css'
#HTML(open(css_file, "r").read())
import requests; HTML(requests.get(css_file).text)
Out[1]:
Em um programa é muito comum chamarmos uma função dentro de uma outra função.
In [2]:
def imprime(i):
print (i)
def imprimeLista(l):
for e in l:
imprime (e)
imprimeLista([1, 3, 5, 7])
Entretanto, nada impede de uma função chamar ela mesma!
Como exemplo, vamos pensar na função fatorial. O fatorial de 3 e 6 respectivamente pode ser calculado conforme descrito abaixo:
$3! = 3 \times 2 \times 1 = 6$
$6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720$
De forma genérica, podemos calcular o fatorial como:
$n! = n \times (n-1) \times (n-2) \times \ldots \times 3 \times 2 \times 1$
Deste modo, podemos facilmente implementar uma função para calcular o fatorial:
In [3]:
def fatorial(n):
fat = 1
while n > 1:
fat *= n
n -= 1
return fat
print(fatorial(3))
print(fatorial(6))
Uma outra forma de cálcular o fatorial é:
$3! = 3 \times 2! = 3 \times 2 = 6$
$6! = 6 \times 5! = 6 \times 120 = 720$
De modo genérico, temos:
$n! = n \times (n-1)!$
Pela equação acima, podemos deduzir que qualquer fotorial pode ser calculado como o seu valor multiplicado pelo fatorial do seu valor subtraído por um.
E quanto vale o fatorial de $n-1$?
R: $(n-1)! = (n-1) \times (n-2)!$
Vamos propor uma função que tenta calcular a equação acima:
def fatorial(n)
return n * (n-1)!
Entretanto, como podemos calcular o (n-1)!?
A função fatorial(n) que estamos desenvolvendo não tem este objetivo?
Então, por que não utilizar esta própria função para calcular o fatorial de (n-1)?
Neste sentido, teremos:
def fatorial(n)
return n * fatorial(n-1)
Entretanto, existe um erro grave nesta função: se a função chama ela mesma, quando esta função termina e retorna?
R: Da forma que está, não termina... :'(
In [0]:
import sys
sys.setrecursionlimit(50)
# Ao executar esta função, o python ficará processando até
# ocorrer um estouro de pilha de memória (stack overflow).
def fatorial(n):
return n * fatorial(n-1)
print(fatorial(6))
sys.setrecursionlimit(1000)
O principal problema do exemplo anterior é que a função não sabe quando terminar!
Deste modo, toda função recursiva precisa ter uma condição de término.
Toda função recursiva deve ter uma lógica similar ao demonstrado a seguir:
def funcRecursiva():
# Parte TRIVIAL
if <conhecemos_a_resposta>:
return <resposta>
#parte GERAL
else:
# utilizamos a recursão
return funcRecursiva()
No caso do fatorial, sabemos que o fatorial de 0 é 1, certo? Esta é a nossa parte TRIVIAL.
In [ ]:
def fatorial(n):
# Parte TRIVIAL
if n == 0:
return 1
# Parte GERAL ou RECURSIVA
else:
return n * fatorial(n-1)
print(fatorial(3))
print(fatorial(6))
print(fatorial(20))
Apesar de parecer que a recursão complica a solução, conforme demosntrado no fatorial (exemplo anterior), uma função recursiva pode facilitar a implementação de muitos problemas, pois permite dividir o problema em problemas menores para solucioná-lo.
Para entener melhor a motivação do uso da recursão, vamos pegar um exemplo mais complexo. Lembram da torre de Hanói?
Caso não lembre, clique aqui antes de continuar lendo.
Como podemos construir um algoritmo para solucionar a torre de Hanói?
Não é trivial. Mas podemos utilizar a recursão com o objetivo de dividir para conquistar.
A chave para resolver este problema é quebrar o desafio em desafios menores até que o desafio seja trivial. Neste caso, o trivial é quando temos apenas um único disco para mover (neste caso, basta mover o disco direto).
Se queremos mover os discos da haste 1 para a haste 3, e existem $n$ discos na haste 1, podemos mover os $n-1$ discos para a haste auxiliar 2, mover o último disco da haste 1 para a haste 3 e, então, levar os $n-1$ discos da haste auxiliar 2 para a haste 3. Veja a figura a seguir:
Ou seja, a parte TRIVIAL da nossa recursão é mover um disco da haste 1 para a haste C. A parte GERAL (recursiva) vai ser mover os $n-1$ discos da haste 1 para a haste 2 e depois mover da haste 2 para a haste 3.
def hanoi():
# Parte TRIVIAL
if numero_de_discos == 1:
<mover_o_disco_da_origem_para_o_destino>
# Parte GERAL
else:
hanoi(<mover_n-1_discos_da_origem_para_o_auxiliar)
<mover_o_disco_da_origem_para_o_destino>
hanoi(<mover_n-1_discos_do_auxiliar_para_o_destino)
Veja a implmementação correta abaixo.
In [5]:
def hanoi(num_discos, hasteOrigem, hasteDestino, hasteAuxiliar):
# Parte TRIVIAL
if num_discos == 1:
print ("Mover o disco da haste " + hasteOrigem + " para a haste " + hasteDestino + ".")
# Parte GERAL
else:
hanoi(num_discos-1, hasteOrigem, hasteAuxiliar, hasteDestino)
print ("Mover o disco da haste " + hasteOrigem + " para a haste " + hasteDestino + ".")
hanoi(num_discos-1, hasteAuxiliar, hasteDestino, hasteOrigem)
hanoi(4, "A", "C", "B")
Funcionou? Verifique:
Agora tente desenvolver uma outra solução para o problema da torre de Hanói sem utilizar a recursão. Pense um pouco e você perceberá que é muito difícil (porém não impossível).
Agora que entendemos a ideia da recursão, vamos analizar passo-a-passo o que acontece com o programa durante uma recursão, do ponto de vista computacional.
Vamos começar com uma função fotorial bem simples: um contador regressivo!
In [6]:
from time import sleep
def contadorRegressivo(n):
if n == 0:
print ("BOOM!")
else:
print (str(n) + "s")
sleep(1)
contadorRegressivo(n-1)
contadorRegressivo(3)
Neste exemplo, ao chamar a função contadorRegressivo(n = 3), o Python irá verificar que n é diferetne de 0, imprimir "3s", dormir por um segundo e chamar a função contadorRegressivo(n = 2).
A função contadorRegressivo(n = 2) irá seguir seguir o mesmo roteiro, mas com o valor de n igual a 2.
O mesmo ocorre com a função contadorRegressivo(n = 1).
Por fim, a função contadorRegressivo(n = 0) cai na parte trivial da recursão, o que faz imprimir "BOOM!" e retornar (sem recursão).
Neste momento, a função contadorRegressivo(n = 0) retorna para a função contadorRegressivo(n = 1), que retorna para a função contadorRegressivo(n = 2) que, por fim, retorna para a função contadorRegressivo(n = 3).
Note que embora o nome da função seja a mesma, os parâmetros são diferentes, ou seja, embora esteja executando o memso código, todos os valores da função são diferentes, pois a instância de cada função é diferente.
O código abaixo imprime é similar ao exemplo anterior, mas imprime passo a passo a recursão.
In [7]:
space = ""
from time import sleep
def contadorRegressivo(n):
space = "||||" * (3-n)
print(space + "contadorRegressivo(n = {}) # Chamado pela {}ª vêz!".format(n,4-n))
if n == 0:
print(space + " if {} == 0: (VERDADEIRO)".format(n))
print(space + " print (\"BOOM!\")")
else:
print(space + " if {} == 0: (FALSO)".format(n))
print(space + " else:")
print(space + " print (str(n = {}) + \"s\")".format(n))
print(space + " sleep(1)")
print(space + " contadorRegressivo(n-1) # Recursão!")
contadorRegressivo(n-1)
if n < 3:
print(space + " # Retornando para contadorRegressivo(n = {})".format(n+1))
else:
print(" # Fim da execução")
contadorRegressivo(3)
A sequência de Fibonacci é uma série que segue a seguinte regra: $x_{n}=x_{n-1}+x_{n-2}$, sendo que $x_{1} = 1$ e $x_{2} = 1$. Os primeiros elementos da sequência de Fibonacci são: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, ...
Um possível código para imprimir a sequencia de Fibonacci é apresentado abaixo:
In [8]:
n1 = 1
n2 = 1
for i in range(1, 20):
n1, n2 = n2, (n1+n2)
print (n1)
print ("...")
Faça um código que calcule a sequência de Fibonacci utilizando recursão.
In [9]:
def Fibonacci(n):
"""
Código
"""
Fibonacci(5)
Fibonacci(7)
In [10]:
def Euclides (a, b):
while b != 0:
a, b = b, a % b
return a
print(Euclides(10, 8))
print(Euclides(21, 13))
print(Euclides(63, 108))
Modifique o algoritmo acima de modo a utilizar recursão.