Revendo a Recursão

A recursão de dados proporciona toda a elegância da recursão sem nenhum inconveniente.

por Brian Kierstead

Praticamente todo programa de pintura conhecido pelo homem vem equipado com um recurso chamado preenchimento com cor. Para usá-lo, selecione uma cor, clique na área da figura que deseja pintar e, prontinho, a área é preenchida com a nova cor (veja a Figura 1). Recentemente, tive de implementar esse recurso em um programa que desenvolvi. Com todos os programas de pintura que existiam no mercado, eu sabia que não teria dificuldade em encontrar amostras de código na Internet. Apesar disso, obtive resultados inesperados: todas as amostras que encontrei eram recursivas.

Figura 1: O FloodFill em ação

. Dê uma olhada nestas imagens de antes e depois para entender o que o FloodFill pode fazer no Microsoft Paint. Quando você clica em algum lugar dentro do círculo, o FloodFill preenche o círculo com a nova cor.

Ainda que a recursão seja uma solução elegante para muitos problemas, ela possui algumas limitações. O número de vezes que uma função pode chamar a si mesma é limitado pela quantidade de espaço de pilha disponível. Infelizmente, você não tem controle sobre o tamanho da pilha de chamadas ou sobre como ela é alocada. Se você tiver uma grande quantidade de dados para processar, ou se cada chamada de função acrescentar muitos dados à pilha, acabará ficando sem espaço de pilha. Isso resultará em uma cruel mensagem do VB: “Run-time error: ‘28’ Out of Stack Space” (“Erro em tempo de execução: ‘28’ Espaço de pilha esgotado”).

Apesar de querer que seu programa lide com dados de tamanho variável, você não tem como saber de antemão de quanto espaço de pilha ele precisará. Além disso, se desejar usar seu código em outro lugar, precisará estar ciente de que os tamanhos de pilha variam entre as plataformas.

Lembre-se de que uma função recursiva não irá parar de chamar a si mesma, mas, ao mesmo tempo, precisará haver um meio de sair sem que faça isso. Veja como exemplo esta função, que calcula fatoriais de forma recursiva:

Listagem 1: Calculando fatoriais

Function Factorial(n as Long) as Long
	" Sai se n igual a zero.
	if n = 0  then
		Factorial = 1
		Exit Function
	End if
	Factorial = Factorial(n - 1)
End Function

Essa função continua chamando a si mesma, decrementando o número em um a cada vez, até atingir zero. A função então retorna um, sem chamar a si mesma. Esse valor é propagado de volta, completando cada chamada recursiva, até a resposta final ser calculada.

Para possibilitar a recursão, o sistema operacional fornece a cada programa uma pequena quantidade de espaço na memória, a pilha de chamadas. A rigor, uma pilha é uma estrutura de dados que retorna itens posicionados nela na ordem inversa em que foram adicionados. Em outras palavras, o último item posicionado na pilha deve ser o primeiro removido, e o primeiro item dever ser o último. Esse é o comportamento conhecido como LIFO (last in, first out - último a entrar, primeiro a sair).

Agora que você já sabe o que é recursão e suas limitações, examine a função FloodFill (veja a Listagem 1). Para chamar a função FloodFill, passe a ela o ponto em que o usuário clicou, a cor da área que deseja preencher e a cor de preenchimento.

Este método recursivo tradicional permite o uso do recurso FloodFill para o preenchimento de um vetor que contém dados de imagem.

Listagem 2: Método recursivo tradicional

Sub FloodFill(x As Long, y As Long, oldcolor As _
	Long, newcolor As Long)

	Dim i, j	As Long

	" Salva se fora dos limites
	If x = Image_Size_x Or y = Image_Size_y Then
	Exit Sub
	End If

	" Salva se o pixel atual não é da cor antiga
	If Image_Data(x, y) <> oldcolor Then
		Exit Sub
	End If

	" Altera o pixel para a nova cor
	Image_Data(x, y) = newcolor

	" Verifica cada pixel tocando o atual
	FloodFill x - 1, y, oldcolor, newcolor
	FloodFill x - 1, y - 1, oldcolor, newcolor
	FloodFill x, y - 1, oldcolor, newcolor
	FloodFill x + 1, y - 1, oldcolor, newcolor
	FloodFill x + 1, y, oldcolor, newcolor
	FloodFill x + 1, y + 1, oldcolor, newcolor
	FloodFill x, y + 1, oldcolor, newcolor
	FloodFill x - 1, y + 1, oldcolor, newcolor

End Sub

Primeiro, a FloodFill verifica as condições que lhe permitirão sair sem chamar a si mesma. Em outras palavras, ela verificará se o ponto está dentro dos limites da imagem e se a cor está correta. Se o ponto for válido, defina-o com a nova cor e, em seguida, chame a FloodFill para cada um dos pontos vizinhos. Se o ponto não for válido, saia da iteração atual. A FloodFill tem boa aparência no papel, mas, se você tentar preencher uma área que seja de 64x64 pixels ou mais, faltará espaço de pilha e ocorrerá o erro em tempo de execução mencionado anteriormente.

Execução da Recursão de Dados

Felizmente, você pode resolver esse problema de outra maneira: basta usar a recursão de dados. Usando uma única função para fazer o loop por todos os dados, você evita os problemas associados à recursão convencional. Ainda que precise de uma pilha de chamadas, você mesmo poderá implementá-la e criar uma que seja dimensionada dinamicamente e em tempo de execução.

