Use fórmulas fechadas para evitar estouro de pilha e obter eficiência

02/02/2025

O problema do estouro de pilha em algoritmos recursivos, explicamos suas causas e apresentamos soluções eficientes usando fórmulas fechadas. Id: 54

Capa do artigo Use fórmulas fechadas para evitar estouro de pilha e obter eficiência

Estouro de Pilha em Algoritmos Recursivos

O estouro de pilha ocorre quando um algoritmo recursivo faz tantas chamadas aninhadas que excede o limite da pilha de execução. Isso geralmente acontece porque a recursão consome memória a cada nova chamada antes de retornar um resultado.

Soluções para o Estouro de Pilha

  • Utilizar memoization para evitar chamadas redundantes.
  • Converter a recursão em iteração para reduzir o uso de memória.
  • Utilizar uma fórmula fechada quando possível, eliminando a recursão.

É sobre essa última solução que enfatizaremos este artigo.

Resolver uma recorrência é encontrar uma fórmula fechada que dê o valor da função diretamente em termos de seu argumento (n). A grande vantagem desse método é que, além de evitar o estouro de pilha, reduz a complexidade do código para constante, ou seja, O(1) na notação Big O, uma vez que as respostas se tornam diretas, independentes de um loop ou recursão para a obtenção de resultados anteriores.

Exemplos de otimização com redução a fórmulas fechadas

1. Soma dos Números

Versão recursiva:

def soma_numeros(n):
    if n == 0:
        return 0
    else:
        return n + soma_numeros(n - 1)

Versão otimizada (fórmula fechada):

def soma_numeros_formula_fechada(n):
   return (n*(n + 1)/2)

Versão recursiva (código completo para verificação do tempo):

import sys
import time


def soma_numeros(n):
    if n == 0:
        return 0
    else:
        return n + soma_numeros(n - 1)


# Marca o início do tempo
start_time = time.time()


# Pega o valor de n a partir da linha de comando
if len(sys.argv) > 1:
    n = int(sys.argv[1])
else:
    print("Por favor, forneça um valor para n.")
    sys.exit(1)


print("Algoritmo recursivo (versão ineficiente):")


resultado=soma_numeros(n)


# Marca o fim do tempo
end_time = time.time()


# Calcula o tempo de execução
execution_time = end_time - start_time


print(str(n),"->", resultado)


print(f"Tempo de execução: {execution_time:.6f} segundos")

Versão otimizada (código completo da fórmula fechada para verificação do tempo de execução):

import sys
import time


def soma_numeros_formula_fechada(n):
   return (n*(n + 1)/2)


#n=4
# Pega o valor de n a partir da linha de comando
if len(sys.argv) > 1:
    n = int(sys.argv[1])
else:
    print("Por favor, forneça um valor para n.")
    sys.exit(1)


# Marca o início do tempo
start_time = time.time()


print("Versão eficiente, de complexidade O(1):")


resultado=soma_numeros_formula_fechada(n)


print(f"Solução com formula fechada: {n} -> ", resultado)


end_time=time.time()


# Calcula o tempo de execução
execution_time = end_time - start_time


print(f"Tempo de execução: {execution_time:.6f} segundos")

2. Fibonacci

Versão recursiva:

def fibonacci_recursivo(n):
    if n <= 1:
        return n
    else:
        return fibonacci_recursivo(n - 1) + fibonacci_recursivo(n - 2)

Versão otimizada (fórmula fechada):

def fibonacci_form_fechada(n):
    phi = (1 + sqrt(5)) / 2
    psi = (1 - sqrt(5)) / 2
    return round((phi**n - psi**n) / sqrt(5))

Versão recursiva (código completo para verificação do tempo):

import sys
import time


def fibonacci_recursivo(n):
    if n <= 1:
        return n
    else:
        return fibonacci_recursivo(n - 1) + fibonacci_recursivo(n - 2)


#n=3
# Pega o valor de n a partir da linha de comando
if len(sys.argv) > 1:
    n = int(sys.argv[1])
else:
    print("Por favor, forneça um valor para n.")
    sys.exit(1)


print("Algoritmo Fibonacci recursivo (versão ineficiente):")


