Funcoes Recursivas

[mauricioportela]

Recentemente, estava trabalhando com funcoes recursivas e me deparei com o custo de processamento da maquina. Utilizando uma determinada funcao recursiva, num "FOR" de 1 ate 40, tinha um tempo de processamento muito longo.

Pesquisando sobre o assunto, encontrei dois alguritmos que me ajudaram bastante em relacao ao custo computacional.

Compartilhando aqui.

Espero que ajude alguem.

Código: Selecionar todos

/**
    A implementacao recursiva padrao da funcao Fibonacci eh muito ineficiente 
    para valores grandes de n, pois pode levar a um grande numero de chamadas 
    recursivas de funcao e a um alto consumo de memoria. No entanto, existem 
    outras implementacoes da funcao Fibonacci que sao mais eficientes e podem 
    calcular os valores da sequencia de Fibonacci com muito menos recursos 
    computacionais.

    Algoritmo de matriz:
        Este algoritmo usa matrizes para calcular os valores de Fibonacci 
        em tempo constante. A ideia basica eh usar uma matriz de 2x2 para 
        representar o valor atual da sequencia de Fibonacci e o valor 
        anterior, e aplicar uma formula matematica para calcular o proximo 
        valor da sequencia. Esse algoritmo eh muito mais eficiente do que a 
        implementacao recursiva padrao, pois evita chamadas recursivas de 
        funcao e usa apenas um pequeno numero de operacoes matematicas para 
        calcular cada valor.

    Algoritmo de tempo constante:
        Este algoritmo calcula os valores de Fibonacci em tempo constante, 
        usando apenas algumas operacoes matematicas simples. A ideia basica 
        eh armazenar o valor atual da sequencia de Fibonacci e o valor 
        anterior em duas variaveis e, em seguida, atualizar as variaveis a 
        cada iteracao do loop para calcular o proximo valor da sequencia. 
        Esse algoritmo eh ainda mais eficiente do que o algoritmo de matriz, 
        pois usa apenas algumas operacoes matematicas simples para calcular 
        cada valor.

    Ambos os algoritmos sao muito mais eficientes do que a implementacao 
    recursiva padrao da funcao Fibonacci e podem calcular os valores da 
    sequencia de Fibonacci com muito menos recursos computacionais. Isso 
    torna esses algoritmos ideais para valores grandes de n, onde a 
    implementacao recursiva pode levar a um tempo de execucao muito longo 
    ou ate mesmo a um estouro de pilha.

**/


FUNCTION Main()
    LOCAL tInicio, tFinal, tProcesso, i, nResultado
    tInicio   := time()
    // ? "Hora inicial:", tInicio

    // *** Use esse FOR com a funcao padrao. Demora cerca de 1 a 2 minutos
    //
    // FOR i := 1 TO 40
    //     nResultado := fib(i)
    //     ? "fibonacci(" + ALLTRIM(STR(i)) + ") = " + ALLTRIM(STR(nResultado))
    // NEXT


    // *** Use esse for com 400 para testar os algoritmos de Matriz e Tempo
    FOR i := 1 TO 400
        nResultado := fib_matriz(i)
        // nResultado := fib_tempo(i)
        ? "fibonacci(" + ALLTRIM(STR(i)) + ") = " + ALLTRIM(STR(nResultado))
    NEXT

    tFinal    := time()
    tProcesso := ELAPTIME(tInicio, tFinal)

    ? "Hora inicial     :", tInicio
    ? "Hora final       :", tFinal
    ? "Tempo do Processo:", tProcesso
RETURN Nil


// Algoritmo Padrao
FUNCTION fib(n)
RETURN (IIF( n > 1, fib(n-1) + fib(n-2), n))


// Algoritmo de Matriz
FUNCTION fib_matriz(n)
    LOCAL aMatriz, aResultado
    IF (n <= 1)
        RETURN n
    ENDIF
    aMatriz := {{1, 1}, {1, 0}}
    aResultado := matriz_pow(aMatriz, n-1)
RETURN aResultado[1, 1]

