Olá, caro aluno! Tudo bem? Espero que sim! Vamos agora recapitular o que foi visto anteriormente? Na aula anterior, você foi apresentado ao conceito de recursão e de sua aplicação a números e strings. Acredito que você tenha realizado todos os exercícios e que eles tenham ajudado a consolidar os seus conhecimentos básicos de recursão. Embora muitos alunos possam achar esse assunto difícil de ser entendido, não necessariamente ele tem que ser. Com a prática, você irá desenvolver as habilidades necessárias para identificar a natureza recursiva de problemas e desenvolver uma solução usando recursões. Então, se você ainda não praticou os exemplos e exercícios da última aula, faça-os antes de prosseguir.

Se você já praticou bastante, vamos em frente!

Nesta aula, iremos aprofundar os seus conhecimentos sobre recursão, aplicando-os a Arrays e Matrizes e resolvendo juntos alguns exercícios.

A principal utilidade da recursão é a de reduzir a complexidade de um problema. Por exemplo, suponha que em um problema seja pedido a soma de um array. Você viu como resolvê-lo usando o reduce e uma função de callback, lembra-se? Agora, veremos o mesmo problema sendo resolvido de outra forma.

Na página HTML, você pode ver o resultado final que nós queremos obter, para isso tenho o botão de INSERIR, para colocarmos elementos, ao lado o campo numérico onde escolho os elementos que quero inserir, e toda vez que inserir quero que seja exibida a soma atual do nosso array, ok? Temos também um botão LIMPAR que serve para zerar essa soma.

Então, por exemplo, posso inserir o elemento 1, o elemento 2, e olhe que a soma está sendo atualizada, pois já temos aqui 1 + 2 com a soma sendo 3.

Ao inserirmos o 3, teremos a soma 1 + 2 + 3 e, e ao clicar em LIMPAR, limpo o array e zero a soma.

Código 1 - 14_1 Soma Array.html

Vamos lembrar como podemos fazer isso usando o reduce. No HTML, a entrada é um número, como pode ser visto na linha 11 do HTML.

Tenho dois botões, INSERIR e LIMPAR, o INSERIR chama a função inserir, o LIMPAR chama a função limpar e um campo de resultado que é onde a gente vai ficar escrevendo essa soma.

No JavaScript, tenho na linha 1 o array numeros que vai ficar armazenando o array atual, tenho a função inserir e a função limpar. Na função inserir, ela pega um número da página e usa o método push para colocar esse elemento no final do array e chama a função imprimir. A função limpar zera aquela variável numeros, ou seja, limpa o array e chama a função imprimir.

Por fim, a função imprimir declara a variável soma e atribui a ela o resultado da soma do array, que é a que vai ser exibida, cria a string resposta com o array numeros e com a soma que foi calculada na linha 15 e atualiza a página.

E como ele faz essa soma? Usando o método reduce com a função de callback somar, que simplesmente soma o acumulador com o valor que você passar. Então começo passando com o valor inicial 0.

Na função de callback, na linha 23, está a função somar com acumulador e com o valor, e ela retorna o acumulador mais o valor, então se tivermos o array [1, 2, 3] ele começa reduce com o valor inicial 0 e faz 0 + 1 + 2 + 3, e reduz isso para a soma, 6.

Isso também pode ser feito usando recursão. Nesse caso, teremos o caso base quando o tamanho do array for 0, ou seja, quando ele estiver vazio. Dessa forma, retornaríamos o valor 0.

Veja só como fica a solução recursiva!

Código 2 - 14_2 Soma Array.html

O HTML é exatamente o mesmo, só mudei o título da página e no JavaScript, as funções inserir e limpar são exatamente as mesmas. Já a função imprimir é exatamente igual nas linhas 17, 18 e 19, entretanto, na linha 15, ao invés de usar a função reduce, a gente vai utilizar a função somarArray, que vai ser a nossa função recursiva, passando o array de numeros. Tá certo?

No caso base, se o array tiver o tamanho 0, ou seja, se o a.length for igual a 0, nós acabamos, pois esse é o nosso caso base e a gente retorna 0. Caso contrário, o nosso retorno vai ser o valor do primeiro elemento mais a soma do resto do array, ou seja, mais o a.slice(1). Lembrando que o a.slice(1) nos dá um array que remove o primeiro elemento do array, ou seja, ele dá o que a gente chama de calda do array. E aí a gente dá o retorno, tá certo?

Na nossa página ela vai ter exatamente o mesmo comportamento. Só que agora estamos usando uma função recursiva.

