Como entender a recursão em JavaScript

Como entender a recursão em JavaScript

11 de September, 2020 0 By António César de Andrade


“Para entender a recursão, é preciso primeiro entender a recursão” – Desconhecido

Se você for como eu, provavelmente não entendeu a recursão na primeira vez que leu sobre ela.

Para mim foi porque

  1. recursão é um conceito difícil em si, e
  2. alguns dos tutoriais e artigos que li não eram muito claros.

Por alguma razão, a maioria dos artigos que explicavam a recursão usavam o exemplo de números fatoriais e a sequência de Fibonacci. Isso significava que eu precisava entender como os números de Fibonacci funcionavam e conectar isso à recursão.

Mas estamos seguindo um caminho diferente neste artigo.

O que é recursão?

No mais básico dos termos, recursão é quando uma função continua chamando a si mesma até que não precise mais.

O que? Sim, a função continua chamando a si mesma, mas com uma entrada menor a cada vez.

Pense na recursão como uma corrida em circuito. É como correr na mesma pista indefinidamente, mas as voltas ficam cada vez menores. Eventualmente, você fará a última e menor volta e a corrida terminará.

O mesmo com a recursão: a função continua chamando a si mesma com uma entrada menor e eventualmente para.

Mas, a função não decide por si mesma quando parar. Dizemos quando parar. Damos à função uma condição conhecida como caso base.

O caso base é a condição que informa à função quando ela deve parar de chamar a si mesma. É como dizer à função qual será a última volta da corrida para que ela pare de correr depois dessa volta.

Exemplos de recursão

Tudo bem, isso é recursão. Vejamos alguns exemplos para entender como funciona a recursão.

Lembra da primeira vez que você aprendeu sobre loops? O primeiro exemplo que você provavelmente deu foi um programa de contagem regressiva. Vamos fazer isso.

Primeiro, vamos entender o que queremos que nosso programa faça. Faça uma contagem regressiva de um determinado número até o menor número, subtraindo 1 a cada vez.

Dado o número 5, esperamos que a saída seja algo como:

// 5
// 4
// 3
// 2
// 1

Tudo bem, como podemos codificar este programa com recursão?

let countDown = number => {
    //base case
    if (number === 0) {
        return;
    }
    console.log(number);
    return countDown(number - 1);
};
console.log(countDown(5)) // 5, 4, 3, 2, 1

Então, o que exatamente está acontecendo aqui?

Se você percebeu, a primeira coisa que fizemos foi definir o caso base. Por quê? Porque a função, antes de tudo, precisa saber quando vai parar de chamar a si mesma.

Você nunca participaria de uma corrida sem antes saber a duração da corrida, certo?

Se você não informar à função quando ela deve parar, algo chamado stackoverflow vai acontecer. A pilha será preenchida com funções que estão sendo chamadas, mas não retornam ou são retiradas da pilha.

O bit recursivo realmente acontece na linha 7. Lá, dizemos à função para continuar retornando a si mesma, mas reduzindo a entrada em um a cada vez.

Então, efetivamente, isso é o que está acontecendo:

// The current input is 5
// Is 5 equal to 0 ?
// No, Ok so lets log 5 to the console.
// Its calls Itself again with number - 1 OR 5 - 1;
// The current input is 4
// Is 4 equal to 0 ?
// No, Ok so lets log 4 to the console
// Repeats until input is 0 so then function stops calling itself. 

Tudo bem, isso fazia sentido. Vamos tentar outro exemplo.

Você sabe como podemos dizer que um número é par usando o operador de resto (%)? Então, se qualquer número% 2 == 0 então esse número é par ou se qualquer número% 3 == 0 então esse número é ímpar.

Bem, acontece que existe outro método.

Se subtrairmos continuamente dois de um número até que o menor número seja 0 ou 1, então podemos dizer se o número é par ou ímpar.

Vamos tentar fazer isso com recursão. Então, dado o número 6, nosso programa deve retornar ‘Até’ porque 6-2-2-2 = 0. Dado 7, nosso programa deve retornar ‘ímpar’ porque 7-2-2-2 = 1.

Vamos ver no código.

let oddOrEven = (number) => {
    if (number === 0) {
        return 'Even';
    } else if (number === 1) {
        return 'Odd';
    } else {
        return oddOrEven(number - 2);
    }
};
console.log(oddOrEven(20)) // Even
console.log(oddOrEven(75)) // Odd
console.log(oddOrEven(98)) // Even
console.log(oddOrEven(113)) // Odd

Novamente, a primeira etapa foi informar à função quando parar de chamá-la de self. Então dissemos a ele o que fazer quando ligar a si mesmo.

A recursão é basicamente dividir para conquistar. Continuamos dividindo o problema, tornando-o cada vez menor.

Recursão vs Loops

Quando se trata de velocidade, um loop é executado muito mais rápido do que uma função recursiva. Também é mais fácil escrever um loop do que uma função recursiva. E quando se trata de legibilidade, é mais fácil saber o que está acontecendo com um loop do que com uma função recursiva.

Mas, as funções recursivas são muito elegantes.

Então, qual é a melhor escolha? Eficiência ou velocidade?

Aqui está uma citação do livro eloquent JavaScript.

A preocupação com a eficiência pode ser uma distração. É outro fator que
complica o design do programa, e quando você está fazendo algo que já
difícil, aquela coisa extra com que se preocupar pode ser paralisante.
Portanto, sempre comece escrevendo algo que seja correto e fácil de entender.
Se você está preocupado por estar muito lento, o que geralmente não é desde
a maioria do código simplesmente não é executado com freqüência suficiente para levar uma quantidade significativa
de tempo – você pode medir depois e melhorá-lo, se necessário.

Neste ponto, você deve estar se perguntando por que no mundo você escolheria escrever uma função recursiva em um loop. Quero dizer, os loops são muito mais fáceis, certo?

Bem, isso é verdade – mas existem alguns problemas que são mais fáceis de resolver com a recursão. Se você gostaria de explorar um desses problemas, considere ler Capítulo 3 do Eloquent JavaScript.

Agora que você descobriu um novo superpoder, vamos colocá-lo em prática.

Faça os seguintes exercícios usando recursão. Se você sentir que pode assumir mais tarefas, poderá resolver os famosos problemas fatoriais e de sequência de Fibonacci.

Exercícios

Se você quiser se desafiar ainda mais, considere resolver esses problemas recursivos.

  1. Escreva um programa que reverta uma string usando recursão. Dada a string “freeCodeCamp”, seu programa deve retornar “pmaCedoCeerf”.
  2. Escreva um programa que retorna o número de vezes que um caractere aparece na string. Seu programa deve receber uma string e o caractere. Ele deve então retornar o número de vezes que o caractere aparece na string.
    Dada a string “JavaScript” e um caractere “a”, seu programa deve retornar 2.

    Dica: Tente descobrir quando você deseja que a função pare de chamar a si mesma e como retornar uma versão menor do problema toda vez que a função chamar a si mesma.

Isso é tudo para este artigo. Espero que tenha ajudado você a entender melhor a recursão.

Se você gostou deste artigo, você pode se conectar comigo no Twitter.





Fonte

Click to rate this post!
[Total: 0 Average: 0]