Substituindo a recursão por uma pilha

Usar recursão para desenvolver um algoritmo deixa o código mais elegante e simples de entender. Mas perdemos a elegância e a simplicidade quando o algoritmo tem que ser debugado ou interpretado para solucionar um bug. Então neste post mostrarei dois exemplos para substituir a recursão por uma estrutura de dados conhecida como pilha ou LIFO (Last In First Out).

O primeiro exemplo é o algoritmo para cálculo do fatorial desenvolvi um classe que calcula o fatorial recursivamente def fatorialRecursive(self, x): e não recursivo def fatorialSimulateRecursive(self, x): o qual calcula o fatorial usando uma pilha, com esse método conseguimos calcular o fatorial de !1000 já com o método recursivo recebemos a seguinte exceção RuntimeError: maximum recursion depth exceeded. Eis uma vantagem de usar uma pilha ao invés de usar recursão.

#!/usr/bin/env python
#  -*- coding: iso-8859-1 -*-
#  This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; version 2 of the License.
#  This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# author: Marlon Petry
# Date: 2008/07/06
# Function: Remove Recursion with one Stack in python
#
class Stack:

     def __init__(self):
         self.stack = []

     def push(self,object):
         self.stack.append(object)

     def pop(self):
         if len(self.stack) == 0:
            raise "Error", "stack is empty"
         obj = self.stack[-1]
         del self.stack[-1]
         return obj

     def isempty(self):
         if len(self.stack) == 0:
            return False
         else:
            return True

class CalculusFatorial:
    stack = Stack()
    def fatorialRecursive(self, x):
        if x == 0:
            return 1
        else:
            return (x * self.fatorialRecursive(x - 1))

    def fatorialSimulateRecursive(self, x):
        factorial = 1;
        while x > 0:
            self.stack.push(x)
            x -= 1

        while self.stack.isempty():
            factorial *= self.stack.pop()

        return factorial

calc = CalculusFatorial()
print calc.fatorialRecursive(950)
print "Não recursivo"
print calc.fatorialSimulateRecursive(950)
calc.show()

O segundo algoritmo é a Torre de Hanoi, muito mais complexo para remover a recursividade fiquei uns dois dias tentando resolver até que encontrei um artigo que descreve como remover a recursão http://obelix.ee.duth.gr/~apostolo/TowersOfHanoi/index.html#non-recursive. Então segui os passos descritos no artigo e consegui chegar a solução.

#!/usr/bin/env python
#  -*- coding: iso-8859-1 -*-
#  This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; version 2 of the License.
#  This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# author: Marlon Petry
# Date: 2008/07/06
# Function: Tower Hanoi Remove Recursion with one Stack in python
#
import pdb
import sys

class Stack:

   def __init__(self):
       self.stack = []

   def push(self,object):
       self.stack.append(object)

   def pop(self):
       if len(self.stack) == 0:
          raise "Error", "stack is empty"
       obj = self.stack[-1]
       del self.stack[-1]
       return obj

   def isempty(self):
       if len(self.stack) == 0:
          return False
       else:
          return True

class Hanoi:
    stack = Stack()
    def hanoi(self,disk,src,dst,temp,tipo):
        if(disk == 1):
            print "Disk %d Move da haste %d para haste %d tipo %d" % (disk,src,dst,tipo)
        else:
	    #pdb.set_trace()
            self.hanoi(disk - 1 , src, dst, temp,1)
            print "Disk %d Move da haste %d para haste %d tipo %d" % (disk,src,temp,tipo)
            #pdb.set_trace()
	    self.hanoi(disk - 1, dst, temp, src,2)

    def hanoiNotRecursive(self,disk,src,dst,temp,tipo):
        flag = -1;

        while disk > 0:
 	    self.stack.push((disk, src, dst, temp,1))
	    disk = disk -1
	    flag += 1
	while flag >= 0:

	    disk,src,dst,temp,tipo = self.stack.pop()
	    flag -=1;
	    if disk == 1:
	    	print "Disk %d Move da haste %d para haste %d tipo %d" % (disk,src,dst,tipo)
            else:
		print "Disk %d Move da haste %d para haste %d tipo %d" % (disk,src,temp,tipo)
	    disk -= 1
	    while disk > 0:
	      self.stack.push((disk, dst, temp, src,2))
              disk = disk - 1
	      flag += 1

testeHanoi = Hanoi()
testeHanoi.hanoi(18,1,2,3,0)
print "Hanoi not recursive"
testeHanoi.hanoiNotRecursive(3,1,2,3,1)

Não cheguei a calcular o tempo de execução para ver se existe diferença talvez faça isso em um próximo post.

Estou participando do concurso Intel Moblin com o projeto Great Picture se achar interessante o projeto seu voto será muito bem vindo mais detalhes sobre o projeto aqui.