Essa soma também poderia ser feita utilizando um laço for ou um laço while. No entanto, imagine que pudéssemos ter arrays aninhados, ou seja, arrays onde seus elementos podem tanto ser números quanto arrays. Mais ainda, suponha que isso pudesse acontecer em vários níveis, como exposto na Figura 4.

Para uma melhor compreensão do array numeros, acompanhe a ilustração. O array numeros é o que está representado pela caixa preta. Note que ele tem apenas quatro elementos que estão representados por caixas brancas: o primeiro é o número 1, o segundo é o número 2 e o último é o número 12. Note, porém, que o terceiro elemento é um array contendo três elementos representados pelas caixas amarelas. A primeira caixa amarela, ou seja, o primeiro elemento desse array, é o número 3, mas o segundo e o terceiro são arrays.

Para facilitar o seu entendimento, vou chamá-los de amarelo2 e amarelo3. O array amarelo2 contém apenas números, a saber, os números 4, 5 e 6. O array amarelo3 contém três elementos. Os dois primeiros são os números 7 e 8, mas o último elemento é um array com três elementos representados por caixas azuis. O primeiro é o número 9 e o último é o número 11, mas o do meio é um array que possui apenas um elemento, o número 10.

Você notou que temos vários níveis de arrays? Isto é o que chamamos de arrays aninhados. Na verdade, você já conheceu um tipo bem comportado de array aninhado, as matrizes. Como já visto, elas são representadas por arrays cujos elementos também são arrays de valores, todos com o mesmo tamanho.

Agora, retornaremos ao problema. Como fazer a soma de todos os elementos numéricos desse array aninhado sem uma definição da quantidade de níveis de aninhamento?

Nesse caso, a solução com laços ficaria mais complicada, porque teríamos que aninhar loops. No entanto, não sabemos a profundidade em que esses loops estão aninhados. O número desconhecido de loops aninhados é uma característica comum de todos os problemas de natureza recursiva e indica que uma solução recursiva é a mais apropriada.

Veja como fica a solução.

O HTML é muito simples, não vou colocar uma opção para ficar construindo esse array aninhado, pois iria complicar muito o exemplo, vamos focar na solução apenas da soma recursiva. Então coloco um botão EXIBIR, o campo "resultado" e vou fixar para esse exemplo, a variável numeros com esse array visto anteriormente, na Figura 4.

A função exibir é chamada quando aperto o botão EXIBIR na tela e ela simplesmente escreve "soma = " e o resultado da função somarArray, passando o nosso array de numeros. A ideia da função é que, se chegar no final do array, é o caso base, ou seja, se a.length==0, a soma é igual a 0.

Código 3 - 14_3 Soma Array.html

Temos duas possibilidades de recursão: ou cheguei no elemento que não é um array (ou seja, ele é um número), ou cheguei num elemento que é um array.

Na linha 12, estou tratando o caso em que cheguei em um elemento que não é um array, assim vou usar a função Array.isArray para verificar se o primeiro elemento, ou seja, a[0], é um array. Para isso, coloco na frente da função o not (!), ficando: !Array.isArray(a[0]). Assim, se o elemento a[0] não é um array, o que tenho que fazer? Preciso adicionar ele à soma do resto desse array. Então, vou somar a[0] com a soma do resto do array, ou seja, somarArray(a.slice(1)), que nos dá a soma da calda desse array, tá certo?

O terceiro caso é quando o elemento é um array. Bom, se o elemento é um array, o que tenho que fazer? Preciso retornar a soma dele com a soma do resto. Então, tenho na linha 15, duas recursões, eu chamo a função somarArray(a[0]) para eu saber qual é a soma desse array e chamo a função somarArray(a.slice(1)), passando o resto desse array que estou no momento. E a recursão vai tratar de sair entrando nos arrays, chamando a soma para eles nos arrays aninhados, até chegar no número. Essa é a beleza da recursão, tá? Portanto, você pode ver que nós temos uma função bastante simples do ponto de vista de tamanho, mas ela dividiu para conquistar a solução de somar esse array aninhado.

Por fim, veja que na página HTML, ao clicar em exibir, tenho, de fato, a soma de todos aqueles elementos do array principal. Interessante, não é?

Algumas vezes, pode-se ter mais de um caso base. Isso acontece quando a recursão pode parar em mais de uma situação. Por exemplo, suponha que se deseje retornar um array cujos elementos são iguais à soma dos respectivos elementos de outros dois arrays. Porém, assuma que os arrays podem ter tamanhos diferentes, como nos dois exemplos apresentados no slide (Figura 6).

