Funções Recursivas e Funções Iterativas

Em programação de softwares de computadores existem dois procedimentos que permitem que um código seja executado repetidamente, um é a função recursiva, onde em um dos passos do procedimento a função invoca-se à si própria, e o outro é a função iterativa, onde ocorre a repetição de um ou mais passos controlados por um laço de repetição.

Os dois procedimentos tem suas vantagens e desvantagens, que envolvem o consumo de memória, de processamento, tamanho e clareza do código etc. Não vou entrar aqui em detalhes quanto à análise da eficiência dos algoritmos, apenas quero apresentar as diferenças estruturais destes dois procedimentos.

Em ambos os casos, por serem procedimentos que realizam uma repetição de passos, é necessário que se tenha uma condição de parada, senão a repetição corre o risco de ser infinita.

A função iterativa utiliza comandos chamados laços de repetição para o controle do fluxo de execução, como o comando for ou while por exemplo, que dependem de uma condição ser verdadeira ou falsa para iniciar ou interromper a repetição.

A função recursiva realiza a repetição dos seus passos invocando à si própria, executando todos os seus passos novamente em uma chamada completamente independente da mesma função. Nesta segunda chamada a função pode invocar-se novamente e assim várias vezes até que uma estrutura de controle encerre esta ação, e então cada retorno é recebido pelas funções anteriores de forma cumulativa.

Segue abaixo versões iterativas e recursivas das soluções de alguns problemas mais conhecidos:

Fatorial de um número, versão iterativa, em VBA:

Public Function FATO(numero As Integer) As Integer

Dim fatorial As Integer
fatorial = 1
For i = 1 To numero
    fatorial = fatorial * i
Next
FATO = fatorial

End Function

Fatorial de um número, versão recursiva, em VBA:

Public Function FATO(numero As Integer) As Integer

If numero <= 1 Then
    FATO = 1
Else
    FATO = numero * FATO(numero - 1)
End If

End Function

Número de Fibonacci, versão iterativa, em VBA:

Public Function FIBONACCI(posicao As Integer) As Long

Dim anterior, atual, proximo As Long
Dim contador As Integer

If posicao = 1 Or posicao = 2 Then
    FIBONACCI = 1
ElseIf posicao >= 3 Then
    anterior = 1
    atual = 1
    For contador = 3 To posicao
        proximo = anterior + atual
        anterior = atual
        atual = proximo
    Next
    FIBONACCI = atual
Else
    FIBONACCI = 0
End If

End Function

Número de Fibonacci, versão recursiva, em VBA:

Public Function FIBONACCI(posicao As Integer) As Long

If posicao >= 3 Then
    FIBONACCI = FIBONACCI(posicao - 1) + FIBONACCI(posicao - 2)
Else
    FIBONACCI = 1
End If

End Function

Pesquisa binária, versão iterativa, em Java:

public static int pesqbinite(int[] vetor, int valor) {

int esq = 0;
int dir = vetor.length - 1;
int meio;

while ( esq <= dir ) {
     meio = (esq + dir) / 2;
     if ( vetor[meio] < valor ) {
          esq = meio + 1;
     } else if( vetor[meio] > valor ) {
          dir = meio - 1;
     } else {
          return meio;
     }
}
return -1;
}

Pesquisa binária, versão recursiva, em Java:

public static int pesqbinrec(int[] vetor, int pi, int pf, int valor){

int meio = ((pf - pi) / 2) + pi;

if (vetor[meio] == valor) {
     return meio;
} else if ((vetor[meio] < valor) && (valor <= vetor[pf])) {
     pi = meio + 1;
     return pesqbinrec(vetor,pi,pf,valor);
} else if ((vetor[meio] > valor) && (valor >= vetor[pi])) {
     pf = meio;
     return pesqbinrec(vetor,pi,pf,valor);
} else {
     return -1;
}
}