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