1

Estou fazendo o curso da FreeCodeCamp e no assunto de recursividade me deparei com esse código:

function countup(n) {
  if (n < 1) {
    return [];
  } else {
    const countArray = countup(n - 1);
    countArray.push(n);
    return countArray;
  }
}

Ele me retorna um array com correspondente ao tamanho N (se eu colocar 5, retorna um array [1,2,3,4,5]).

Eu entendo o conceito de recursividade, mas não consegui entender esse código. Porque o const countArray = countup(n - 1);? Qual o significado dessa linha? Porque pra mim, a partir do momento que eu chamo a função countup(n - 1), o que esta abaixo dela não é executado. Podem me ajudar?

3 Respostas 3

2

Depois que você chama countup(n - 1), as linhas abaixo são executadas sim, mas só depois que esta chamada retorna.

Para simplificar, vamos ver o que acontece quando você chama countup(2):

  • countup(2): n é igual a 2, então não entra no if (n < 1)
  • é chamado countup(n - 1), ou seja, countup(1)
    • dentro da chamada countup(1): n é igual a 1, então não entra no if (n < 1)
    • é chamado countup(n - 1), ou seja, countup(0)
      • dentro da chamada countup(0): n é igual a 0, então entra no if (n < 1) e retorna um array vazio ([])
    • countup(0) retornou o array vazio, que foi colocado na variável countArray (é o que a linha const countArray = countup(n - 1) faz)
    • countArray.push(n): aqui n vale 1, então 1 é colocado no array (que agora é [ 1 ])
    • o array [ 1 ] é retornado
  • countup(1) retornou o array [ 1 ], que é colocado na variável countArray
  • countArray.push(n): aqui n vale 2, então 2 é colocado no array (que passa a ser [ 1, 2 ])
  • o array [ 1, 2 ] é retornado

Ou seja, a primeira chamada começa no valor inicial de n (no exemplo acima foi 2), e a cada chamada recursiva ele vai diminuindo, até chegar a zero. Quando chega a zero, ela retorna o array vazio e o processo começa a "voltar", inserindo os números no array e retornando-o para a chamada anterior.

O que pode confundir é que a cada chamada o contexto muda: o valor de n e o array countArray sendo manipulados têm valores diferentes. Mas no fim tudo "se junta" e o resultado é um array contendo todos os números de 1 a n.

O importante é que o fato de fazer uma chamada recursiva não trava a execução, como você imagina. O que acontece é que uma chamada recursiva pode acabar fazendo outras chamadas recursivas (como quando countup(2) chamou countup(1), que por sua vez chamou countup(0)), e essas chamadas ficam "penduradas" esperando as outras retornarem. E depois que elas retornam, a execução continua nas linhas seguintes.

O que garante que esse processo não dura para sempre é a condição de parada (if (n < 1)), pois é quando não é feita mais nenhuma chamada recursiva.


Para ententer recursão, antes precisa entender recursão

Pode ser que ajude se você pensar na definição da solução de maneira recursiva: como eu crio um array contendo os números de 1 a N?

  1. se N < 1, o intervalo de 1 a N não terá nenhum número, então o array é vazio (é o que o if faz)
  2. se N >= 1 (ou seja, o bloco else):
    • 2.a) crio um array contendo os números de 1 a N - 1 (usando este mesmo algoritmo recursivamente, ou seja, volto para o passo 1, mas usando o valor de N - 1)
    • 2.b) adiciono o N nesse array

O passo 2.a corresponde a const countArray = countup(n - 1) (eu resolvo o mesmo problema recursivamente para N - 1), e o passo 2.b corresponde a countArray.push(n).

A ideia de recursão é basicamente essa: existe um caso "base" com uma solução trivial (o array vazio), e para os outros casos você resolve instâncias menores do problema de maneira recursiva, até chegar ao caso base, e no final junta tudo.


Explicando de outra maneira