O método Init() define o tamanho da pilha, Push() posiciona os dados nela e Pop() remove seus dados (veja a Listagem 2). O método Pop() também aceita um parâmetro opcional que permite a remoção de um número arbitrário de itens do alto da pilha. A propriedade Value permite a exibição e a alteração dos dados que estejam na pilha no momento. Ela também aceita um índice, que é relativo ao topo da pilha. Use Value(0) para obter o item superior da pilha. Para obter o item seguinte, use Value(1), e assim sucessivamente. CStack também expõe isEmpty(), um método que retorna True quando a pilha está vazia. Clear() reinicializa a pilha toda. Internamente, CStack armazena dados no vetor m_stack, que você pode dimensionar com uma chamada de Init(0). Dois índices controlam o acesso a m_stack(): m_stackPtr, que aponta para o alto da pilha, e m_stackTop, que controla quantos itens você pode colocar na pilha. Quando um item é acrescentado à pilha, m_stackPtr é incrementado em um; quando é retirado da pilha, é decrementado de um.

Listagem 3: Implementação da classe CStack

Private m_stack()		As Long
Private m_stackPtr		As Long
Private m_topPtr			As Long

Public Property Let Value(ByVal _
	IndexFromTop As Long, ByVal vData As Long)
	m_stack(m_stackPtr - IndexFromTop) = vData
End Property

Public Property Get Value(ByVal _
	IndexFromTop As Long) As Long
	If m_stackPtr - IndexFromTop >= 0 Then
		Item = m_stack(m_stackPtr - IndexFromTop)
	Else
		Err.Raise vbObjectError + 1, _
			"CStack:Item", "Index exceeds stack range"
	End If
End Property

Private Sub Class_Initialize()
	m_stackPtr = -1
End Sub

Public Sub Init(size As Long)
	ReDim m_stack(size)
	m_topPtr = size - 1
End Sub

Public Sub Push(ByVal Item As Long)
	If m_stackPtr < m_topPtr Then
		m_stackPtr = m_stackPtr + 1
		m_stack(m_stackPtr) = Item
	Else
		Err.Raise vbObjectError + 1, _
			"CStack::Push", "Stack Overflow"
	End If
End Sub

Public Sub Pop(Optional ByVal nCount As Long = 1)
	If m_stackPtr >= 0 Then
		m_stackPtr = m_stackPtr - nCount
		If m_stackPtr < -1 Then
			m_stackPtr = -1
		End If
	Else
		Err.Raise vbObjectError + 2, _
			"CStack::Pop", "Stack is Empty"
	End If
End Sub

Public Function isEmpty() As Boolean
	isEmpty = False
	If m_stackPtr = -1 Then
		isEmpty = True
	End If
End Function
Public Sub Clear()
	m_stackPtr = -1
End Sub

Esta implementação do módulo da classe CStack permite o armazenamento de dados na pilha com Push. A propriedade Value permite a exibição e a atualização dos itens na pilha. Você pode remover itens individuais de uma pilha usando Pop ou todos os itens de uma vez com Clear. Use o método isEmpty para testar se a pilha está vazia.

É interessante observar que o método Clear() na verdade não remove os dados de m_stack(); ele simplesmente redefine m_stackptr como -1. Da mesma forma, o método isEmpty() verifica se m-stackPtr está definido como -1.

Se você tem uma pilha, pode implementar o preenchimento com cor usando recursão de dados. Ainda que essa função pareça mais complicada que a original, é semelhante; você até faz a chamada da mesma maneira. Comece acrescentando à pilha o ponto passado à função, juntamente com uma direção inicial, DIR_LF. Em seguida, há um loop; na verdade, dois. Esses loops Do encapsulam o comportamento recursivo dessa função.

Os dados do ponto atual (o do alto da pilha) são copiados para as variáveis temporárias current_x, current_y e current-direction. Sabe-se quantas vezes um ponto atinge o alto da pilha examinando-se a variável current_direction. Se ela for igual a DIR_LF, é a primeira vez.

Na primeira vez em que um ponto aparece no alto da pilha, é preciso verificar se ele é válido. No FloodFill, é necessário testar se o ponto está dentro dos limites da imagem e se a cor está correta. Neste caso, foi criada uma função de ajuda, CheckBounds(), para a execução do teste.

Toda vez que um ponto atinge o alto da pilha, seu contador de direção é incrementado em um, o que corresponde às constantes declaradas no início da função. Para mover um determinado ponto no sentido horário, acrescente cada um de seus vizinhos à pilha para posterior processamento.

Se um ponto for inválido, ele será retirado da pilha e o contador de direção do ponto anterior será incrementado em um. Se o ponto for válido, repita o processo para cada um dos pontos vizinhos desse novo ponto. Quando o contador de direção de um ponto atingir DONE, remova o ponto da pilha e mova para o ponto seguinte. O processo chega ao fim quando não há mais pontos na pilha.

A vantagem da FloodFill2 (veja as listagens A e B) é evidente. Como a função não chama a si mesma, você não precisa se preocupar com a falta de espaço na pilha de chamadas. Você pode processar quantos dados desejar e, mais importante, pode usar o preenchimento com cor em imagens de qualquer tamanho.

Sobre o autor

Brian Kierstead, nascido e criado na costa leste do Canadá, aprendeu a arte do desenvolvimento de softwares com as lagostas que pescou nas armadilhas do barco de pesca do seu pai. As lagostas, em troca de sua liberdade, ensinaram muitas coisas a Brian, incluindo o Visual Basic, o SQL Server e o COM.

Download do código referente a este artigo

Clique aqui para fazer o download.