2 min de leitura ·

Introdução básica à recursividade

https://www.lucasmantuan.com.br
https://github.com/lucasmantuan
https://www.linkedin.com/in/lucasmantuan

Uma rotina é recursiva quando ela chama a si mesma repetidamente para a resolução de um problema. Apesar de se ter uma definição simples, a recursividade nem sempre é algo fácil de entender.

Ela é uma estratégia utilizada na ciência da computação que consiste em dividir um problema grande em problemas menores e cada vez mais fáceis de se resolver, até chegar em um que seja simples o suficiente para ser resolvido sem dificuldade.

Quando chegamos nesta última resolução do problema, este informa sua resolução para o problema anterior, que por sua vez, comunica ao anterior e assim, sucessivamente, até se chegar na resolução do problema inicial.

Para a execução de uma função recursiva, é necessário que ela siga três regras básicas, que são:

Uma função recursiva deve ter um caso base, ou seja, que encerra sua execução quando a função chega nele.
Uma função recursiva deve mudar seu estado e se aproximar do caso base a cada nova chamada de sua função, e aproximar daquele resultado que é previsto como o resultado final.
E, por último, um algoritmo recursivo obviamente deve chamar a si mesmo recursivamente.

Como exemplo podemos citar o jogo das bonecas Matrioska. O objetivo consiste em pegar a última boneca, a menor de todas, abrindo boneca por boneca. Este é o nosso caso base.

Vamos então chamar a nossa função retirarMatrioska(). Esta função primeiramente vai verificar se a última boneca foi retirada. Se ela tivesse sido retirada nossa função se encerraria, mas não é este o caso em nosso exemplo. Logo após a verificação, a função retira uma das bonecas e em seguida chama a função retirarMatrioska() novamente.

Desta forma, a nossa função retirarMatrioska() só vai parar de ser executada quando a última boneca, a menor de todas, for retirada.

Nossa função retirarMatrioska() possui as três regras básicas da recursão. Primeiro, ela tem um fim previsto quando a última Matrioska é retirada. A cada nova chamada da função, nos aproximamos do seu resultado final. Por fim, ela chama a si mesma, ou seja, uma função recursiva.

kht

2 anos atrás

Complementando (sei que a intenção foi dar uma ideia básica, mas acho que vale a pena aprofundar só um pouquinho, com alguns pontos que eu acho importante)...

Recursão (ou recursividade) é uma daquelas coisas que no começo é difícil de entender, mas depois que entende, muita gente se empolga e quer usar em "tudo".

Mas você não deveria usar pra tudo. Na verdade, no dia-a-dia você vai usar menos do que imagina. A maioria dos problemas mais comuns encontrados em grande parte dos sistemas podem ser resolvidos com um loop simples em vez de recursão.

Claro que é importante saber o conceito (pois um dia vai ter um caso que é melhor resolvido com recursão), mas é mais importante ainda saber quando não usar (pois tais casos não são a regra).

Exemplo

Um exemplo clássico é o cálculo do fatorial. Esse é muito usado para ensinar recursão, justamente porque a definição matemática é recursiva. Para calcular o fatorial de um número N, basta fazer:

se N é zero, o resultado é 1
senão, o resultado é N * fatorial(N - 1)

E aí segue a implementação clássica (todos os exemplos abaixo estão em JavaScript):

function recursiveFat(n) {
    if (n == 0) {
        return 1;
    }
    return n * recursiveFat(n - 1);
}

Atenção: nenhuma das funções mostradas vai verificar se n é um número negativo, ~~por preguiça~~ para simplificar os exemplos :-)

E isso funciona, mas tem alguns detalhes (que muita gente esquece de explicar quando ensina recursão).

Ao se chamar uma função, a chamada é empilhada no stack (ou "colocada na pilha"), e fica lá até que a função retorne. Mas como o resultado de uma chamada depende de outra chamada recursiva, as funções só serão desempilhadas quando a última destas chamadas retornar.

Por exemplo, se eu chamo recursiveFat(2):

