Recursão

A recursão é um método de resolução de problemas onde o dividimos em subproblemas menores até chegar a um problema pequeno suficiente para ser resolvido de forma trivial. Ocorre quando uma função ou um algoritmo se refere a si mesmo. Um exemplo seria por exemplo buscar uma palavra em um dicionário, no caso a palavra ‘casa’. Podemos escrever um algoritmo para realizar essa pesquisa:

1                    Pegue o dicionário

2                    Abra na página do meio do dicionário

3                    Olhe para a página

4                    Se ‘casa’ estiver na página

5                            Fim

6                    Se ‘casa’ estiver na metade à esquerda

7                            Buscar na metade esquerda

8                    Se ‘casa’ estiver na metade à direita

9                            Buscar na metade esquerda

10                 Senão

11                         Fim

       Ao olharmos esse pseudocódigo parece um ciclo infinito, mas estamos na verdade dividindo o problema ao meio a cada iteração e parando quando não houver mais páginas no dicionário. Um exemplo clássico de problema que pode ser resolvido utilizando recursão é cálculo do fatorial de um número ‘n’. Definindo a função fatorial em JavaScript e realizando a chamada da função para calcular o fatorial de 5.

Observando a função fatorial temos a estrutura de uma função recursiva. Inicialmente é preciso definir o ‘base case’, ou seja, o caso mais trivial e que determina o final da recursão. Para o cálculo do fatorial este caso é quando chegamos ao fatorial do número 1, que vale 1. Após o ‘base case’, definimos o ‘recursive case’, que é quando a função chama a si mesma com parâmetro que a encaminha para o ‘base case’, neste exemplo (n – 1). Se executamos a função para ver cada passo, podemos perceber que:

1° passo:     fatorial(5) = 5 * fatorial(4)

2° passo:     fatorial(4) = 4 * fatorial(3)

3° passo:     fatorial(3) = 3 * fatorial(2)

4° passo:     fatorial(2) = 2 * fatorial(1)

5° passo:     fatorial(1) = 1

     Para cada passo acima, as execuções vão sendo empilhados em uma parte da memória chamada ‘stack’ sendo a primeira mais na base e a última no topo. Quando a recursão encontra o ‘base case’, o valor final é resolvido a com o valor do ‘base case’, aqui o fatorial(1), a pilha vai sendo resolvida até chegar na base com o valor 120.

                Daí podemos então definir as três leis da recursão:

1. Um algoritmo recursivo deve ter um caso básico
2. Um algoritmo recursivo deve mudar o seu estado e se aproximar do caso básico.
3. Um algoritmo recursivo deve chamar a si mesmo, recursivamente.

      Com essas três leis em mente, sempre que encontrar um problema que se repete, você pode utilizar a recursão para criar uma solução elegante e eficiente!

Referências

[1] Como pensar como um cientista da computação. Recursão. Disponível em <https://panda.ime.usp.br/pensepy/static/pensepy/12-Recursao/recursionsimple-ptbr.html>

Acesso em: 20/02/2020.