FUNCTION matriz_mul(a, b)
    LOCAL c, i, j
    c := {{0, 0}, {0, 0}}
    FOR i := 1 TO 2
        FOR j := 1 TO 2
            c[i, j] := a[i, 1] * b[1, j] + a[i, 2] * b[2, j]
        NEXT
    NEXT
RETURN c

FUNCTION matriz_pow(a, n)
    LOCAL b
    IF (n == 1)
        RETURN a
    ELSEIF ((n % 2) == 0)
        b := matriz_pow(a, n/2)
        RETURN matriz_mul(b, b)
    ELSE
        b := matriz_pow(a, (n-1)/2)
        RETURN matriz_mul(matriz_mul(b, b), a)
    ENDIF



// Algoritmo de Tempo Constante
FUNCTION fib_tempo_const(n)
    LOCAL fib_antigo, fib_atual, fib_prox, i
    IF (n <= 1)
        RETURN n
    ENDIF
    fib_antigo := 0
    fib_atual  := 1
    FOR i := 2 TO n
        fib_prox := fib_atual + fib_antigo
        fib_antigo := fib_atual
        fib_atual := fib_prox
    NEXT
RETURN fib_atual

[JoséQuintas]

Função recursiva é ela chamando ela mesma, isso todo mundo sabe.

Isso vai criando uma pilha de chamadas
A função chama a si mesma esperando resultado, que chama a si mesma, esperando resultado, .....
Existe um limite pra isso.
No DOS era "call stack" e poderia ser configurado no CONFIG.SYS
No windows o limite é maior, mas limite existe.

Com FOR/NEXT, ou outra coisa, esse negócio de deixar funções em aberto desaparece.

NÃO QUE SEJA PROBLEMA RECURSIVIDADE.

Mas deixar como uso infinito... com certeza vai estourar a capacidade de tudo.

Lembro que tive problema ao usar SIXCDX no Clipper, por estourar essa "call stack".
No blinker adicionei isto, na época:

Código: Selecionar todos

   ? "blinker PROCEDURE depth 120"
   ? "blinker executable alignment 128"

Então... recursividade é normal, só não pode abusar e criar situações que podem ser infinitas.

[mauricioportela]

Boa noite!

Recursividade - é a funcao chamando ela mesma. Mas, não é pra ficar em loops eternos. No caso desse código que postei, foi só pra mostra o processo. A execução da função recursiva normal com somente 40 giros e comparar com as funções dos algoritmos mencionados ( Matriz e Tempo ) com 400 (quatrocentos) giros!! Veja o tempo que é gasto com os 40 giros e compare com o tempo dos outros.

[JoséQuintas]

Nesse caso não tem a ver com recursividade, mas com o melhor algorítmo a ser usado.
Se o cálculo parte do menor, e depende da sequência do menor pro maior, recursividade é errado, pelo menos dessa forma.

[JoséQuintas]

Se perguntar no bing (com IA) ele mostra exatamente a função recursiva que postou.

Achei a brincadeira interessante....
Peguei a rotina normal no bing, e criei esta recursiva, partindo do menor.
Usei a original do bing pra conferir cálculo.
É meio doida mas funcionou.
Nem comparei velocidade, é instantâneo.

Código: Selecionar todos

PROCEDURE Main

   LOCAL nCont

   SetMode(25,80)
   CLS
   Altd()
   FOR nCont = 1 TO 40
      ? Fibonacci( nCont ), Fibonaccir( nCont )
   NEXT
   Inkey(0)

   RETURN

FUNCTION Fibonaccir( n, a, b, n2 )

   LOCAL c

   IF a == Nil
      RETURN fibonacci( n, 0, 1, 0 )
   ENDIF
   IF n2 == n
      RETURN a + b
   ENDIF
   c := a + b
   a := b
   b := c
   n2 += 1

   RETURN fibonacci( n, a, b, n2 )

FUNCTION fibonacci( n )

   LOCAL a := 0
   LOCAL b := 1
   LOCAL c := 0
   LOCAL i

   FOR i := 1 TO n
      c := a + b
      a := b
      b := c
   NEXT i
   (c)

   RETURN a

