<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Introdução à Programação em Python
Recursão
Em um programa é muito comum chamarmos uma função dentro de uma outra função.
Step1:  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
Step2:  Uma outra forma de cálcular o fatorial é
Step3:  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
Step4:  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
Step5:  Funcionou? Verifique
Step6:  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.
Step7:  Atividade 1
A sequência de Fibonacci é uma série que segue a seguinte regra
Step9:  Faça um código que calcule a sequência de Fibonacci utilizando recursão.
Step10:  Atividade 2
Pode-se calcular o máximo divisor comum (MDC) entre dois números inteiros positivos utilizando o algoritmo de Euclides.
Veja a implementação do algoritmo de Euclides abaixo
<ASSISTANT_TASK:>
Python Code:
def imprime(i):
    print (i)
def imprimeLista(l):
    for e in l:
        imprime (e)
imprimeLista([1, 3, 5, 7])
Explanation: Introdução à Programação em Python
Recursão
Em um programa é muito comum chamarmos uma função dentro de uma outra função.
End of explanation
def fatorial(n):
    fat = 1
    while n > 1:
        fat *= n
        n -= 1
    return fat
print(fatorial(3))
print(fatorial(6))
Explanation: 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:
End of explanation
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)
Explanation: 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:
python
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:
python
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... :'(
End of explanation
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))
Explanation: 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:
```python
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.
End of explanation
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")
Explanation: 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.
```python
def hanoi():
    # Parte TRIVIAL
    if numero_de_discos == 1:
        <mover_o_disco_da_origem_para_o_destino>
# Parte GERAL
else:
    hanoi(&lt;mover_n-1_discos_da_origem_para_o_auxiliar)
    &lt;mover_o_disco_da_origem_para_o_destino&gt;
    hanoi(&lt;mover_n-1_discos_do_auxiliar_para_o_destino)
```
Veja a implmementação correta abaixo.
End of explanation
from time import sleep
def contadorRegressivo(n):
    if n == 0:
        print ("BOOM!")
    else:
        print (str(n) + "s")
        sleep(1)
        contadorRegressivo(n-1)
contadorRegressivo(3)
Explanation: 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!
End of explanation
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)
Explanation: 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.
End of explanation
n1 = 1
n2 = 1
for i in range(1, 20):
    n1, n2 = n2, (n1+n2)
    print (n1)
print ("...")
Explanation: Atividade 1
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:
End of explanation
def Fibonacci(n):
    
        Código
    
Fibonacci(5)
Fibonacci(7)
Explanation: Faça um código que calcule a sequência de Fibonacci utilizando recursão.
End of explanation
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))
Explanation: Atividade 2
Pode-se calcular o máximo divisor comum (MDC) entre dois números inteiros positivos utilizando o algoritmo de Euclides.
Veja a implementação do algoritmo de Euclides abaixo:
End of explanation
<END_TASK>