Olá! Nesta aula, você conhecerá a técnica chamada de Recursão e suas possibilidades. O termo recursão é bastante utilizado entre os programadores de computador, principalmente entre os mais experientes. Isso porque a recursão é uma técnica de resolução de problemas muito poderosa que facilita a programação de funções em situações específicas. Esse assunto faz parte do universo dos programadores mais experientes, devido a sua maior complexidade, uma vez que, tanto a assimilação da ideia por trás da recursão quanto sua correta utilização, são habilidades que se desenvolvem com o tempo. Existe uma frase engraçada segundo a qual, "para entender recursão, você primeiro tem que entender recursão". Por isso, é importante que você preste bastante atenção ao assunto que veremos aqui, ok?

Para começar, vou te apresentar o conceito de recursão para que você entenda melhor essa técnica. A recursividade é um termo bastante genérico, usado não só na computação. Ela remete ao processo de repetição de algo (um objeto, uma declaração, entre outros), apresentados anteriormente. Veja isso de forma simples, através de figuras do dia a dia. Você consegue perceber alguma recursividade nessa imagem (Figura 1)?

Note que o quadro da Monalisa aparece dentro do próprio quadro diversas vezes, e isso configura a recursão, e ela pode ser infinita! Se observássemos o quadro com uma lupa, dentro de cada quadro iríamos encontrar um quadro menor, seguido de outro quadro dentro dele menor ainda, e por aí vai. Claro que se esse processo é feito por um ser humano, chegará um momento em que ele não terá precisão para pintar quadros de tamanho ínfimo. Ficou fácil entender a recursividade com esse exemplo, não é mesmo?

Um exemplo mais comum (Figura 2), que você já deve ter percebido, é quando estamos em um local com um espelho na frente e outro atrás, de forma paralela. Sua imagem é refletida pelo espelho da frente e pelo de trás. Este segundo reflexo aparece no espelho da frente como um clone seu, que é refletido novamente para o espelho de trás que, por sua vez, projeta mais um clone seu à frente, e assim em diante.

Talvez o meu exemplo favorito seja este aqui (Figura 3). Estranho, né? Pura recursão!!!

A recursão é uma das ideias centrais da Ciência da Computação. Nessa área, ela é um método para resolver problemas cuja solução dependa de soluções menores do mesmo problema. É o que chamamos de "Dividir para Conquistar", expressão que se originou na Política e na Sociologia, mas que foi incorporada pela computação. Geralmente, os problemas podem ser resolvidos por iteração usando laços, mas para isso você precisa identificar e indexar as instâncias menores no momento da programação. Por outro lado, a recursão resolve esses problemas usando funções que são chamadas de dentro de seu próprio código, e sua abordagem pode ser aplicada a muitos tipos de problemas.

Niklaus Wirth, esse do slide (Figura 4), é um cientista da computação suíço que já projetou diversas linguagens de programação, incluindo Pascal. Em 1984, ele ganhou o Prêmio de Turing, que é considerado o "Oscar da Computação", exatamente por esse trabalho. Ele afirmou que "O poder da recursão está evidentemente na possibilidade de definir um conjunto infinito de objetos por uma declaração finita. Da mesma maneira, um número infinito de cálculos pode ser descrito por um programa recursivo finito, mesmo que esse programa não contenha repetições explícitas".

A maioria das linguagens de programação suporta recursão e permite que uma função chame a si mesma. Outras, não definem nenhuma construção de laço e dependem apenas da recursão. Já foi provado que essas linguagens apenas recursivas podem ser usadas para resolver os mesmos problemas que as linguagens que possuem estruturas de controle como while e for. Ou seja, recursão e iteração têm o mesmo poder de expressão e elas podem ser substituídas uma pela outra.

Antes de escolher entre a recursão e a iteração (for/while), você deve avaliar o problema a ser resolvido e a linguagem de programação a ser utilizada. Em linguagens de programação imperativas, como JavaScript, a iteração é a preferida, principalmente para recursão simples, ou seja, quando uma função f chama apenas ela mesma. Isso porque a iteração evita a sobrecarga de chamadas de função e o gerenciamento da pilha de chamadas que acontece na recursão.