[JoséQuintas]

Com tempo: as duas rodando juntas 100 voltas, deu.... 0 segundos kkkkk

[JoséQuintas]

Aqui o objetivo foi conferir, e não medir tempo.
As 4 rotinas juntas.

Código: Selecionar todos

PROCEDURE Main

   LOCAL nCont, tInicio, tFinal

   SetMode(25,80)
   CLS
   Altd()
   tInicio := Time()
   FOR nCont = 1 TO 35
      ? nCont, Fibonacci( nCont ), Fibonaccir( nCont ), fib( nCont ), fib_matriz( nCont )
   NEXT
   tFinal := Time()
   ? "inicio " + tInicio
   ? "final  " + tFinal
   ? "tempo  " + ElapTime( tInicio, tFinal )
   Inkey(0)

   RETURN

FUNCTION Fibonaccir( n, a, b, n2 )

   LOCAL c

   IF a == Nil
      RETURN fibonacci( n, 0, 1, 0 )
   ENDIF
   IF n2 == n
      RETURN a + b
   ENDIF
   c := a + b
   a := b
   b := c
   n2 += 1

   RETURN fibonacci( n, a, b, n2 )

FUNCTION fibonacci( n )

   LOCAL a := 0
   LOCAL b := 1
   LOCAL c := 0
   LOCAL i

   FOR i := 1 TO n
      c := a + b
      a := b
      b := c
   NEXT i
   (c)

   RETURN a


// Algoritmo Padrao
FUNCTION fib(n)
RETURN (IIF( n > 1, fib(n-1) + fib(n-2), n))

// Algoritmo de Matriz
FUNCTION fib_matriz(n)
    LOCAL aMatriz, aResultado
    IF (n <= 1)
        RETURN n
    ENDIF
    aMatriz := {{1, 1}, {1, 0}}
    aResultado := matriz_pow(aMatriz, n-1)
RETURN aResultado[1, 1]

FUNCTION matriz_mul(a, b)
    LOCAL c, i, j
    c := {{0, 0}, {0, 0}}
    FOR i := 1 TO 2
        FOR j := 1 TO 2
            c[i, j] := a[i, 1] * b[1, j] + a[i, 2] * b[2, j]
        NEXT
    NEXT
RETURN c

FUNCTION matriz_pow(a, n)
    LOCAL b
    IF (n == 1)
        RETURN a
    ELSEIF ((n % 2) == 0)
        b := matriz_pow(a, n/2)
        RETURN matriz_mul(b, b)
    ELSE
        b := matriz_pow(a, (n-1)/2)
        RETURN matriz_mul(matriz_mul(b, b), a)
    ENDIF
    RETURN 0

// Algoritmo de Tempo Constante
FUNCTION fib_tempo_const(n)
    LOCAL fib_antigo, fib_atual, fib_prox, i
    IF (n <= 1)
        RETURN n
    ENDIF
    fib_antigo := 0
    fib_atual  := 1
    FOR i := 2 TO n
        fib_prox := fib_atual + fib_antigo
        fib_antigo := fib_atual
        fib_atual := fib_prox
    NEXT
RETURN fib_atual

Conclusão:
Não tem a ver com recursividade, e sim com o algorítmo usado.
Algorítmo ruim acaba com tudo, com ou sem recursividade.

[JoséQuintas]

Só comentário:

Lembro de ver comparações entre Visual Basic e Delphi....

No Delphi usavam campo inteiro, o mais rápido de todos.
No Visual Basic usavam campo variant, o pior de todos.
Aí o Delphi sempre mostrava o melhor tempo.

No Visual Basic também tem tipo inteiro.
Tipo variant é pra qualquer tipo, ainda devia ter tempo de conversão no meio.

Comparar coisas com referência diferente não dá.
Provavelmente quem usava Delphi não conhecia VB, e fez do jeito que pensava ser igual.

No caso atual, apenas analisei o jeito de calcular, que era do menor pro maior.
Não faz sentido usar recursividade pra isso, mas... funciona.

E até que minha cabeça ainda funciona kkkk