PauloRB.dev

Desenvolvedor de Software

Recursão com a Torre de Hanoi em PHP | PauloRB.dev Recursão com a Torre de Hanoi em PHP - PauloRB.dev
Recursão com a Torre de Hanoi em PHP

Recursão com a Torre de Hanoi em PHP

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

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.

Mais Posts

Script para automatizar as instalações de extensões do php em distribuições LINUX

Script para automatizar as instalações de extensões do php em distribuições LINUX

Publiquei neste artigo https://paulorb.dev/alternar-entre-multiplas-versoes-no-php/ formas de como instalar diversas versões do PHP em distros Linux mas surgiu um problema que... Leia mais

A função WITH RECURSIVE no PostgreSQL

A função WITH RECURSIVE no PostgreSQL

A função WITH RECURSIVE no PostgreSQL é uma ferramenta poderosa para a execução de consultas recursivas em bancos de dados.... Leia mais

Como Usar a Porta 443 para Conexões SSH com o Bitbucket e Contornar Restrições de Rede

Como Usar a Porta 443 para Conexões SSH com o Bitbucket e Contornar Restrições de Rede

Se você já se deparou com a frustrante mensagem de erro “ssh: connect to host bitbucket.org port 22: Network is... Leia mais

Converter campos de um banco de dados do tipo json para array com laravel

Converter campos de um banco de dados do tipo json para array com laravel

Hoje boa parte dos banco de dados relacionais podem armazenar campos com valores no formato JSON o que garante maior... Leia mais