Funções recursivas em AdvPL

Hoje vamos abordar o conceito de funções recursivas, com foco na linguagem AdvPL, com alguns exemplos de uso, e para cada exemplo será abordada uma alternativa para não usar recursividade. Trata-se de um artigo técnico, que explora um recurso abordado em programação de nível avançado.

Definição

Uma função ou rotina é classificada como recursiva, quando esta rotina realiza uma ou mais chamadas para ela mesma, de dentro do seu próprio código.

Exemplo 1 – Fatorial

Acho que o exemplo mais simples e mais utilizado para exemplificar uma função recursiva é o algoritmo para cálculo fatorial de um número. Vamos escrever esta rotina em AdvPL:

User Function TesteFat()
msginfo(Fatorial(4) , "Resultado do Fatorial")
Return
STATIC Function Fatorial( nNum )
Local nResult
If nNum > 1
  nResult := nNum * Fatorial( nNum - 1 ) 
Else
  nResult := 1
Endif
Return nResult

Se tudo der certo, a execução da função U_TESTEFAT deve mostrar uma mensagem contendo o número 24 ( 4! = 4x3x2x1 = 24 )

Reparem no corpo da função Fatorial(), caso o número recebido como parâmetro seja maior que um, o retorno da função será o número recebido como parâmetro multiplicado pelo retorno da própria função Fatorial(), chamada com o número recebido subtraído de uma unidade. Quando a função receber um valor que não é maior que 1, ela retorna 1.

Neste caso, ao informarmos o valor 4, a função chama ela mesma passando o valor 3, que por sua vez chama ela mesma novamente passando o valor 2, que por sua vez chama ela mesma com o valor 1, e neste ultimo caso a função retorna 1, que será multiplicado por 2 e retornado ( 2 ) , e este retorno multiplicado por 3 e retornado ( 6 ), e este por sua vez será multiplicado por 4 e retornado ( 24 ).

A utilização de recursão normalmente está sujeito ao limite de pilha de chamada de funções da linguagem em uso. No caso do AdvPL, o limite de empilhamento — ou “stack” — é de 100 funções. Logo, uma recursão não poderá ter mais de 99 niveis.

Agora, existem formas de se evitar a recursão. Normalmente é possível “planificar” o algoritmo, para não precisar usar recursão. Por exemplo, vou escrever uma segunda versão da função Fatorial, sem o uso de recursão:

STATIC Function Fatorial2( nNumero )
Local nRetorno := nNumero
Local nI
For nI := nNumero - 1 to 1 STEP -1
  nRetorno := nRetorno * nNumero 
Next
Return nRetorno

Usando a função acima, o número recebido como parâmetro é atribuído diretamente ao resultado, então o programa entra em um loop de processamento, contando a partir do numero anterior até 1, multiplicando o retorno pelo número da variável do loop, fazendo exatamente o cálculo fatorial, sem usar recursão. Ao eliminar a recursão, além de evitar o risco de estouro na pilha de chamada de funções da linguagem, economizamos vários ciclos de CPU gastos com a manutenção da pilha de chamadas de funções.

Exemplo 2 – Varrer uma árvore

Existem outros algoritmos que normalmente utilizam recursão, como por exemplo um algoritmo para varrer uma estrutura de árvore. Por exemplo, fazer uma soma de todos os arquivos a partir de um diretório e seus sub-diretórios. Em uma função recursiva, cada diretório encontrado em um nível chama a própria função informando o subdiretório encontrado, que por sua vez chamará a função novamente caso dentro deste diretório existam outros subdiretórios. Vamos ao exemplo:

