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:

Copy Code


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');

Neste exemplo, a função torreDeHanoi é definida para resolver o problema para n discos, com os parâmetros origem, destino, e auxiliar indicando os pinos. Inicialmente, você move n-1 discos do pino de origem para o pino auxiliar, usando o pino de destino como auxiliar. Em seguida, você move o disco restante diretamente do pino de origem para o pino de destino. Finalmente, você move os n-1 discos que foram colocados no pino auxiliar para o pino de destino, usando o pino de origem como auxiliar.

O que torna a Torre de Hanoi um exemplo fascinante de recursão é a maneira como o problema é quebrado em problemas menores que têm a mesma natureza do problema original, permitindo uma solução elegante e direta através de chamadas recursivas.

A recursão é uma técnica fundamental na programação, permitindo aos desenvolvedores escrever código limpo e eficiente para resolver problemas complexos. O exemplo da Torre de Hanoi em PHP demonstra como abordagens recursivas podem simplificar a solução de problemas que, à primeira vista, podem parecer intimidadores. Ao dominar a recursão, os desenvolvedores podem enfrentar desafios de programação mais complexos com confiança e eficiência.