VBA Excel - Introdução à recursividade

Setembro 2017

Esta é uma apresentação da recursividade por funções simples, uma introdução através de alguns exemplos. Uma função (ou procedimento) é chamada recursiva quando chama a si mesma. Ela precisa de uma porta de saída, comumente chamada de Ponto de parada. Ela consiste em uma instrução indicando que o restante do procedimento não deve ser executado. Consciente de que essa teoria é relativamente complexa, passemos logo ao primeiro exemplo.


Fatorial

Análise

Em matemática, o fatorial de um número natural n, representado por n!, é o produto de todo os números inteiros positivos inferiores ou iguais a n (Fonte Wikipédia). Isso se traduz por n! = n x (n-1) x (n-2) x (n-3) x... x 1. Pode-se igualmente adotar outra equação matemática para esta escrita fatorial n, sendo o n multiplicado pelo fator de n -1: n! N = x (n-1)! Vemos nesta equação, desenhar-se nossa recursividade
Fatorial (n) = n * fatorial (n-1)
. Podemos ver aqui uma função que se chama a ela mesma.

Qual seria a porta de saída, o ponto de ruptura? Na definição de fatorial, nós encontramos o produto dos números inteiros estritamente positivo. Ou seja, um ponto de ruptura quando o nosso n? = 1.

O código

Observação: Nb > número e Nb > número.

Função Fatorial 
'O If existe para o ponto de ruptura, para não executar o resto do  procedimento 
If Nb = 1 Then '===> Ponto de ruptura:  chegamos a 1
     Fatorial = 1 
else 
     Fatorial = Nb * fatorial(Nb - 1) 
===> Equação: fatorial(n) = n * 
fatorial(n-1) 
End If 
End Function

Máximo divisor comum

Algoritmo de Euclides

Em matemática, para determinar o Máximo Divisor Comum (MDC) de dois números (a e b), precisamos fazer a divisão de a por b (onde encontramos um resto r1) e depois a divisão de b por r1 (o resto encontrado é r2), em seguida, aquela de r1 por r2 ... e assim por diante. A definição da divisão Euclidiana assegura que os resultados r1, r2 ... sejam estritamente decrescentes e acabarão por anular-se. O MDC de a e b é o último resto não nulo desta sequência (Algoritmo de Euclides).

Em informática, precisamos, portanto, de uma função pela qual vamos passar dois parâmetros (nossos dois números iniciais). Esta função vai calcular o resto da divisão destes dois números e se chamar ela mesma, usando o restante dessa divisão como o segundo parâmetro. O ponto de ruptura desta função é, evidentemente, quando o resto da divisão será nulo.

O código

 Função MDC_Recursivo(Nb1 As Long, Nb2 As Long)
As Long, Nb2 As Long)
Dim Reste As Long
Resto = Nb1 Mod Nb2 ' ===> Divisão e cálculo do resto  
If Resto = 0 Then ' ===> Ponto de ruptura
    MDC_Recursivo = Nb2 ' ===> Nb2 é o último resto não nulo 
Else
    MDC_Recursivo = MDC_Recursivo(Nb2, Reste) ' ===> Chamada recursiva
End If
End Function

O código de chamada

Na definição, também é dito que o cálculo do MDC de dois números, Nb1 e Nb, 2 requer:

Nb1> Nb2
NB1 e Nb2 diferentes de 0

Para fazer isso, basta adicionar dois pequenos testes na função de chamada. O primeiro vai intervir nos dois números se Nb2 > NB1, no segundo vai resolver um dos dois (ou ambos) números nulos.

 Sub Appel_MDC() 
Dim Nb1 As Long, Nb2 As Long, NbTemp As Long
'caso um dos dois números for igual a zero  
If Nb1 = 0 Then MsgBox "O MDC é igual a " & Nb2: Exit Sub
If Nb2 = 0 Then MsgBox "O MDC é igual a " & Nb2: Exit Sub
'Nb1 deve ser superior a Nb2
If Nb1 < Nb2 Then
    NbTemp = Nb1
    Nb1 = Nb2
    Nb2 = NbTemp
End If
MsgBox MDC_Recursivo(Número1, Número2) 'Lançamento Função MDC_Recursivo
End Sub

Conversão algarismos romanos

Análise

A numeração dos algarismos romanos foi padronizada no uso atual e é baseada em quatro princípios (Fonte):

