O que é uma recursão?

De acordo com a Wikipedia, uma recursão é definida como:

“... um método de resolver um problema onde a solução depende de soluções para instâncias menores do mesmo problema”

Vamos tentar entender essa afirmação usando um exemplo e, em seguida, tirar algumas conclusões.

A filosofia por trás da recursão:

Vejamos um problema como o cálculo de 5! (fatorial). Para saber o resultado de 5! precisamos calcular:

5! = 5 *4 *3 *2 *1

5! = 5 *4! = 5 *4 *3 *2 *1

Se tivéssemos que escrever o algoritmo para esta operação, ele se pareceria com:

factorial = n * (n -1)!

Recursão e loop for são intercambiáveis. Parece uma abordagem intuitiva olhar primeiro para um loop for em ação para entender o que está acontecendo.

Primeiro, vamos criar a função de loop for e, em seguida, vamos interrompê-la.

def factorial_loop(n):
    
    fact = 1
    for i in range(1, n+1):
        fact *=i
        
    return fact
factorial_loop(5)
'Out: 120'

• A função recebe um número n, no nosso caso, o número 5
• Definimos função de intervalo para começar de 1 a n + 1 a fim de incluir (5) e descartar 0 porque 0 * qualquer número = 0
• Definimos "fato = 1" para o valor inicial porque qualquer número multiplicado por 1 permanece inalterado (1 * 1 = 1)
• Dentro do " for loop " pegamos o resultado anterior e o multiplicamos pelo próximo número (i)

# 1 Iteration:
def factorial_loop(5):
    
    fact = 1
    for i=1 in range(1, 6):
        1 *= 1
        
    return 1
# 2 Iteration:
def factorial_loop(5):
    
    fact = 1
    for i=2 in range(1, 6):
        1 *= 2
        
    return 2
# 3 Iteration:
def factorial_loop(5):
    
    fact = 2
    for i=3 in range(1, 6):
        2 *= 3
        
    return 6
# 4 Iteration:
def factorial_loop(5):
    
    fact = 6
    for i=4 in range(1, 6):
        6 *= 4
        
    return 24
# 5 Iteration:
def factorial_loop(5):
    
    fact = 24
    for i=5 in range(1, 6):
        24*= 5
        
    return 120

A recursão fará o mesmo trabalho que o loop for, entretanto a sintaxe da recursão é um pouco diferente e pode não ser muito intuitiva à primeira vista, mas iremos decompô-la passo a passo.

def factorial_recursion(n):
    if n <= 1:
        return 1
    else:
        return n * factorial_recursion(n-1)
        
factorial_recursion(5)

1. Instrução IF / ELSE… A recursão cria um loop, este loop deve ter uma condição para parar. Por esse motivo, toda recursão tem uma instrução IF / ELSE. Em nosso caso, quando n atinge o valor 1, retornamos o valor um e interrompemos a recursão (loop).
2. Para criar uma recursão, uma função deve chamar a si mesma. Você pode ver na parte else: da função.
3. Quando a função está chamando a si mesma, precisamos ter certeza de que ela alcançará nosso caso base (n ≤ 1) para parar. No nosso caso, decrementamos n por um Eg: factorial_recursion (n-1)

Exemplo 2:

Divida uma palavra em grupos de 2 letras. Se a palavra tiver letras irregulares, adicione “_” à última letra. A saída deve ser uma lista com grupos de duas letras do tipo string.

• A recursão continua até len (s) = 1.
• Na solução, começamos a fatiar duas letras e instruímos o python a continuar até que o caso básico seja atingido.

def split_string_recursion(s):
    if len(s) == 0:
        return ''
    elif len(s) == 1:
        return [s + '_']
    else:
        return [s[:2]] + split_string_recursion(s[2:])
split_string_recursion('amazing')
'out: ['am', 'az', 'in', 'g_']'

def reverse_string_recursive(s):
    if len(s) == 0:
        return ''
    else:
        return reverse_string_recursive(s[1:]) + s[0]
    
reverse_string_recursive('amazing')

Crie uma matriz fibonacci usando recursão.

def fib_recursive(n):
    if n <=2:
        return 1
    else:
        return fib_recursive(n-1) + fib_recursive(n-1)
    
fib_recursive(5)