sexta-feira, 28 de agosto de 2009

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;
}
}

Nenhum comentário:

Postar um comentário