Algoritmos 2

Algoritmos recursivos

O padrão de algoritmos iterativos descreve soluções para a maioria dos problemas práticos do dia a dia. 

Entretanto ocasionalmente pode ser necessário usar outros tipos de algoritmos. 

Em particular para certos problemas complexos pode ser usado o paradigma divide-and-conquer, onde  particionamos o problema inicial em problemas menores cujas soluções podem ser combinadas para resolver o problema inicial.

Uma variante deste paradigma consiste em resolver versões do mesmo problema mas de tamanho menor e depois combinar estas soluções numa solução geral. 

Para conseguir isto precisaremos saber resolver algum caso "pequeno" do problema e dai conseguir resolver um caso um pouco maior. Por indução isto em geral basta para resolver qualquer tamanho do problema. Vamos chamar este padrão de algoritmos recursivos.

Vejamos um exemplo, o venerável problema das Torres de Hanoi.

Neste problema clássico são dadas três hastes e uma pilha de discos de tamanhos diferentes. Inicialmente os discos estão todos empilhados em tamanho decrescente numa haste. Pede-se mover todos discos numa pilha em outra haste. Cada movimento consiste em mover um disco de uma haste para outra sem jamais colocar um disco sobre outro menor.

Por exemplo aqui se mostra uma solução para oito discos (demora uns 5 minutos!):

Como fazer um procedimento para resolver isto? Usar nosso paradigma iterativo parece complicado demais neste caso. Parece mais um caso para usar recursividade.

Seja n o número de discos numa instância deste problema. Vamos considerar o caso "pequeno" em que n = 1. A solução é simples, basta mover o único disco para a haste livre (há duas hastes livres). Um só movimento. Ligeiramente ridiculo, não é?

Bem e como proceder para o caso geral de n discos? Imagine que sabemos resolver para n - 1 discos. Esta é nossa hipótese de indução: dada uma pilha de n-1 discos sabemos como move-los para uma haste livre. 

Dado isto o procedimento de solução fica simples!

Imagine o problema com n discos na haste A, como na figura acima. Por hipótese sabemos resolver o problema para n - 1 discos, então movemos os n - 1 discos superiores da haste A para a haste B.

Ficou um só disco na haste A, justo o maior, e a haste C está vazia. Mas nós sabemos resolver o caso de um só disco, como mencionado acima. Então movemos o disco solitário da haste A para a haste C.

Ficamos com n - 1 discos empilhados na haste B e o disco grande já na haste C.

Aplicamos novamente a hipótese de indução e movemos os discos da haste B sobre o disco já na haste C.

E o problema está resolvido!

A solução passo a passo pode ser representada assim:

Na figura os passos de 1 a 3 correspondem a usar nossa hipótese de indução para n-1 discos, o passo 4 é o caso de mover um só disco e os passos 5 a 7 correspondem ao segundo uso da hipótese de indução.

Vejamos como fica o pseudo código deste algoritmo:

# n é o numero de discos, 
# X é a haste inicio, Y é a haste destino e Z é uma haste livre
defina Hanoi( n, x, y ):
        se n == 1:
                 mova o disco da haste X para a haste Y
                 retorna

        Hanoi(n - 1, X, Z)

        Hanoi(1, X, Y)

        Hanoi(n - 1, Z, Y)

        retorna
                  
 Como vemos a função Hanoi() chama a sí mesma dentro de seu corpo. Daí que este tipo de algoritmo é chamado de recursivo. 

Note o ponto essencial de que a chamada recursiva de Hanoi é para um problema menor (n - 1 em vez de n). 

Algoritmos recursivos são um recurso poderoso mas que requer muito cuidado em sua utilização e bastante experiência para bons resultados. Felizmente na prática você dificilmente terá de construi-los.

Python icon by kaelan