Enviar um café pro programador

Recursividade em Python: Somatório e Fatorial Usando Função Recursiva

"Para aprender recursividade, você precisa saber recursividade..."

Essa frase pode soar bem louca, a primeira vista.
Mas quando te ensinarmos melhor o conceito de uma função recursiva, ela vai fazer total sentido para você.


Somatório na Matemática

Definimos como somatório, uma função matemática representada por:
f(x) = 1 + 2 + 3 + ... + (x-1) + x

Ou seja, somamos tudo de 1 até o valor x.
Exemplos:
f(4) = 1 + 2 + 3 + 4 = 10
f(5) = 1 + 2 + 3 + 4 + 5 = 15
f(6) = 1 + 2 + 3 + 4 + 5 + 6 = 21
etc

Porém, note uma coisa:
f(5) = f(4) + 5 = 10 + 5 = 15
f(6) = f(5) + 6 = 15 + 6 = 21

Ou seja, podemos generalizar:
f(x) = f(x-1) + x

Agora, calma.
Vamos ver o motivo dessa teoria toda.

Função Recursiva em Python

Dizemos que uma função é recursiva quando, dentro dela, ela chama ela mesma.
Porém, com outro argumento.

No exemplo anterior, passamos um valor x para a função recursiva.
Ela soma x com o valor de f(x-1), ou seja, ela vai chamar ela mesma, mas ao invés de passar o parâmetro x, vai passar o parâmetro x-1.

E essa função que recebeu x-1 vai somar (x-1) com f(x-2), ou seja, chamou ela mesma novamente, mas agora com um parâmetro (x-2). E por aí vai.

Onde termina isso?
Ora, com f(1) = 1




Somatório com Função Recursiva

Se ainda está perdido, tudo bem, é pra estar mesmo.
Mas vamos resolver um exemplo que vai te fazer entender melhor.

Crie um script que peça um inteiro positivo para o usuário.
Em seguida, exiba a soma do somatório de 1 até esse número.

Nosso código fica assim:

def somatorio(x):
    if x==1:
        return 1
    else:
        return x + somatorio(x-1)

while True:
    x = int(input("Somatorio de 1 até: "))
    print("Soma: ",somatorio(x) )

Agora vamos ver o que faz linha por linha.

Primeiro, definimos nossa função, vai se chamar somatorio e recebe um valor como parâmetro, o x.
A primeira coisa a se fazer numa função recursiva é definir onde ela vai parar, ou seja, dizer "ei, chega, aqui você vai parar de invocar você mesma"

Nesse caso, é quando o argumento for 1, aí o somatório é 1 e retorna 1.
Se não for argumento 1, ai cai no ELSE, então o retorno é o próprio argumento x somado de somatorio(x-1).

Lembra da função f(x)? Agora ela se chama é somatorio:
somatorio(x) = x + somatorio(x-1)

E prontinho, no cordo do script pedimos um número ao usuário.
Por exemplo, se x =4 :

Primeiro return: 4 + somatorio(3)
Segundo return: 4 + 3 + somatorio(2)
Terceiro return: 4 + 3 + 2 + somatorio(1)
Quarto return: 4 + 3 + 2 + 1 = 10




Fatorial com Recursividade

Para calcularmos o fatorial de um inteiro n, basta multiplicarmos todos os números de 1 até o próprio n. Expressamos o fatorial de n por n !

Por exemplo:

  • 4! = 4*3*2*1 = 24
  • 5! = 5*4*3*2*1 = 120
  • 6! = 6*5*4*3*2*1 = 720


Agora note duas coisas:
5! = 5 * 4!
6! = 6 * 5!

Ou seja:
n! = n * (n-1)!

Implementando isso em código Python:

def fatorial(x):
    if x==1:
        return 1
    else:
        return x * fatorial(x-1)

while True:
    x = int(input("Fatorial de: "))
    print("Fatorial: ",fatorial(x) )

O ponto de parada é quando a função recebe 1 como argumento.
Aí ela retorna 1.

Se não for 1, retorna o valor do argumento x multiplicado pelo fatorial de (x-1)!

Exercício Proposto: Fibonacci

A série de Fibonacci é uma sequência de números, cujos dois primeiros são 0 e 1. O termo seguinte da sequência é obtido somando os dois anteriores. Faça uma script em Python que solicite um inteiro positivo ao usuário, n. Então uma função exibe todos os termos da sequência até o n-ésimo termo. Use recursividade.

Solução:
Gerar a sequência de Fibonacci

Recursividade em Programação Python - o que é

7 comentários:

  1. Acredito que tenha um erro no exercício de fatorial,pois o ponto de parada da função(1º if) tem que ser 0, pois fatorial de 0 é 1

    Parabéns pelo curso!

    ResponderExcluir
    Respostas
    1. Sou iniciante, posso estar errado, mas acredito que a correção seria usar um elif conforme abaixo:

      def fatorial(x):

      if x == 1:
      return 1
      elif x==0:
      return 1
      else:
      return x * fatorial(x-1)
      while True:
      x = int(input("Fatorial de: "))
      print("Fatorial do número escolhido é: ",fatorial(x) )
      fatorial(x)

      Excluir
    2. Não será necessário você validar com ELIF pois a validação é implicita, ou seja, caso o if não seja 1, cai no else e executa a funcão

      Excluir
  2. #codigo refatorado

    def fatorial(n):
    if n == 0:
    return 1
    return n * fatorial(n - 1)

    while True:
    x = int(input("Fatorial de: "))
    print("Fatorial: ",fatorial(n) )

    ResponderExcluir
  3. Se alguém estiver procurando como eu fazer o somatório de uma lista, o código se encontra logo abaixo:
    def somar(lista):
    if len(lista) == 1:
    return int(lista[0])
    else:
    return int(lista[0]) + somar(lista[1:])

    lista = input("Digite numeros: ").replace(" ", "").split(",")

    print(somar(lista))

    ResponderExcluir
    Respostas
    1. Bacana anonimo, mas vale lembrar que o curso tem um roteiro, e neste ponto ainda não ensinamos lista.

      Excluir