Note que na primeira soma dos arrays representados com quadrados azuis, a recursão vai parar quando o array numeros1 estiver vazio. Por outro lado, na segunda soma dos arrays representados com quadrados amarelos, a recursão vai parar quando o array numeros2 estiver vazio.

Tem-se, então, dois casos bases: um em que o array numeros1 está vazio e um em que o array numeros2 é quem está vazio. Nesses casos, retornamos o outro array. Veja como fica a recursão final.

Nesse exemplo, assuma que os arrays não são aninhados, ou seja, que todos os seus elementos são valores numéricos.

Então, a gente vai fazer a inserção dos elementos nos dois Arrays e depois cada inserção irá gerar um Array de soma que vamos exibir na tela. Então, ao invés de ter só um botão para inserir no Array, a gente vai ter dois botões: INSERIR NO ARRAY 1 e INSERIR NO ARRAY 2. Assim, usando o exemplo da Figura 11, vou inserir o 10, 20, 30, e o 40 no Array 1. No Array 2 vou colocar o 1, e perceba na Figura 7 que o Array Soma já tem a soma do primeiro elemento do Array 1 com o primeiro elemento do Array 2, que é 11, e o resto fica igual ao Array 1 porque o Array 2 não tem elementos, ok?

No entanto, à medida que eu for inserindo no Array 2, a soma vai mudando. E se o Array 2 tiver um tamanho maior que o Array 1, acontecerá o mesmo que aconteceu quando o Array 1 tinha mais elementos, passará direto para o Array Soma, já que no Array1 não haverá um elemento correspondente, ou seja, o quinto elemento do Array Soma é exatamente igual ao último elemento do Array 2 porque o Array 1 só tem quatro elementos, como mostra a Figura 8.

Como fica a nossa solução? O nosso HTML é parecido com o que a gente já viu, tem um campo de entrada na linha 11, dois botões, sendo um para inserir no Array 1 e outro para inserir no Array 2, e perceba que a função inserir agora tem um parâmetro, a gente passa o valor 1 para inserir no Array 1, e o valor 2 para inserir no Array 2, como é possível ver nas linhas 12 e 13. O botão LIMPAR simplesmente chama a função limpar, e, por fim, o nosso campo de escrever o resultado.

Código 4 - 14_4 Soma Dois Arrays.html

Agora, vamos conhecer o JavaScript dessa solução. Ao invés de ter agora só um array, temos dois arrays: numeros1 e numeros2. A função inserir é parecida com a anterior, só que agora ela verifica se o parâmetro que ele recebeu, n, é igual a 1 ou a 2. E se for igual a 1, essa função pega o valor que está na página e empurra ele, ou seja, faz um push dele, colocando na calda do array numeros1. Caso contrário, se o n for 2, ela coloca na calda do array numeros2 e chama a função imprimir.

A função limpar, limpa, de fato, os dois arrays e chama também a função imprimir. E a função imprimir, novamente, constrói um texto que é a resposta, e altera na página o parágrafo de resultado com esse texto, e o que tem nele? Tem o Array 1, o Array 2 e o Array Soma. E o array de soma é igual ao resultado de chamar a função somar passando numeros1 e numeros2, ok?

Então o foco realmente é na definição recursiva dessa função somar. E como eu somo dois arrays, a e b? Bom, se é uma função recursiva, é bom começar pelo caso base, e tenho dois casos base:

1. Se o primeiro array acabar, a função acaba porque eu simplesmente pego o resto do outro array.
2. Se o segundo array acabar, a função também termina porque eu só faço retornar o resto do outro array.

Assim, o caso base é quando a.length, ou seja, o tamanho do primeiro array é 0, ou b.length, ou seja, o tamanho do segundo array é 0. Então se a.length==0, o meu array de soma é o b. Senão, se o b.length==0, o meu array de soma é o a.

Caso contrário, o que eu tenho? Já que os dois arrays têm elementos, visto que o a.length e o b.length não são 0, a minha soma vai começar com a soma do primeiro elemento de a com o primeiro elemento de b, como consta na linha 34.

Logo, meu array de soma vai iniciar com um elemento que é a soma desses dois elementos e construo um array com essa soma. Em seguida, calculo o array com a soma do resto, que é uma chamada recursiva, como consta na linha 36, ou seja, somo o a.slice(1) com o b.slice(1), e isso vai me dar um array que é o array de soma desses dois arrays, e eu concateno ele com o começo que já calculei. Então, pego o meu começo, que está na minha variável soma e concateno com a soma do resto, está certo? E, finalmente, o que vou ter é exatamente esse array contendo a soma dos elementos dos dois arrays que a gente já viu na página que realmente funciona.