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 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.

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.

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.

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.

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:

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:

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.

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:

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.