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.
