PauloRB.dev

Recursão com a Torre de Hanoi em PHP

Por Paulo RB em 11/04/2024

Recursão é um conceito essencial em programação que se refere a uma função que se chama a si mesma dentro de sua definição. Embora possa parecer complicado à primeira vista, a recursão é uma ferramenta poderosa e elegante para resolver problemas complexos de maneira simplificada. Neste artigo, exploraremos como a recursão pode ser aplicada em PHP para resolver um dos quebra-cabeças mais fascinantes e educativos da ciência da computação: a Torre de Hanoi.

A recursão acontece quando uma função chama a si mesma. Cada chamada da função trabalha em uma parte menor do problema, aproximando-se de uma condição que não exige mais chamadas recursivas, conhecida como caso base ou ponto de parada. Sem alcançar o caso base, a função continuaria se chamando infinitamente, o que resulta em um erro de “estouro de pilha” ou “loop infinito”. Portanto, o projeto de uma função recursiva deve garantir que ela sempre tenha um ponto de parada.

A Torre de Hanoi é um problema clássico de recursão que envolve mover uma série de discos de um pino para outro, com a condição de que um disco maior não pode ser colocado em cima de um disco menor e que apenas um disco pode ser movido de cada vez. A solução para o problema da Torre de Hanoi é elegante e demonstra bem o poder da recursão.

Vamos ver como isso pode ser implementado em PHP:

function torreDeHanoi($n, $origem, $destino, $auxiliar) {
    if ($n === 1) {
        echo "Mova o disco 1 de $origem para $destino" . PHP_EOL;
        return;
    }
    // Move n-1 discos de origem para auxiliar, usando destino como auxiliar
    torreDeHanoi($n-1, $origem, $auxiliar, $destino);
    // Move o disco restante de origem para destino
    echo "Mova o disco $n de $origem para $destino" . PHP_EOL;
    // Move os n-1 discos de auxiliar para destino, usando origem como auxiliar
    torreDeHanoi($n-1, $auxiliar, $destino, $origem);
}

// Quantidade de discos
$discos = 3;
torreDeHanoi($discos, 'A', 'C', 'B');