Qualquer letra colocada à direita de outra figurando um valor superior ou igual a sua se adiciona à ela. Qualquer letra de unidade colocada imediatamente à esquerda de uma letra mais forte do que ela, indica que o número que lhe corresponde deve ser subtraído do número que segue. Os valores são agrupados em ordem decrescente, exceto os valores a serem subtraídos de acordo com a regra anterior. A mesma letra não pode ser usada quatro vezes consecutivas, exceto o M.

Aqui, nós não vamos nos preocupar em verificar o número romano em si mesmo, logo, os dois últimos princípios não nos interessam. Nós vamos converter um número romano em algarismo arábico, sem nos preocuparmos se a escrita de um número romano está certa ou não. Nós temos, então, duas regras a serem verificadas, ou seja, o valor do primeiro dígito é maior do que o número que segue. Neste caso, o resto é adicionado ao valor da figura. O valor do primeiro número é menor que o número que segue. Neste caso, o restante é convertido e subtraído do valor do primeiro dígito.

Aqui, a recursividade se baseia na conversão do resto. O ponto de ruptura da nossa função é o comprimento da cadeia composta pelos algarismos romanos. A conversão do último caractere (que corresponde à conversão do resto) será, de fato, a conversão de uma cadeia de comprimento igual a 1. Precisaremos de duas funções, uma recursiva para a conversão sucessiva dos valores e o cálculo, e uma para avaliar cada uma das letras do algarismo romano.

O código

Não vamos nos focar na conversão de letras em algarismos arábicos. Isso não acrescentará nada à nossa dica.

Função de conversão de cada uma das letras

Função Conv(letra As Cadeia) As Long 
Dim Romanos(), Arábicos(), Pos As Integer

Romanos = Array("M", "D", "C", "L", "X", "V", "I")
Arábicos = Array(1000, 500, 100, 50, 10, 5, 1)
Pos = -1
On Error Resume Next
Pos = Application.Match(letra, Romano, 0) - 1
On Error GoTo 0
If Pos <> -1 Then Conv = Arábicos(Pos)
End Function

Sun(Romanos), Arábicos() As Integer Pos

Rm = Array("H", "D", "C", "L", "X", "V", "I")
Arábicos = Array(1000, 500, 100, 50, 10, 5, 1)
Pos = -1
On Error Resume Next
Pos = Application.Match(letra, Romanos, 0) - 1
On Error GoTo 0
Se Pos <> -1 Then Conv = Arábicos(POS)
End Function</code>

Função recursiva

... de conversão da cadeia de algarismos romanos:
Nesta função, precisamos trabalhar em uma cadeia de caracteres correspondente ao algarismo Romano. Vamos precisar converter letra por letra desta cadeia. Para isso, usamos a função Mid (veja este artigo). Também vamos precisar extrair desta cadeia o resto, ou seja, uma subcadeia iniciando no enésimo caractere da cadeia original e de comprimento (comprimento original - n). Mid também nos permite isso.

Function Convertido(strRomano As String) 
Dim i As Long, strLetra As String, Valor As Integer

If Len(strRomano) = 1 Then ' ===> Ponto de ruptura: o comprimento da  cadeia tratada (resto) = 1
    Convertido= Conv(strRomano)
Else
    Valor = Conv(Mid(strRomano, 1, 1)) '===> Chamada da função de conversão do número 
     ' Teste de comparação com o algarismo romano seguinte 
     ' para sempre adicionar, basta multiplicar por -1 no caso do número seguinte ser  superior 
     If Valor < Conv(Mid(strRomain, 2, 1)) Then Valor = Valor * (-1) 
     ' Recursividade com a cadeia de comprimento reduzida em 1 
     Convertido = Valor + Convertido(Mid(strRomano, 2, Len(strRomano) - 1)) 
End If 
End Função

Combinações de uma cadeia de caracteres

Análise

Suponhamos uma cadeia de três caracteres “aze" a qual queremos, em troca, todas as combinações possíveis. A lista de combinações é obtida pela permutação de cada caractere. A primeira permutação com a cadeia abc seria o primeiro caractere indo para o final da cadeia: bca, e o segundo, para final da cadeia: bac. A segunda permutação com cadeia bca, seria o primeiro caractere indo para o final da cadeia: cab, e o segundo, para o final da cadeia: cba. A primeira permutação com a cadeia de cab seria o primeiro caractere indo para o final da cadeia: abc, e o segundo, para o final da cadeia: acb.

Desta maneira, nós obtivemos nossas seis combinações, ou seja, bca, bac, cab, cba, abc, acb

O código

As variáveis públicas permitem armazenar diferentes combinações, progressivamente:
 'à declarar  no cabeçalho do seu módulo 
Dim Tb(), IndTab As Long