# Marca o início do tempo
start_time = time.time()


resultado=fibonacci_recursivo(n)


print(str(n),"->", resultado)


end_time=time.time()


# Calcula o tempo de execução
execution_time = end_time - start_time


print(f"Tempo de execução: {execution_time:.6f} segundos")

Versão otimizada (código completo da fórmula fechada para verificação do tempo de execução):

import sys
from math import sqrt
import time


def fibonacci_form_fechada(n):
    phi = (1 + sqrt(5)) / 2
    psi = (1 - sqrt(5)) / 2
    return round((phi**n - psi**n) / sqrt(5))


# Pega o valor de n a partir da linha de comando
if len(sys.argv) > 1:
    n = int(sys.argv[1])
else:
    print("Por favor, forneça um valor para n.")
    sys.exit(1)


print("Algoritmo Fibonacci com fórmula fechada (versão eficiente):")


start_time=time.time()


resultado=fibonacci_form_fechada(n)


print(str(n),"->", resultado)


end_time=time.time()


# Calcula o tempo de execução
execution_time = end_time - start_time


print(f"Tempo de execução: {execution_time:.6f} segundos")

3. Soma das Potências de 2

Versão recursiva:

def soma_potencias_recursiva(n):
    if n == 0:
        return 1  # 2^0 = 1
    else:
        return (2 ** n) + soma_potencias_recursiva(n - 1)

Versão otimizada (fórmula fechada):

def soma_potencias_fechada(n):
    return (2 ** (n + 1)) - 1

Versão recursiva (código completo para verificação do tempo):

import sys
import time


def soma_potencias_recursiva(n):
    if n == 0:
        return 1  # 2^0 = 1
    else:
        return (2 ** n) + soma_potencias_recursiva(n - 1)


# Marca o início do tempo
start_time = time.time()


# Pega o valor de n a partir da linha de comando
if len(sys.argv) > 1:
    n = int(sys.argv[1])
else:
    print("Por favor, forneça um valor para n.")
    sys.exit(1)


print("Algoritmo recursivo (versão ineficiente):")


resultado = soma_potencias_recursiva(n)


# Marca o fim do tempo
end_time = time.time()


# Calcula o tempo de execução
execution_time = end_time - start_time


print(str(n), "->", resultado)
print(f"Tempo de execução: {execution_time:.6f} segundos")

Versão otimizada (código completo da fórmula fechada para verificação do tempo de execução):

import sys #Para manipulação do parâmetro de entrada n
import time #Para verificação do tempo de execução


# Função otimizada (usa a fórmula fechada):
def soma_potencias_fechada(n):
    return (2 ** (n + 1)) - 1


# Marca o início do tempo
start_time = time.time()


# Pega o valor de n a partir da linha de comando
if len(sys.argv) > 1:
    n = int(sys.argv[1])
else:
    print("Por favor, forneça um valor para n.")
    sys.exit(1)


print("Algoritmo otimizado (fórmula fechada):")


resultado = soma_potencias_fechada(n)


# Marca o fim do tempo
end_time = time.time()


# Calcula o tempo de execução
execution_time = end_time - start_time


print(str(n), "->", resultado)
print(f"Tempo de execução: {execution_time:.6f} segundos")

Esses exemplos mostram como podemos evitar o estouro de pilha ao substituir recursões por soluções matemáticas eficientes.

Veja o vídeo sobre esta postagem no Youtube:

https://www.youtube.com/watch?v=rXQ6xxDd6uY

Para comentários:

Se quiser comentar, sugerir (acréscimos, retificações etc), criticar, elogiar, informar, sobre algum trecho deste artigo, peço a gentileza de utilizar a área de comentários do abaixo informada, no Youtube.

Já existe uma mensagem por lá dedicada a comentários sobre temas publicados neste portal.

Essa também é uma forma de contribuir com o trabalho e estimular sua continuidade e aprimoramento.

Peço a gentileza de comentar, curtir e compartilhar o conteúdo, além de se inscrever no canal do Youtube e ativar o sino de notificações para receber notícias de novos conteúdos.

Agradeço desde já!

Destinado para esses comentários em geral:

https://www.youtube.com/@roberto_csantos/community