User Function TesteDir()
MsgInfo( TamDir('\') , 'Tamanho do RootPath' )
Return
STATIC Function TamDir( cPath )
Local aFiles := Directory(cPath+'*.*')
Local aSubDir := Directory(cPath+'*.*','D')
Local nI
Local nSize := 0
// Acumula o tamanho dos arquivos desta pasta
For nI := 1 to len(aFiles)
  nSize += aFiles[nI][2]
Next
// Acumula o tamanho das pastas a partir desta, caso existam
// Ignora os diretorios "." ( atual ) e ".." ( anterior ) 
For nI := 1 to len(aSubDir)
  If aSubDir[nI][1] != "." .and. aSubDir[nI][1] != ".."
    nSize += TamDir( cPath + aSubDir[nI][1] + '\' )
  Endif
Next
Return nSize

Feito da forma acima, primeiro a função contabiliza o tamanho dos arquivos da pasta informada como parâmetro, para depois contabilizar o tamanho das sub-pastas, recursivamente. Agora, vamos escrever a mesma função sem recursão:

STATIC Function TamDir2( cPath )
Local aFiles := {}
Local aSubDir := {}
Local aVerify := {}
Local nI
Local nSize := 0
// Acrescenta a pasta atual como pendencia
aadd( aVerify , cPath )
While len(aVerify) > 0
 
  // Loop de processamento, enquanto houver subdiretorios
  // pendentes a serem verificados
 
  // Pega o path da ultima pendencia
  cPath := aTail(aVerify)
 
  // remove a ultima pendencia encolhendo o array
  aSize( aVerify , len(aVerify)-1 )
 
  // Identifica os arquivos da pasta
  aFiles := Directory(cPath+'*.*')
 
  // Acumula o tamanho dos arquivos desta pasta
  For nI := 1 to len(aFiles)
    nSize += aFiles[nI][2]
  Next
 
   // Verifica os sub-diretorios a partir desta pasta
   aSubDir := Directory(cPath+'*.*','D')
 
   // Acrescenta os sub-diretorios como pendencias
   For nI := 1 to len(aSubDir)
     If aSubDir[nI][1] != "." .and. aSubDir[nI][1] != ".."
       aAdd( aVerify , cPath + aSubDir[nI][1] + '\' )
     Endif
   Next
 
Enddo
Return nSize

Sem a recursão, criamos um array de pendências, onde cada pendência é um path a ser verificado e contabilizado. A primeira pendência é o próprio diretório recebido como parâmetro. O loop principal de processamento não é finalizado enquanto houverem pendências. A cada interação, a última pendência é removida. Os arquivos contidos no path em processamento é verificado, e caso dentro dele exista qualquer sub-diretório, estes serão acrescentados como novas pendências. Assim, conseguimos varrer toda a estrutura de diretórios e sub-diretórios sem usar recursão.

Finalizando

Na verdade, ao deixarmos de usar recursividade, passamos a trabalhar com um loop de iterações. Os problemas de cálculo fatorial e varrer todos os elementos de uma árvore são naturalmente recursivos, já que é necessário ser mantido registro de estados anteriores durante sua execução. Em ambas as abordagens, devemos tomar cuidado para evitar um cenário de loop infinito, principalmente na análise de elementos de uma árvore. Caso uma estrutura em árvore contenha um nó filho que aponte para um nó pai — situação conhecida como referência circular — tanto usando recursão como iteração, caso não exista uma proteção para evitar analisar um nó da árvore já processado, a aplicação é finalizada com uma ocorrência de estouro de pilha — stack — quando usada recursão, ou acaba entrando em loop infinito – quando utilizada iteração.

Imagine uma visão de estrutura organizacional de uma empresa, onde cadastramos todos os departamentos, e depois amarrações hierárquicas dentro de uma visão. Caso erradamente seja criada uma referência circular neste cadastro, e você chame uma rotina de processamento que varre a árvore de departamentos para registrar um acumulador por departamento seguindo esta árvore, se não houver uma proteção ou validação durante a execução ou no cadastro, fatalmente você terá problemas dessa natureza.

Até o próximo post, pessoal 😉

Referências

FATORIAL. In: WIKIPÉDIA, a enciclopédia livre. Flórida: Wikimedia Foundation, 2014. Disponível em: <http://pt.wikipedia.org/w/index.php?title=Fatorial&oldid=38597266>. Acesso em: 14 jan. 2015.

DIRECTORY, in TDN – Totvs Development Network. Disponível em: <http://tdn.totvs.com/display/tec/Directory>. Acesso em: 14 jan. 2015.

Recursividade, in DEI – Departamento Engenharia Informática. Disponível em: <http://academy.dei.uc.pt/page/programacao/progAvancado/recursividade>. Acesso em: 14 jan. 2015.

RECURSIVIDADE (CIÊNCIA DA COMPUTAÇÃO). In: WIKIPÉDIA, a enciclopédia livre. Flórida: Wikimedia Foundation, 2014. Disponível em: <http://pt.wikipedia.org/w/index.php?title=Recursividade_(ci%C3%AAncia_da_computa%C3%A7%C3%A3o)&oldid=38973260>. Acesso em: 14 jan. 2015.

Anúncios

2 comentários sobre “Funções recursivas em AdvPL

  1. E, aproveitando o embalo, uma atualização (ERRATA) : O Limite de empilhamento de funções ( Stack ) em AdvPL são 200 chamadas, e não 100 como foi mencionado no artigo.

    Curtir

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s