Outro conceito importante é o de recursão mútua, que ocorre quando duas ou mais funções formam uma recursão através de um ciclo de chamadas. No slide (Figura 5), temos um exemplo de uma recursão mútua, onde uma função g chama uma função h, que, por sua vez, chama a função g.

Nesta aula, utilizaremos apenas as recursões simples, para simplificar o entendimento dos principais conceitos de recursão. Mas, lembre-se sempre da existência de recursões mútuas.

Observe a função texto no slide (Figura 6). No corpo dessa função temos uma chamada para a própria função, o que a torna uma função recursiva. Porém, essa função nunca irá retornar nada, pois ela sempre é chamada novamente antes do retorno. Temos então um caso de uma recursão infinita, como aquela do espelho.

Em JavaScript, um programa que chame a função texto levantará um erro que poderá ser visto apenas na ferramenta de depuração. Lembre-se que, na maioria dos navegadores, por exemplo, o Google Chrome, você pode acessar essa função apertando a tecla F12. E se decidir fazer isso, você poderá identificar a mensagem de erro "Uncaught RangeError: Maximum call stack size exceeded", a qual indica que o tamanho máximo da pilha de chamadas de função foi atingido. Em outras linguagens de programação, você poderá receber a mensagem de erro "Stack Overflow", ou seja, estouro de pilha, que indica o mesmo problema.

Isso acontece porque toda vez que uma função é chamada, um espaço na memória é alocado para armazenar informações, como os valores das variáveis locais, por exemplo. Em uma recursão infinita você chama a própria função infinitas vezes, certo? Como a memória é finita, chegaria um momento em que não haveria mais memória para ser alocada e o programa seria interrompido pelo sistema operacional do computador.

Vamos ver esse erro acontecendo na prática? Utilize o Código 1 e fique à vontade para editá-lo e fazer vários testes.

Código 1 - 13_1 Recursão Infinita.html e 13_1 Recursão Infinita.js

Nesse exemplo, temos um HTML simples, com apenas um campo de entrada, e ao clicar no botão "exibir" chamaremos a função exibir, que está no arquivo JavaScript. O JavaScript pega o valor desse número que colocamos na linha 2 e guarda na variável resposta o resultado da chamada da função texto. E no final joga no parágrafo de resposta do HTML o valor da variável resposta.

Mas o que é a função texto? Como é que ela foi definida? A função texto concatena a string "Linha..." com a quebra de linha do HTML com o resultado da função texto. A função texto chamará a si mesma, e vai ficar fazendo isso infinitamente.

Teste esse comportamento ao carregar a página HTML. Coloque um valor qualquer, por exemplo, o número quatro, e ao clicar em "Exibir", você verá que nada acontecerá. Teremos um erro, e ao entrar na ferramenta de depuração, de fato, será criado um erro: "Uncaught RangeError: Maximum call stack size exceeded". É um erro de limites, porque ele excedeu o tamanho máximo da pilha de chamadas, gerado exatamente pela recursão infinita.

Claramente, a maneira errada de se usar recursão em programação é a sua forma infinita. O problema do nosso exemplo é que a recursão implementada nele nunca para, e toda função recursiva tem que parar em algum momento. Esse ponto de parada é o que chamamos de caso base e eles, geralmente, estão em um comando if, onde a condição define o momento em que desejamos que a recursão pare. Portanto, uma recursão bem implementada tem, pelo menos, um caso base e um caso de recursão. Alguns autores também defendem o uso de uma condição de terminação, que funciona como um freio de emergência e garante que, em caso de entrada de dados incorretos, a recursão não seja executada. Note a diferença entre o caso base e a condição de terminação: o caso base é o objetivo de nossa função recursiva e a condição de terminação garante o tratamento de dados incorretos.