a chamada recursiveFat(2) é empilhada
não cai no if (pois n é igual a 2), e chama n * recursiveFat(n - 1), ou seja, 2 * recursiveFat(1). Para ter este resultado, eu preciso saber qual o valor de recursiveFat(1), então precisamos executá-la primeiro
- a chamada recursiveFat(1) é empilhada
- não cai no if (pois n é igual a 1), e chama n * recursiveFat(n - 1), ou seja, 1 * recursiveFat(0). Para ter este resultado, eu preciso saber qual o valor de recursiveFat(0), então precisamos executá-la primeiro
  - a chamada recursiveFat(0) é empilhada
  - agora cai no if, pois n é igual a zero, então retorna 1
- recursiveFat(0) retornou 1, então agora conseguimos calcular 1 * recursiveFat(0) -> 1 * 1 -> 1
recursiveFat(1) retornou 1, então agora conseguimos calcular 2 * recursiveFat(1) -> 2 * 1 -> 2

O resultado é 2. Mas veja que, para recursiveFat(2) retornar, ela teve que ficar esperando recursiveFat(1) terminar, que por sua vez teve que esperar recursiveFat(0) terminar. Durante todo esse tempo, todas as 3 chamadas estavam ocupando espaço na pilha.

O problema é que a pilha tem tamanho limitado. Por exemplo, se chamarmos recursiveFat(100000), vai dar erro:

RangeError: Maximum call stack size exceeded

São tantas chamadas recursivas "penduradas", esperando as demais terminarem, que estourou o tamanho da pilha.

Se eu fizesse o algoritmo iterativo (com um loop simples), isso não aconteceria:

function iterativeFat(n) {
    var fat = 1;
    // não preciso multiplicar por 1 porque não muda nada, posso começar do 2 mesmo
    // se n for menor que 2, ele nem entra no for e o resultado será 1
    for (var i = 2; i <= n; i++) {
        fat *= i;
    }
    return fat;
}

Obs: agora se eu chamar iterativeFat(100000) vai dar Infinity, mas isso é porque o resultado ultrapassa o valor máximo que o Number do JavaScript suporta. Se quiser mesmo ter o resultado, pode trocar para BigInt, bastando colocar o sufixo n nos números: var fat = 1n e for (var i = 2n; etc. Independente disso, o importante é que agora só temos uma única chamada da função (contra várias chamadas da versão recursiva), portanto não vai estourar a pilha (pode estourar a memória se os números começarem a ficar grandes demais, claro, mas aí não tem jeito, fatorial cresce muito rápido).

E além de não estourar a pilha, a versão iterativa ainda é mais rápida, veja.

Não estou dizendo que recursão é "do mal" ou que nunca deva ser usada. É um conceito importante e tem seus usos. Por exemplo, em árvores, que são estruturas naturalmente recursivas: alguns algoritmos para percorrer o DOM de uma página (que é uma árvore) podem ser melhores expressos de forma recursiva. Mas a maioria dos casos mais comuns do dia-a-dia pode ser resolvida com um loop simples.

Além disso, de maneira geral, todo algoritmo iterativo pode ser convertido para um recursivo e vice-versa. Mas só porque pode, não quer dizer que você deve fazê-lo. Muitas vezes um deles será bem melhor (mais simples, mais claro e/ou mais eficiente) que o outro.

O importante é entender o conceito, seus prós e contras, quais problemas ele resolve bem e em quais casos ele não é o mais adequado, e aí decidir quando usar ou não (aliás, isso vale pra tudo em computação).

LucasMantuan

Autor

2 anos atrás

Opa, só para entender melhor. Para contornar este problema do estouro de pilha eu poderia otimizar a função recursiva, algo como:

function tailRecursiveFat(n, resultado = 1) {
    if (n == 0) {
        return resultado;
    }
    return tailRecursiveFat(n - 1, n * resultado);
}

Mas, coloquei ela no site de testes, e para este exemplo que você passou o loop for ainda é mais rápido.

kht

2 anos atrás

Isso só elimina o estouro de pilha em linguagens que otimizam a recursão em cauda - o que não é o caso do JavaScript, pois ainda sim estoura a pilha, veja: https://ideone.com/n6mFHd

Ah, vale lembrar que o número que faz a pilha estourar pode variar, pois depende de detalhes da implementação. Mas o JavaScript (pelo menos na versão atual) não otimiza recursão em cauda, então para evitar o estouro em todos os casos, só usando loop mesmo.

Obs: parece que o Safari otimiza recursão em cauda, mas os demais pelo jeito não (testei no Node, e também estourou a pilha).

maniero

2 anos atrás

Aqui vai um link com um artigo sobre recursividade.