Recursividade: o que é e como funciona (com exemplos)

Neste artigo

1. Como funciona a recursividade?
2. O que é o fatorial?
3. Para que serve o fatorial na prática?
4. Exemplo de recursividade: o fatorial
5. O que acontece por dentro de uma função recursiva?
6. O que acontece se eu esquecer o caso base?
7. Agora é com você!
8. Recursividade ou laço de repetição?

Recursividade é quando uma função chama a si mesma para resolver um problema, dividindo-o em versões cada vez menores dele mesmo, até chegar a um caso tão simples que a resposta é imediata. Esse caso simples se chama caso base.

No artigo sobre funções, você viu que uma função pode ser chamada quantas vezes você quiser. A pergunta de hoje é: e se ela chamar ela mesma? Parece coisa de maluco, eu sei kkkk. Mas calma! No final das contas vai ser tudo bem simples.

Como funciona a recursividade?

Pense nas bonecas russas, aquelas que têm uma boneca menor dentro da outra. Para chegar na última, você abre uma, encontra outra igual, só que menor, abre de novo… até chegar na boneca que não abre mais. Essa última é o caso base. Depois você fecha todas, uma por uma, voltando pelo mesmo caminho.

Toda função recursiva tem duas partes, e você precisa das DUAS:

• Caso base: a condição que diz quando parar.
• Chamada recursiva: a função chama a si mesma, sempre com um problema menor que o anterior.

O que é o fatorial?

Antes do código, vale conhecer o personagem do nosso exemplo. O fatorial vem da matemática: é o produto de um número natural por todos os que vêm antes dele, até chegar no 1. O símbolo é o ponto de exclamação, colocado depois do número. Assim:

• 3! = 3 × 2 × 1 = 6
• 4! = 4 × 3 × 2 × 1 = 24
• 5! = 5 × 4 × 3 × 2 × 1 = 120

Não, a matemática não está gritando com você. O 5! é só o jeito curto de escrever a multiplicação inteira.

Um detalhe: por definição, 0! = 1. E repare como o fatorial cresce rápido: 10! já é 3.628.800, e 20! é 2.432.902.008.176.640.000.

Para que serve o fatorial na prática?

Para contar possibilidades. Veja três usos:

• Ordenar coisas (permutações): n itens diferentes podem ser colocados em fila de n! formas. Três livros, A, B e C, cabem na prateleira em 3! = 6 ordens: ABC, ACB, BAC, BCA, CAB e CBA. Seis pessoas em uma fila: 6! = 720 ordens.
• Formar anagramas: as 5 letras da palavra MARTE podem ser embaralhadas de 5! = 120 formas.
• Escolher grupos (combinações): quando a ordem não importa, a conta é n! ÷ (k! × (n − k)!), em que k é o tamanho do grupo. Escolher 4 funcionários entre 10 dá 210 grupos. Escolher 6 números entre 60 dá 50.063.860 combinações.

Essas contagens são o primeiro passo no cálculo de probabilidades: para saber a chance de um resultado, é preciso contar quantos resultados existem.

Na programação, o fatorial aparece quando um programa precisa testar todas as ordens possíveis de alguma coisa. Com 10 itens, são 3.628.800 ordens. Com 20, o número já tem 19 dígitos. “Testar tudo” deixa de ser opção bem depressa.

O Python já traz essa conta pronta: math.factorial(5) devolve 120. Mas hoje nós vamos escrever a nossa, porque o fatorial tem uma característica que interessa muito a este artigo.

Exemplo de recursividade: o fatorial

O fatorial é o exemplo clássico de recursividade, e agora você vai ver o motivo. Olhe com atenção para a conta: 5! = 5 × 4 × 3 × 2 × 1. O trecho 4 × 3 × 2 × 1 é o 4!. Ou seja, 5! = 5 × 4!. Do mesmo jeito, 4! = 4 × 3!, e assim por diante… O problema contém uma versão menor dele mesmo! É a boneca dentro da boneca. O caso base é o 1!, que vale 1 e não precisa de conta nenhuma. Veja em PHP:

<?php

function fatorial(int $n): int
{
    if ($n <= 1) {
        return 1; // caso base: aqui a função para de se chamar
    }

    return $n * fatorial($n - 1); // chamada recursiva
}

echo fatorial(5), PHP_EOL; // 120

Em Python:

def fatorial(n):
    if n <= 1:
        return 1  # caso base: aqui a função para de se chamar

    return n * fatorial(n - 1)  # chamada recursiva


print(fatorial(5))  # 120

E em C:

#include <stdio.h>

int fatorial(int n) {
    if (n <= 1) {
        return 1; // caso base: aqui a função para de se chamar
    }

    return n * fatorial(n - 1); // chamada recursiva
}

int main(void) {
    printf("%d\n", fatorial(5)); // 120
    return 0;
}