Vamos à correção do nosso exemplo? Para isso, considere que o usuário entra com a quantidade n de linhas que ele deseja que seja exibida na página. Nesse caso, observe que desejamos que a recursão pare quando não tivermos mais linhas para exibir, ou seja, o nosso caso base será quando n for igual a zero. Por outro lado, se o n for maior que zero, inserimos uma linha e fazemos a recursão. Além disso, vamos considerar que a função retornará uma mensagem de erro se recebermos um número negativo. Vejamos o resultado!

Veremos como é que fica a solução finita dessa recursão no nosso exemplo (Ver Código 2).

Código 2 - 13_2 Recursão Finita.html e 13_2 Recursão Finita.js

O HTML é exatamente o mesmo e no JavaScript temos a recursão finita. A função exibir também é praticamente a mesma, só que quando chamarmos a função texto será passado para ela o número de linhas que se deseja exibir.

Veja que a nova função texto será uma função recursiva, mas finita, ou seja, ela irá parar. Iremos guardar a variável retorno e colocaremos uma condição de terminação caso o n a ser passado seja negativo. Se ele for negativo, não poderá ser exibido um número negativo de linhas, então, ele vai dar como retorno o texto "Insira um número maior ou igual a zero".

Caso contrário, entraremos no caso base, que é quando o n for igual a zero. Se o n for igual a zero (linha 15), o retorno será o texto "FIM". Temos também o caso recursivo, que é quando o n é maior que zero. Observe que o else (linha 19) será exatamente nosso caso recursivo, porque o n não é negativo e também não é zero, então ele só poderá ser maior do que zero. Temos como retorno o texto "Linha " concatenado com n, concatenado com a quebra de linha do HTML, concatenado com a chamada da função texto, uma chamada recursiva, passando o n-1.

Dessa forma, a função texto ficará chamando, criando as linhas, até chegar ao valor de n igual a zero, onde colocaremos a palavra "FIM". Ao carregar a página HTML, e colocar, por exemplo, o valor 5, e clicar em "Exibir", serão exibidos, de fato, "Linha 5", "Linha 4", "Linha 3", "Linha 2", "Linha 1", até o caso base, o "FIM". Veja a Figura 7.

Então conseguimos resolver aquele problema do erro da recursão infinita usando o caso base e o caso recursivo, e sempre garantindo que estamos nos aproximando do caso base, ok?

Você entendeu bem como funciona o nosso programa? Veja agora como funciona a pilha de chamadas de função em um exemplo (Figura 8). Suponha que o valor inserido seja 3. Nesse caso, o programa chamará a função texto usando 3 como parâmetro, ou seja, texto(3). Porém, o retorno de texto(3) é a string "Linha 3 <br>" concatenada com o retorno de texto(2). Continuando, o retorno de texto(2) é a string "Linha 2 <br>" concatenada com o retorno de texto(1). Da mesma maneira, o retorno de texto(1) é a string "Linha 1 <br>" concatenada com o retorno de texto(0). Finalmente, com essa chamada, chegamos ao caso base, o valor 0, pois, nesse caso, a função texto não faz recursão e simplesmente retorna a string "FIM".

A partir deste momento, começamos a "desempilhar" os resultados. Acompanhe na Figura 9 essa ação.

Dessa forma, o retorno de texto(1) é a string "Linha 1 <br>" concatenada com a string "FIM".

Essa string é concatenada ao final da string "Linha 2 <br>" para gerar o retorno de texto(2).

Da mesma maneira, concatenamos o retorno de texto(2), ou seja, a string "Linha 2 <br>" + "Linha 1 <br>" + "FIM", ao final da string "Linha 3 <br>", para gerar o retorno de texto(3).

Dessa forma, chegamos, finalmente, ao resultado da chamada texto(3), ou seja, a string "Linha 3 <br>" + "Linha 2 <br>" + "Linha 1 <br>" + "FIM", a qual é finalmente exibida na tela.