Devido a esta dúvida nos comentários, vou tentar explicar de forma um pouco mais detalhada. Para simplificar, vamos supor que eu chamei countup(1).

É feita a chamada a countup(1):

  • aqui o n vale 1, por isso não entra no if (n < 1)
  • dentro do bloco else:
    • const countArray = countup(n - 1); como n vale 1, então é feita a chamada para countup(0)

Aqui fazemos uma pausa para explicar que a chamada a countup(0) é "independente" da chamada a countup(1). Apesar de ser a mesma função, e de ser chamada dentro dela mesma, são duas chamadas diferentes e cada uma executa de acordo com o seu contexto (no caso, o valor que é passado como parâmetro é diferente).

Então a chamada countup(1) está executando a linha const countArray = countup(n - 1);. Isso quer dizer que ela precisa pegar o retorno de countup(0) e atribuir o valor retornado na variável countArray. Ou seja, ela precisa esperar countup(0) executar por completo.

E como countup(0) executa? Assim:

  • n vale 0, por isso entra no if (n < 1) e retorna um array vazio ([])

Como countup(0) já terminou (retornando um array vazio), então countup(1) pode continuar executando de onde parou:

const countArray = countup(n - 1);

Nesta linha ela pega o retorno de countup(0) (o array vazio) e atribui este valor na variável countArray. Depois ela executa as linhas seguintes:

countArray.push(n);
return countArray;

Ou seja, ela adiciona n ao array (e como estamos dentro da chamada countup(1), o n vale 1, portanto o número 1 será adicionado ao countArray). E por fim, countArray (que agora é o array [1]) é retornado, e countup(1) encerra sua execução.

Repare que cada chamada a countup é "independente": só porque uma está no if, não quer dizer que outra não pode estar no else (pois cada uma tem um contexto diferente, já que os valores de n que cada uma recebe é diferente). E só porque uma delas retornou, não quer dizer que as outras devem retornar imediatamente: cada uma retorna só quando chega em alguma linha contendo return.


De maneira similar, quando chamamos countup(2):

  • aqui o n vale 2, por isso não entra no if (n < 1)
  • dentro do bloco else:
    • const countArray = countup(n - 1); como n vale 2, então é feita a chamada para countup(1)

Ou seja, a chamada countup(2) precisa esperar countup(1) terminar para atribuir o retorno na variável countArray.

E pela explicação acima, já sabemos que countup(1) retorna o array [1]. Ou seja, depois que countup(1) termina, o array [1] é retornado e atribuído na variável countArray.

Depois disso, a chamada countup(2) pode continuar executando. A linha seguinte é countArray.push(n);, e como countArray é [1] e o n vale 2, o número 2 é adicionado no array, que passa a ser [1, 2].

Depois disso o array é retornado, e o resultado é [1, 2].

10
  • 'dentro da chamada countup(0): n é igual a 0, então entra no if (n < 1) e retorna um array vazio ([])' Se ele retorna um array vazio, o certo não seria SAIR da função? Porque o ELSE é executado se ele somente é feito para ser executado se o IF for falso? O que quero dizer é: se o IF for verdadeiro, então o ELSE não é executado. Ai que estou em duvida tambem. E pra ser bem sincero e peço até desculpas porque sua resposta é extremamente completa, a partir deste tópico que eu coloquei eu realmente nao entendi Commented 10/03/2020 às 19:35
  • @BrunoValle Não, ele só sai da função se tivesse um return countup(0). Mas como vc guarda o retorno em uma variável (countArray = countup(0)), o retorno é guardado na variável e a execução continua. Não sei se ajuda, mas imagine que em vez de countup vc chamasse uma outra função qualquer (countArray = outrafuncao(n - 1)), a função countup retornaria ou continuaria na linha seguinte? O fato de chamar a mesma função é só um detalhe, pois ela será chamada novamente e cada chamada é "independente". Não sei se isso confundiu mais ainda ou ajudou...
    – hkotsubo
    Commented 10/03/2020 às 19:38
  • Ou seja, countup(0) retorna o array vazio e essa chamada se encerra. Mas countup(0) foi chamado dentro da execução de countup(1) (e essa ainda não se encerrou, pois ela está dentro do else e precisa continuar nas linhas seguintes)
    – hkotsubo
    Commented 10/03/2020 às 19:42
  • @BrunoValle countup(1) entra no else e chama countup(0). E countup(0) entra no if e retorna o array vazio. A execução de countup(0) encerrou, mas countup(1) ainda não, pois ela ainda precisa executar o resto (atribui o retorno de countup(0) na variável countArray, faz o push e o return). Cada chamada de countup é independente, o fato de uma estar no if não impede a outra de estar no else
    – hkotsubo
    Commented 10/03/2020 às 20:01
  • @BrunoValle Atualizei a resposta, adicionei uma explicação mais detalhada no final. Veja se ajudou a entender melhor
    – hkotsubo
    Commented 11/03/2020 às 11:35
