# Recursão — Caso-base e Caso Recursivo

Irei escrever sobre algoritmos e estruturas de dados em paralelo com o livro [Entendendo Algoritmos: Um Guia Ilustrado Para Programadores e Outros Curiosos](https://www.amazon.com.br/Entendendo-Algoritmos-Ilustrado-Programadores-Curiosos/dp/8575225634/ref=sr_1_1?qid=1677021688&refinements=p_27%3AAditya+Y.+Bhargava&s=books&sr=1-1) de Aditya Y. Bhargava.

Estou usando o livro para aprender sobre algoritmos e estruturas de dados, e escrever sobre o que estou aprendendo, pois acredito que assim eu consiga fixar melhor o conteúdo.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586257784/aa9aa18e-39b7-4861-9428-d8f9806b5da5.jpeg align="left")

### Capítulo 3 — Recursão

Recursão é um conceito muito importante em programação, e é um dos conceitos mais difíceis de entender. A ideia de recursão é que uma função chame ela mesma, e que essa função tenha uma condição de parada. A condição de parada é o ponto em que a função não chama ela mesma novamente, e retorna um valor.

No livro Entendendo Algoritmos, o autor Aditya Y. Bhargava usa o exemplo de uma pessoa que está procurando uma chave dentro de uma caixa, mas dentro dessa caixa possui diversas caixas e a pessoa precisa fazer uma busca dentro de cada uma dessas caixas.

Irei usar o mesmo exemplo para explicar o conceito de recursão, mas farei um código em PHP para exemplificar.

```php
function procurarChave($caixa) {
    if (caixaEstaVazia($caixa)) {
    return null;
} else if (chaveEstaNaCaixa($caixa)) {
    return $caixa;
} else {
    foreach ($caixa->caixas as $caixa) {
    $resultado = procurarChave($caixa);
        if ($resultado != null) {
            return $resultado;
        }
    }
}

return null;
}
```

Dentro da função procurarChave, temos uma condição de parada, que é quando a caixa está vazia, e não há mais caixas para procurar. Caso a caixa não esteja vazia, a função chama ela mesma, passando como parâmetro a caixa que está dentro da caixa atual.

No momento em que a função chama ela mesma, ela cria uma nova instância da função, e cria uma nova pilha de execução. Quando a função termina de executar, ela retorna o valor, e a pilha de execução é removida da memória.

A função procurarChave é uma função recursiva, pois ela chama ela mesma.

### Caso Base e Caso Recursivo

Uma das coisas mais comuns de acontecer quando se está aprendendo sobre recursão é fazer um loop infinito, pois esquecemos de colocar a condição de parada. Para evitar esse tipo de problema, é importante entender o conceito de caso base e caso recursivo.

Vou usar novamente um exemplo do livro Entendendo Algoritmos para explicar o conceito de caso base e caso recursivo. Vou usar JavaScript para exemplificar.

A função recursiva abaixo é uma função que imprime todos os números no console, e adiciona 1 no número a cada chamada da função.

```javascript
function imprimirNumero(numero) {
    console.log(numero);
    imprimirNumero(numero + 1);
}
```

Noto que a função não tem uma condição de parada, e que ela chama ela mesma a cada execução. Isso faz com que a função entre em um loop infinito, e que o navegador fique travado.

Para evitar esse problema, é necessário adicionar uma condição de parada, que é o caso base. O caso base é o ponto em que a função não chama ela mesma novamente, e retorna um valor.

```javascript
function imprimirNumero(numero) {
    console.log(numero);
    if (numero < 100) {
        imprimirNumero(numero + 1);
    }
}
```

Agora a função não entra em um loop infinito, pois ela tem uma condição de parada. A função chama ela mesma até que o número seja menor que 100, e quando o número for maior ou igual a 100, a função não chama ela mesma novamente, e retorna o valor.

### A Pilha de Chamadas

O seu computador organiza a memória em pilhas, e cada pilha é chamada de stack. Quando uma função é chamada, ela cria uma nova stack, e quando a função termina de executar, a stack é removida da memória.

Veja o exemplo abaixo em Python:

```python
def test():
    print("Aqui está a função test")
    test2()
    print("Aqui está a função test novamente")
    test3()

def test2():
    print("Aqui está a função test2")

def test3():
    print("Aqui está a função test3")

test()
```

Perceba que a função test chama a função test2, e depois chama a função test3. Quando a função test termina de executar, a stack é removida da memória, e a função test2 é executada. Quando a função test2 termina de executar, a stack é removida da memória, e a função test3 é executada. Quando a função test3 termina de executar, a stack é removida da memória, e o programa termina de executar.

Talvez tenha ficado um pouco confuso, vou tentar deixar mais claro.

Essa é a pilha de execução do programa:

![](https://cdn-images-1.medium.com/max/800/1*JkmGi-0I_UEkMNBXv40eYg.png align="left")

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586260023/8bcace23-6fcc-43f8-bd72-bc0669c1de8b.png align="left")

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586261682/1bb2968a-f8c6-4120-90c5-5410136c42fc.png align="left")

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586264091/534bb2a9-c28c-4484-9891-cf9ce68682cf.png align="left")

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586265709/62114813-cf88-4912-aef4-28c42cb9a79e.png align="left")

### Pilha de Chamadas e Recursão

Agora que você já sabe o que é uma pilha de chamadas, vamos ver como a recursão funciona com a pilha de chamadas.

Vou usar o mesmo exemplo do livro Entendendo Algoritmos para exemplificar. Vou usar JavaScript para exemplificar.

```javascript
function fatorial(n) {
    if (n == 1) {
        return 1;
    } else {
        return n * fatorial(n - 1);
    }
}
```

A função fatorial recebe um número como parâmetro, e retorna o fatorial desse número. A função chama ela mesma, passando como parâmetro o número atual menos 1.

Quando a função fatorial é chamada, ela cria uma nova stack, e quando a função termina de executar, a stack é removida da memória.

Mas nesse caso, diferente do exemplo anterior, a função chama ela mesma antes de terminar de executar. Isso faz com que a função fatorial seja chamada novamente, e uma nova stack seja criada.

Então, no caso de um factorial de 5, a função fatorial é chamada 5 vezes, e 5 stacks são criadas. Veja o exemplo abaixo:

```javascript
fatorial(1)

fatorial(2)

fatorial(3)

fatorial(4)

fatorial(5)
```

Perceba que sempre que a função fatorial é chamada, ela cria uma nova stack, e quando a função termina de executar, a stack é removida da memória.

Lembre-se, sempre que uma função é chamada, ela cria uma nova stack, e ela só é removida da memória quando a função termina de executar.

### Recapitulando

* Uma função recursiva é uma função que chama ela mesma.
    
* Uma função recursiva precisa de um caso base, que é o ponto em que a função não chama ela mesma novamente, e retorna um valor.
    
* Caso não tenha um caso base, a função entra em um loop infinito.
    
* Quando uma função é chamada, ela cria uma nova stack, e quando a função termina de executar, a stack é removida da memória.
    
* Cada stack é criada quando uma função é chamada, sendo removida da memória quando a função termina de executar.
    

### Finalização

Dessa vez eu tentei usar mais de uma linguagem para exemplificar para deixar claro que estrutura de dados e algoritmos são independentes de linguagem.

Essa foi uma pequena documentação dos meus estudos, espero que possa ajudar mais pessoas.  
Qualquer dúvida, correção ou sugestão pode deixar nos comentários.