O procedimento da chamada:
Sub Chamada_Combinações()
‘O procedimento Combinar precisa de dois parâmetros:
‘A cadeia: strText
‘A subcadeia que permite a permutação: início
‘Esta, no momento da chamada está vazia, é claro 
Combinar "AZE", ""
End Sub


O procedimento recursivo que sempre efetua as permutações graças à função Mid.
Sub Combinar(strText As String, início As String) 
Dim i As Integer 

If Len(strText) = 1 Then 'Quando o comprimento do strText for igual a 1
     ‘Armazenamos a cadeia composta de: início e str text 
     ReDim Preserve Tb(IndTab) 
     Tb(IndTab) = início e strText 
     = 1 + IndTab IndTab 
Else 
     For i = 1 To Len(strText) 
         "Enviamos o primeiro caractere da subcadeia strText para o final
         Combinar Mid(strText, 2, Len (strText) - 1) início & Mid(strText, 1, 1) 
         "Trabalhar na cadeia de caracteres 
           strText = Mid(strText, 2, Len(strText) - 1) & Mid(strText, 1, 1)
    Next
End If
End Sub


Observação:. Para melhorar a compreensão deste código, eu os convido a inicia-lo em modo de passo a passo F8 a partir do Editor VBA.

Pesquisa em uma variável de tabela

Análise

Este exercício é uma tradução, em VBA, do algoritmo da Dicotomia encontrada aqui (em francês - veja o capítulo: Algoritmo de pesquisa para dicotomia).

Resumindo, o procedimento deve comparar o valor desejado com o aquele situado no meio da variável de tabela. Se o valor desejado for maior do que aquele do meio > vamos procurar na metade superior da tabela (recursividade). Se ele for inferior ao do meio > vamos procurar na metade inferior da tabela (recursividade). Se eles forem iguais >
voltar ao índice (no meio, neste caso). Se a ponta inferior >= a ponta superior, o valor não existe. Estes dois pontos são os pontos de ruptura.

O código

O código de chamada da função

 Sub Chamada() 
Dim Tb_In(10) As Integer, Ind As Integer, k As Integer

' Preenchimento da nossa tabela 
For k = 1 To 31 Step 3
    Tb_In(Ind) = k
    Ind = Ind + 1
Next k
MsgBox Está_Situada_Na_Tabela_A_O_índice(Tb_In(), 19, LBound(Tb_In), UBound(Tb_In))End Sub

A função recursiva

Os parâmetros obrigatórios são:
A variável da tabela contendo todos os dados: procedimento de chamada: Tb_In(), Função: Tbl().
O valor desejado: procedimento de chamada: 19, função: i
A ponta inferior: procedimento de chamada: LBound(Tb_In), Função: mini
A ponta superior: procedimento de chamada: UBound(Tb_In) Função: maxi.

Function Está_Situado_Na_Tabela_A_0_índice(Tbl() As Integer, i As Integer, mini As Integer, maxi As Integer) As Integer
Dim Meio As Integer
Meio = (mini + maxi) / 2
If Tbl(Meio) = i Then ' Encontramos o número i desejado
    Está_Situado_Na_Tabela_A_O_índice = Meio
ElseIf mini >= maxi Then ' Não foi encontrado i e onde não se pode mais continuar
    E_Situado_Na_Tabela_A_índice = 0
ElseIf Tbl(Meio) > i Then 'Podemos continuar com uma subtabela 
    ' o número desejado é inferior  ao valor situado no  “meio de 2 pontas da tabela”
    Está_Situado_Na_Tabela_A_O_índice = Está_Situado_Na_Tabela_A_0_índice(Tbl(), i, mini, Meio - 1)
Else
    ' o número desejado é superior ao valor situado no  “meio das 2 pontas da tabela”
    Está_Situado_Na_Tabela_A_O_índice = Está_Situado_Na_Tabela_A_O_índice(Tbl(), i, Meio + 1, maxi)
End If
End Função

Conclusão

Nada foi inventado aqui. Partimos de algoritmos simples, que podem ser encontrados na Internet e transcrevemos em pequenas funções recursivas em VBA.

Foto: © Microsoft.com

Veja também

Artigo original publicado por pijaku. Tradução feita por ninha25. Última modificação: 3 de novembro de 2016 às 12:34 por pintuda.
Este documento, intitulado 'VBA Excel - Introdução à recursividade ', está disponível sob a licença Creative Commons. Você pode copiar e/ou modificar o conteúdo desta página com base nas condições estipuladas pela licença. Não se esqueça de creditar o CCM (br.ccm.net) ao utilizar este artigo.