Recursão

Ao escrever programas, normalmente chamamos funções diferentes para executar tarefas muito específicas. Chamamos sqrt para calcular a raiz quadrada de um número, ou as funções max e min para encontrar o valor máximo ou mínimo de um conjunto de números. Recursão é o processo de chamar a mesma função a partir dela própria. Assim, se implementámos uma função de nome f e, em algum ponto do corpo de f, essa função chamar novamente f (geralmente com argumentos diferentes), isso seria uma chamada recursiva:

def f(n):                                   # Define uma função chamada f
    print(f'f() called with argument {n}')  # Imprime em cada chamada (para demonstração)
    if n <= 0:                              # Pára se n for negativo
        print('Let\'s stop here...')
    else:                                   # Caso contrário, chama f com um número mais pequeno
        f(n - 1)

f(10)

Isto é o que o programa iria imprimir

f() called with argument 10
f() called with argument 9
f() called with argument 8
f() called with argument 7
f() called with argument 6
f() called with argument 5
f() called with argument 4
f() called with argument 3
f() called with argument 2
f() called with argument 1
f() called with argument 0
Let's stop here...

Este é um exemplo simples que demonstra como se pode implementar uma função recursiva de forma bastante básica. Em cenários mais reais, normalmente fazemos alguns cálculos dentro destas funções e retornamos resultados em vez de apenas imprimir mensagens.

Nos problemas de algoritmia, a recursão pode ser muito útil, especialmente no tratamento de grafos, algoritmos de ordenação avançados ou na técnica de backtracking, que veremos mais tarde no curso. Problemas que requerem recursividade são muito comuns, e por vezes é muito mais simples implementar uma solução recursiva do que uma solução iterativa com ciclos.

Video preview — Um vídeo de Reducible – 5 Simple Steps for Solving Any Recursive Problem

O processo de resolver um problema grande, dividindo-o recursivamente em problemas cada vez mais pequenos até chegar ao caso mais simples, pode ser percebido de forma mais clara através do conceito conhecido como “salto de fé recursivo”.

Salto de Fé Recursivo

Ao implementar uma solução recursiva para um problema, costuma-se criar uma função que, em algum ponto, chama a si própria. A parte em que a função se chama novamente é geralmente chamada de chamada recursiva.

A grande vantagem das soluções recursivas é que podemos assumir que a função funciona corretamente para alguns argumentos simples e, a partir daí, implementar o comportamento correto para os casos mais complexos. Assim como chamamos outras funções como sqrt, max ou abs, podemos assumir que a função funciona para alguns valores menores ou mais simples e usar esses resultados para construir a resposta atual.

💡

A única exigência é garantir que a função chega ao caso base (o caso mais simples). Caso contrário, teríamos uma função recursiva que correria indefinidamente, provocando um StackOverflow!

Como demonstração de como se pode realizar um cálculo dentro de uma função recursiva, podemos tentar calcular a soma de todos os números de 0, 1, 2, …, n dado um número n.

Vamos implementar a função sum passo a passo. O primeiro passo é garantir que a função funciona corretamente para o caso mais simples (contar adequadamente a soma se n for 0 ou 1):

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:         # Se n for 0 => a soma é 0
        return 0       # Termina a execução da função aqui
    if n == 1:         # Se n for 1 => a soma é 1
        return 1       # Termina a execução da função aqui

print(sum(1))          # sum(1) -> 1
print(sum(0))          # sum(0) -> 0
print(sum(2))          # sum(2) -> None (porque ainda não implementámos esta parte)

Com esta parte da função, já podemos usar o facto de sum(0) devolver sempre 0 corretamente, enquanto sum(1) devolverá sempre 1. A função funcionará corretamente mesmo que chamemos a função sum com argumentos 0 ou 1 a partir da própria função sum.

Assim, podemos avançar mais um passo e implementar a função sum para n = 2 e n = 3, utilizando os resultados de sum(1) e sum(0):

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:             # Se n for 2, somamos 2 ao resultado de sum(1) já implementado
        return n + sum(1)  # ou n + sum(n - 1)
    if n == 3:             # Se n for 3, somamos 3 ao resultado de sum(2) já implementado
        return n + sum(2)  # ou n + sum(n - 1)

print(sum(1))          # sum(1) -> 1
print(sum(0))          # sum(0) -> 0
print(sum(2))          # sum(2) -> sum(1) -> 3
print(sum(3))          # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4))          # sum(4) -> None (porque ainda não implementámos esta parte)

Desta forma, é claro que a função sum funciona corretamente para os casos pequenos, como n igual a 0, 1, 2 ou 3.

Tendo isto, podemos implementar a função para outros valores de n maiores que 3. A única exigência é chegarmos a esses valores de n (0, 1, 2 ou 3) ao chamar a função sum a partir dela própria. Assim, para valores maiores de n, como 4, 5 ou 6, por exemplo, podemos implementar a função sum usando o facto de que, para calcular sum(4), basta somar 4 ao resultado de sum(3), enquanto para calcular sum(5) basta somar 5 ao resultado de sum(4):

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return n + sum(1)
    if n == 3:
        return n + sum(2)
    # Para todos os outros casos (4, 5, 6, ...)
    return n + sum(n - 1)  

print(sum(2))          # sum(2) -> sum(1) -> 3
print(sum(3))          # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4))          # sum(4) -> sum(3) -> sum(2) -> sum(1) -> 10
# ...

Os elementos-chave de uma função recursiva são:

Caso base: Uma condição que interrompe a recursão. Sem isto, a função chamaria a si própria indefinidamente, originando um loop infinito. Neste exemplo, é quando n == 0 e n == 1.

Passo recursivo: Onde a função se chama a si própria, geralmente com um argumento diferente. Aqui, é sum(n - 1).

Dado que as chamadas para n == 1, n == 2 e n == 3 são, na essência, iguais às chamadas para n == 4, n == 5, etc., podemos simplificar ainda mais a função sum, mantendo apenas um caso base (quando n == 0):

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:
        return 0
    return n + sum(n - 1)  

print(sum(2))          # sum(2) -> sum(1) -> sum(0) -> 3
print(sum(3))          # sum(3) -> sum(2) -> sum(1) -> sum(0) -> 6
print(sum(4))          # sum(4) -> sum(3) -> sum(2) -> sum(1) -> sum(0) -> 10
# ...

Assim, com o salto de fé recursivo, assumimos/sabemos que a função funciona corretamente para casos mais pequenos e, a partir disso, construímos o resto da função com base nesses casos simples. Isso ajuda a perceber como funções recursivas funcionam e como podem ser implementadas.

💡

Chamar a função recursivamente é como chamar uma função completamente diferente que tens a certeza de que funcionará corretamente com os argumentos passados.

Desafio

Implementa uma função recursiva que calcule n! módulo .

Entrada

A entrada contém um único inteiro n (1 ≤ n ≤ 1000).

Saída

O programa deve imprimir o resultado de n! módulo .

Exemplos

Entrada	Saída
5	120
10	3628800

Salto de Fé Recursivo

Desafio

Entrada

Saída

Exemplos

Constraints

To check your solution you need to sign in

Sign in to continue