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.