ATENÇÃO: lembra que o fatorial cresce rápido? Isso aparece no código. Testei aqui: na versão em C, com o tipo int de 4 bytes, a conta sai certa até 12! (479.001.600). O 13! é 6.227.020.800, não cabe mais na variável, e fatorial(13) mostrou um número errado: 1932053504. Na versão em PHP, fatorial(20) funcionou, e fatorial(21) parou com TypeError: fatorial(): Return value must be of type int, float returned. No Python, fatorial(21) devolveu 51090942171709440000, sem erro.

O que acontece por dentro de uma função recursiva?

Veja o passo a passo de fatorial(4):

Passo	Chamada	O que ela faz
1	fatorial(4)	Espera o resultado de fatorial(3)
2	fatorial(3)	Espera o resultado de fatorial(2)
3	fatorial(2)	Espera o resultado de fatorial(1)
4	fatorial(1)	Caso base: devolve 1
5	fatorial(2)	Devolve 2 × 1 = 2
6	fatorial(3)	Devolve 3 × 2 = 6
7	fatorial(4)	Devolve 4 × 6 = 24

Percebe que as chamadas vão se empilhando e depois são resolvidas na ordem inversa? O computador guarda cada chamada em uma pilha: a última que entrou é a primeira que sai.

Ver a animação da pilha de chamadas de fatorial(4)

O que acontece se eu esquecer o caso base?

A função nunca para de se chamar, a pilha enche e o programa quebra. Veja esta função em Python, sem caso base:

def contagem(n):
    print(n)
    contagem(n - 1)  # sem caso base: nunca para


contagem(3)

Testei aqui e o programa terminou com o erro RecursionError: maximum recursion depth exceeded. No PHP, o manual oficial avisa que recursão infinita é considerada erro de programação, e que chamadas recursivas acima de 100 a 200 níveis já podem esgotar a pilha e encerrar o script.

Agora é com você!

Escreva uma função recursiva que soma todos os números de 1 até n. Para n = 4, o resultado é 10 (4 + 3 + 2 + 1). Antes de digitar, responda no papel: qual é o caso base? E qual é a chamada recursiva?

Se você respondeu essas duas perguntas, o código já está pronto na sua cabeça!!! Tente sozinho antes de pedir a resposta para alguém. É usando o seu raciocínio que você aprende de verdade.

Recursividade ou laço de repetição?

Tudo que você faz com recursividade dá para fazer com um laço de repetição, e vice-versa. Então quando usar cada um?

	Recursividade	Laço de repetição
Combina com	Problemas que se dividem em partes iguais e menores, como pastas dentro de pastas	Repetições simples, com começo e fim conhecidos
Memória	Usa a pilha a cada chamada	Usa menos memória
Leitura	Costuma ficar mais curta	Mais direta para quem está começando

Para o fatorial, sendo bem sincero, o laço resolve melhor. Usei esse exemplo porque é o mais fácil de enxergar. A recursividade brilha mesmo quando chegarmos em árvores e nos algoritmos de busca e ordenação.

E é para lá que vamos! No próximo artigo você vai conhecer a busca binária, um jeito muito rápido de achar um valor dentro de um vetor. Até lá!

Confiança Sempre!!!

Fontes:

• Manual do PHP. Funções definidas pelo usuário (funções recursivas).
• Documentação do Python. O tutorial do Python.
• UFMG, Departamento de Ciência da Computação. Algoritmos e Estruturas de Dados I, aula 11: recursividade, com o fatorial, o caso base e a pilha de execução.
• Unicamp, Instituto de Computação. MC102, aula 12: recursão, com o estado da pilha a cada chamada do fatorial.
• Universidade do Porto, Faculdade de Ciências. Estruturas de Dados, apontamentos sobre recursividade, com os erros mais comuns e o estouro de pilha.
• UFSCar. AED1, aula 14, com a relação entre pilha de execução e recursão e a conversão para um laço.
• Unicamp, Instituto de Computação. Notas de aula de Algoritmos e Programação de Computadores: recursão, com a mesma função escrita com recursão e com laço.
• Unicamp, Instituto de Computação. MC102, aula 16: recursão, com o que acontece quando a função não tem caso base.
• Real Python. RecursionError, com o erro que o Python mostra ao passar do limite de chamadas.
• Universidade Federal do Amazonas, PROFMAT. Análise Combinatória: Teoria e Aplicações para o Ensino Básico (dissertação, 2018), com a definição do fatorial, o 0! = 1, a forma recursiva, as permutações e as combinações.
• IFSC, Câmpus Tubarão. Análise Combinatória, com o símbolo do fatorial e os exemplos da fila de 6 pessoas, dos anagramas de MARTE e do sorteio de 4 entre 10.
• Documentação do Python. Módulo math (em inglês), com a função factorial.