Agora, encare o mesmo exemplo de uma outra maneira. Imagine que temos pessoas e que elas sabem fazer a mesma coisa: receber um bilhete com uma solicitação de texto contendo um valor n e retornar um bilhete com o texto resultante. Para isso, veja que eles executam o mesmo código. No entanto, existe uma restrição importante. Cada pessoa só pode gerar um texto de cada vez. Por isso, caso eles precisem chamar a função novamente para conseguir gerar o seu texto, devem repassar um bilhete com essa chamada para outra pessoa e aguardar o retorno de um bilhete com o resultado. É exatamente isso que acontece na recursão marcada de amarelo no slide (Figura 10).

Veja uma simulação de como aconteceria o que foi descrito anteriormente na geração da chamada texto(3). Para isso, usaremos quatro pessoas: Marcel, Lauana, Vinicius e Gabi.

É claro que não dá para ficar fazendo esse tipo de cálculo manualmente todas as vezes. No entanto, podemos usar a ferramenta de depuração dos navegadores para fazer esse acompanhamento. Vamos ver como funciona no Chrome?

Voltaremos ao exemplo (Ver Código 2) só que desta vez usaremos a ferramenta de depuração para acompanhar o funcionamento da pilha de chamadas.

Entraremos na ferramenta de depuração, faremos um breakpoint na chamada da função texto e pediremos para ser exibido, por exemplo, o número 3. Então fizemos um breakpoint, estamos com nosso Scope (escopo), onclick chamou função exibir, e se dermos um step into, então onclick chamará função exibir e a função exibir chamará a função texto. Estamos com n atualmente igual a 3 e retorno ainda é indefinido (linhas 7 e 8). Como 3 é maior que 0, o n pulará a condição de terminação, o caso base, e entrará em recursão, na condição else. Veja a Figura 11.

Então o retorno estará com o valor vazio, e se fizermos um step into, chamaremos novamente a função texto, veja que na call stack colocamos uma nova chamada à função texto, o n agora é o 2 e o retorno dessa nova chamada é undefined. Veja a Figura 12.

E novamente, 2 > 0, e o comportamento será exatamente o mesmo. Dando step into, voltamos de novo e colocamos novamente uma chamada a função texto na call stack, só que o n agora é 1, ok? Novamente 1 > 0, vai acontecer a mesma coisa, chamamos função texto, colocamos uma quarta chamada, só que o n agora é zero. Veja a Figura 13.

Como temos o n igual a 0, ele não satisfaz a condição de terminação, mas ele vai entrar no caso base e o retorno receberá o valor "FIM". Temos que o retorno é "FIM" e quando voltarmos à chamada, teremos a situação em que no escopo o n será 0. Daremos um step into, desempilharemos aquela chamada, assim, teremos só três chamadas da função texto, e no escopo o n será 1 e o retorno será "Linha 1 <br> FIM" com resultado da última chamada. Daremos mais um step into, e teremos o retorno já pronto para ser retornado para a chamada anterior. Ao desempilharmos mais um texto da pilha, estaremos naquela chamada em que o n era igual a 2 e o retorno será "Linha 2 <br> Linha 1 <br> FIM". Montamos o valor de retorno e desempilhamos mais uma chamada de texto da pilha para a chamada onde o n era 3, e o retorno será "Linha 3 <br> Linha 2 <br> Linha 1 <br> FIM". Preparamos o valor de retorno e retornamos, dessa vez, desempilhamos a última chamada que tinha na pilha e voltamos para a função exibir.

O valor da variável resultado será exatamente o último texto que vimos: "Linha 3 <br> Linha 2 <br> Linha 1 <br> FIM", e estamos prontos pra alterar na página o valor do parágrafo exibindo esse resultado. E você verá que, de fato, ele aparecerá na página HTML. Veja a Figura 14.

Dessa forma, podemos acompanhar esse processo recursivo usando a ferramenta de depuração, principalmente o call stack, o escopo, e se desejar também o watch, que mostra as expressões.

Legal, né?

Ficamos por aqui! Na próxima videoaula, você verá vários exemplos de aplicações de recursão aos números.