1

Veja que cada vez que o countup é chamado dentro dele mesmo, o interpretador aguarda até que a função retorne um valor para que ele possa prosseguir com a execução do código.

Para facilitar o entendimento acompanhe o cenário abaixo e leia os comentários dentro do código.

Considere countup(2):

Primeira execução:

function countup(2) {
    if (2 < 1) {
        return [];
    } else {
        // O interpretador vai parar aqui até que a função
        // retorne seu valor...veja o Segunda execução
        const countArray = countup(2 - 1);
        countArray.push(n);
        return countArray;
    }
}

Segunda execução

function countup(1) {
    if (1 < 1) {
        return [];
    } else {
        // O interpretador vai parar aqui até que a função
        // retorne seu valor...veja o Terceira execução
        const countArray = countup(1 - 1);
        countArray.push(n);
        return countArray;
    }
}

Terceira execução

function countup(0) {
    if (0 < 1) {
        // Para o valor 0 esta função irá retornar um array vazio.
        // Este resultado será recebido na segunda execução
        return [];
    } else {
        const countArray = countup(0 - 1);
        countArray.push(n);
        return countArray;
    }
}

Voltando a segunda execução

function countup(1) {
    if (1 < 1) {
        return [];
    } else {
        // Agora com o resultado na mão da terceira execução o 
        // interpretador irá prosseguir até o return
        const countArray = [] /* countup(1 - 1) = [] */;
        countArray.push(n); // Agora o array vazio ganha o valor 1 = [1]
        return countArray;
    }
}

Voltando a primeira execução

function countup(2) {
    if (2 < 1) {
        return [];
    } else {
        // Agora com o resultado na mão da segunda execução o 
        // interpretador irá prosseguir até o return
        const countArray = [1] // countup(2 - 1) = [1];
        countArray.push(n); // O array ganha o novo valor 2: [1, 2]
        return countArray;
    }
}
2
  • Marcelo, muito obrigado pela explicação!!! Sou novo aqui e estava com receio de mandar perguntas. Mais uma vez, obrigado! Commented 11/03/2020 às 11:50
  • Grande @BrunoValle, fico feliz em ajudar ;) e sempre que tiver dúvidas não hesite em postar. abs Commented 11/03/2020 às 15:29
0

Quando N < 1 (primeira condição), a recursividade vai começar a voltar. Ou seja, na linha que você está em dúvida const countArray = countup(n - 1);, o método irá retornar 0, portanto const countArray = 0. A partir disso, irá executar as linhas de baixo:

countArray.push(n);
return countArray;

Ou seja, N será adicionado ao array na volta da recursividade. Se você colocar essas linhas antes de countArray = countup(n - 1);, o array retornará como [5,4,3,2,1], pois você estará adicionando n ao array antes de chegar no início da contagem.

1
  • Vitor, muito obrigado!! Commented 11/03/2020 às 11:50

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .