O que é programação recursiva e como funciona? A matemática por trás da tecnologia

O que é recursão em programação ou desenvolvimento de software?

Se você já viu uma boneca russa, já experimentou um exemplo visual de recursão: um objeto contendo versões menores de si mesmo. Na programação, a recursão é uma técnica poderosa que permite que uma função chame a si mesma para resolver problemas complexos de maneira simples.

A programação recursiva é uma técnica algorítmica de engenharia de software para resolução de problemas. Esta técnica foi projetada para resolver problemas em que a ordem de complexidade depende do tamanho do problema . Está especialmente orientado para o desenvolvimento de funções em que os tempos de computação são elevados.

Exemplos:

• Procure um elemento em uma lista. Usar a recursão para procurar linearmente um elemento em uma lista não é eficiente e ocupa mais espaço de memória. Uma pesquisa iterativa com loop é muito mais direta e rápida.
• Cálculo do fatorial de um número. Este problema, por sua própria definição matemática, possui uma definição matemática recursiva natural, portanto sua implementação recursiva é direta e muito mais eficiente.

A programação recursiva é baseada em uma técnica na qual uma função chama a si mesma para resolver um problema. Em vez de resolver o problema inteiro de uma vez, a função divide o problema em subproblemas menores e trata cada um deles recursivamente. Este processo continua até que um caso base ou condição de terminação seja alcançado, o que interrompe as chamadas recursivas e evita que elas se repitam indefinidamente.

Em cada chamada recursiva, a função funciona numa versão simplificada ou reduzida do problema original. Ao resolver este subproblema menor, o programa acumula soluções parciais que, no final, são combinadas para resolver o problema como um todo. Dessa forma, a recursão permite que problemas complexos sejam decompostos em etapas mais simples, que a função pode resolver passo a passo automaticamente.

É importante que cada algoritmo recursivo defina claramente sua condição base, pois sem ela a função continuaria chamando a si mesma indefinidamente, o que causaria um erro de stack overflow. Portanto, a recursão é uma técnica muito poderosa, mas requer cuidados na sua implementação para ser eficiente.

Programação recursiva VS programação iterativa

• Na programação recursiva, uma função chama a si mesma, direta ou indiretamente, para resolver um problema. Um problema é decomposto em subproblemas menores, resolvendo cada um deles até que um caso base seja alcançado.

• Na programação iterativa, estruturas de controle como loops (for, while) são usadas para repetir uma sequência de instruções um número definido de vezes ou até que uma condição seja atendida.

A utilização de técnicas de programação iterativa ou recursiva dependerá da natureza e complexidade do problema e, sobretudo, do tempo necessário para resolvê-lo, ou seja, da sua ordem de complexidade.

Em geral, a programação iterativa é mais intuitiva e fácil de executar, é aquela que normalmente é utilizada por padrão e com a qual os programadores costumam ter mais afinidade.

Como regra quase geral, a programação recursiva é usada quando o tempo de execução cresce exponencialmente com o tamanho do problema, em vez de linearmente, já que para um problema muito grande a função pode demorar muito para terminar ou ir até o infinito. Também é utilizado quando o tempo de execução para resolver um problema recursivamente é muito menor que a versão iterativa ou quando seu consumo de recursos, como RAM, é menor.

Como vimos até agora, a recursão é uma ferramenta poderosa para resolver problemas complexos, porém, em alguns casos, pode levar a tempos de execução exponenciais se não for utilizada de forma eficiente. O uso de técnicas como memoização pode otimizar a recursão para evitar comportamento desnecessariamente lento.

A ordem da complexidade

O conceito de ordem de complexidade é uma medida que descreve o comportamento do tempo ou espaço que um algoritmo precisa para executar dependendo do tamanho de sua entrada. É utilizado para analisar e comparar a eficiência de diferentes algoritmos, o que é essencial quando se trata de problemas que envolvem grandes quantidades de dados. Existem 2 tipos de complexidade, temporal e espacial.

• Complexidade de tempo: refere-se ao tempo que um algoritmo leva para ser executado conforme o tamanho do problema aumenta.
• Complexidade de espaço: refere-se à quantidade de memória que um algoritmo requer à medida que o tamanho do problema aumenta.

Para expressar a complexidade, utiliza-se a notação Big O (O(n)), que fornece uma forma de representar o comportamento assintótico de um algoritmo, ou seja, como ele se comporta quando o tamanho do problema tende a ser grande. A notação Big O descreve o pior cenário para o tempo ou espaço exigido por um algoritmo, dada uma entrada de tamanho n.

Exemplos de ordens de complexidade comuns

Ordenado da maior para a menor eficiência:

O(1) - Tempo constante

• O tempo de execução não depende do tamanho da entrada.
• Exemplo: Acesse um elemento em uma lista ou array pelo seu índice.
• Não importa se a lista tem 10 ou 1 milhão de itens, o acesso é imediato.

O(log n) - Tempo logarítmico:

• O tempo de execução aumenta logaritmicamente à medida que o tamanho da entrada aumenta. Esse tipo de complexidade é típico de algoritmos que dividem o problema em metades a cada etapa.
• Exemplo: pesquisa binária.
• Aqui, a cada passo, reduzimos pela metade o tamanho da lista, de modo que o número de operações cresce logaritmicamente em relação ao tamanho da lista.

O(n) - Tempo linear:

• O tempo de execução aumenta proporcionalmente ao tamanho da entrada.
• Exemplo: Percorra uma lista para encontrar um item.
• Aqui, se houver 1.000 elementos, teremos que verificar todos os 1.000; se houver 1 milhão, o tempo aumenta proporcionalmente.

O(n log n) - Tempo quase linear:

• Esse tipo de complexidade geralmente ocorre em algoritmos de classificação eficientes, como Merge Sort ou Quick Sort.
• Exemplo: Algoritmo de classificação eficiente.
• Nesse caso, a lista é repetidamente dividida em partes menores (log n divisões), e cada divisão envolve percorrer toda a lista (n).

O(n²) - Tempo quadrático:

• O tempo de execução cresce proporcionalmente ao quadrado do tamanho da entrada. Isso é típico de algoritmos que exigem comparações ou iterações aninhadas.
• Exemplo: Algoritmo de seleção ou classificação por bolha.
• Se a lista tiver 1.000 elementos, o algoritmo faz 1.000² operações (1 milhão de comparações).

O(2^n) - Tempo exponencial:

• O tempo de execução dobra com cada aumento no tamanho da entrada. Algoritmos com esta complexidade tornam-se ineficientes muito rapidamente.
• Exemplo: Cálculo da série de Fibonacci sem otimização.

O(n!) - Tempo fatorial:

• O tempo de execução cresce fatorialmente com o tamanho da entrada. É extremamente ineficiente e ocorre em problemas combinatórios.
• Exemplo: Algoritmo que gera todas as permutações possíveis de um conjunto.

Por que é importante compreender a ordem da complexidade?

A ordem de complexidade ajuda a prever como seu algoritmo se comportará quando aplicado a grandes conjuntos de dados. Um algoritmo com complexidade O(n) ou O(log n) pode ser executado com eficiência mesmo em milhões de dados, enquanto um algoritmo com complexidade O(n²) ou pior pode se tornar inútil com grandes entradas.

Por exemplo, se você tiver uma lista de 10 milhões de itens, um algoritmo O(n) como a pesquisa linear pode ser gerenciável, mas um algoritmo O(n²) pode levar muito tempo para ser concluído. Escolher o algoritmo certo é crucial para manter um desempenho aceitável.

Tipos de algoritmos recursivos

Os tipos de recursão são diferenciados pela forma como os problemas são divididos e pelo número de chamadas recursivas feitas. Escolher o tipo certo de recursão para um problema específico é fundamental para melhorar a eficiência e o desempenho do algoritmo. A otimização da memória e o tempo de execução são fatores importantes a serem considerados ao decidir a melhor abordagem recursiva para resolver um determinado problema.

1. Recursão de cauda

Na recursão final, a chamada recursiva é a última operação que a função executa antes de retornar o resultado. Isto significa que não há operações pendentes após a chamada recursiva. Este tipo de recursão é eficiente em termos de uso de memória, pois não requer o armazenamento de múltiplas chamadas na pilha de execução. Algumas linguagens de programação otimizam esse tipo de recursão para evitar consumo excessivo de memória.

• Vantagem: Permite otimização de memória em linguagens que suportam otimização de recursão final.
• Desvantagem: Nem sempre é fácil converter um algoritmo em recursão final.

2. Recursão sem cauda

Na recursão não final, a chamada recursiva não é a última instrução executada. Após a chamada recursiva, existem operações pendentes que devem ser realizadas, como multiplicações ou adições. Este tipo de recursão requer mais memória, pois o sistema precisa armazenar o estado de cada chamada recursiva até que todas as chamadas sejam concluídas.

• Vantagem: É mais flexível e pode ser aplicado a uma ampla variedade de problemas.
• Desvantagem: Consome mais memória, pois deve armazenar informações na pilha para cada chamada recursiva.

3. Recursão binária ou árvore recursiva

Na recursão binária, uma função faz mais de uma chamada recursiva em cada etapa. Isso gera uma estrutura em árvore, onde cada nó dá origem a dois (ou mais) subproblemas. Este tipo de recursão é comum em problemas como o cálculo da série de Fibonacci ou no percurso de estruturas de dados hierárquicas, como árvores.

• Vantagem: É adequado para problemas que se enquadram naturalmente em dois subproblemas.
• Desvantagem: Gera muitas chamadas recursivas, o que pode aumentar o tempo de execução se não for otimizado.

4. Recursão múltipla

A recursão múltipla é uma generalização da recursão binária, onde uma função faz mais de duas chamadas recursivas. Este tipo de recursão é aplicado em problemas onde são necessários múltiplos subproblemas para resolver o problema original, como gerar todas as permutações de um conjunto de elementos.

• Vantagem: Útil para problemas que exigem a exploração simultânea de múltiplas soluções ou subproblemas.
• Desvantagem: A complexidade e o número de chamadas recursivas podem crescer exponencialmente, o que pode tornar o algoritmo ineficiente.

5. Recursão aninhada

Na recursão aninhada, uma chamada recursiva é feita dentro de outra chamada recursiva. Isto significa que o resultado de uma chamada recursiva é necessário para calcular a próxima chamada. Esse tipo de recursão pode ser mais complexo de entender e depurar.

• Vantagem: Útil em problemas onde os resultados intermediários de uma chamada recursiva são usados ​​imediatamente na próxima.
• Desvantagem: é mais difícil de acompanhar e pode ser confuso, pois existem múltiplas camadas de chamadas recursivas.

6. Recursão divisão e conquista

Na recursão divisão e conquista, o grande problema é dividido em vários subproblemas menores, que são resolvidos recursivamente. As soluções para esses subproblemas são então combinadas para formar a solução do problema original. Essa abordagem é usada em algoritmos como classificação de lista (Merge Sort) e pesquisa binária.

• Vantagem: É muito eficiente quando o problema pode ser dividido em partes menores de forma equilibrada.
• Desvantagem: Se o problema não puder ser dividido de forma eficiente, a recursão poderá se tornar ineficiente.

7. Recursão Mútua

Na recursão mútua, duas ou mais funções chamam uma à outra, formando um loop de chamadas recursivas entre elas. Isso é usado quando o problema requer que várias funções chamem umas às outras para resolver subproblemas dependentes.

• Vantagem: Útil nos casos em que o fluxo do programa depende de vários processos interligados.
• Desvantagem: Difícil de acompanhar e depurar, pois pode ser difícil entender o fluxo de controle entre funções que chamam umas às outras.

O princípio da indução

A relação entre a recursão e o princípio da indução é fundamental, pois ambos se baseiam na ideia de resolver um problema dividindo-o em subproblemas menores, e ambos dependem de um “caso base” que garante que o processo termine. É uma prática comum ao projetar uma solução recursiva validar se ela cumpre o princípio da indução para determinar se a abordagem está correta ou não.

Vamos ver a relação entre os dois conceitos com base nas definições de ambos:

O que é indução matemática?

A indução matemática ou princípio da indução é um método de prova usado para provar que uma proposição é verdadeira para todos os números naturais (ou inteiros não negativos). O princípio da indução baseia-se em duas etapas fundamentais:

• Caso base: mostra-se que a proposição é verdadeira para um valor inicial, geralmente n = 0 em = 1
• Etapa indutiva: a proposição é assumida como verdadeira para um número arbitrário n (hipótese indutiva), e então é mostrado que, sob essa suposição, também é verdadeira para n + 1

Isto garante que, se a afirmação for verdadeira para o caso base e o passo indutivo estiver correto, a afirmação será verdadeira para todos os números naturais.

O que é recursão?

Como já vimos neste artigo, a recursão é uma técnica em programação e matemática onde uma função ou algoritmo chama a si mesmo para resolver subproblemas menores do problema original. Tal como na indução, a recursão tem dois componentes principais:

• Caso base: uma condição que interrompe chamadas recursivas e retorna um resultado direto (ou seja, a solução mais simples para o problema).
• Caso recursivo: A função chama a si mesma com um subconjunto menor do problema original e usa os resultados dessas chamadas recursivas para construir a solução final.

Relação entre recursão e indução

A principal conexão entre recursão e indução é que ambas seguem uma estrutura semelhante na resolução de problemas. Na verdade, um algoritmo recursivo pode ser comprovado como correto usando indução matemática. Vamos ver como:

Etapa 1: caso base

Na recursão, o caso base define quando o algoritmo para de chamar a si mesmo e resolve o problema diretamente. Isto é o equivalente ao caso base na indução matemática, onde a afirmação é verificada como verdadeira para um valor inicial, como n = 0

Etapa 2: etapa recursiva e etapa indutiva

No caso recursivo, a função chama a si mesma com uma versão menor do problema, até finalmente chegar ao caso base. Este processo é semelhante ao passo indutivo na indução matemática, onde assumimos que a proposição é verdadeira para um número arbitrário n, e depois mostramos que também é verdadeira para n + 1

Num algoritmo recursivo, assume-se que a função resolve corretamente o subproblema (hipótese indutiva), e com esta suposição, construímos a solução para o problema maior (equivalente ao passo indutivo na indução).

Exemplo 1: Fatorial

Calcular o fatorial de um número n é um exemplo clássico de recursão e pode ser comprovado por indução matemática.

1. Definição recursiva do fatorial:

n! =
\begin{cases}
1 & \text{si } n = 0 \\
n \times (n - 1)! & \text{si } n > 0
\end{cases}

2. Prova por indução:

• Caso base: Para n = 0, temos 0! = 1, o que é verdadeiro por definição.
• Passo indutivo: Suponha que n! é verdade para um número n = k (hipótese indutiva), ou seja, k! = k x (k - 1)!

Agora precisamos mostrar que isso também é verdade para n = k + 1 usando a definição recursiva do fatorial:

(k+1)! = (k + 1) xk!

Pela hipótese indutiva, sabemos que k! = k x (k - 1)! , por isso:

(k+1)! = (k + 1) xk!

Isto completa a etapa indutiva, mostrando que a definição recursiva do fatorial é correta para todo n.

Neste exemplo, a recursão fatorial segue exatamente a mesma estrutura de uma prova por indução matemática: o caso base garante que o processo pare, e a etapa recursiva (indutiva) garante que possamos construir soluções maiores a partir de soluções menores.

Exemplo 2: Série Fibonacci

O cálculo da série de Fibonacci também segue esta mesma relação entre recursão e indução:

1. Definição recursiva de Fibonacci:

F(n) =
\begin{cases}
0 & \text{se } n = 0 \\
1 & \text{se } n = 1 \\
F(n - 1) + F(n - 2) & \text{se } n > 1
\end{cases}

2. Prova por indução:

• Caso base: Para n = 0 e n = 1, F(0) = 0 e F(1) = 1, o que é verdadeiro por definição.
• Etapa indutiva: suponha que F(n) esteja correto para n = k e n = k - 1 . Precisamos mostrar que também é correto para n = k + 1.
• Usando a definição recursiva de Fibonacci:

F(k + 1) = F(k) + F(k - 1)

Sabemos, pela hipótese indutiva, que F(k) e F(k - 1) estão corretos, então F(k + 1) também está correto.

Este é outro exemplo em que a recursão segue um princípio indutivo.

Exemplos de problemas complexos resolvidos por recursão

1. Divisão e conquista

Um exemplo clássico de dividir e conquistar é o algoritmo Merge Sort, usado para classificar listas.

Mesclar etapas de classificação:

1. Divisão: Se a lista tiver mais de um elemento, ela será dividida em duas metades.
2. Resolver: O mesmo processo é aplicado recursivamente a cada metade até que cada sublista tenha um único elemento (já ordenado).
3. Combinar: As sublistas ordenadas são combinadas para formar uma única lista ordenada.

Exemplo:

Para a lista [38, 27, 43, 3, 9, 82, 10]:

1. Dividir: Divida em [38, 27, 43] e [3, 9, 82, 10] e depois em listas menores até chegar a listas de item único.
2. Resolver: As listas de um elemento já estão ordenadas.
3. Combinar: As sublistas ordenadas são combinadas em ordem até obter [3, 9, 10, 27, 38, 43, 82].

A complexidade do Merge Sort é O(n log n), pois ele divide logaritmicamente e combina em tempo linear.

2. Problemas de otimização

Um exemplo clássico de problema de otimização é o problema da Mochila , onde o objetivo é maximizar o valor total dos objetos que podem ser incluídos em uma mochila, sem ultrapassar sua capacidade de peso.

Descrição do problema:

Dado um conjunto de objetos, cada um com um peso e um valor, o problema é determinar a combinação de objetos que maximiza o valor total em uma mochila com capacidade de peso limitada.

• Entrada:
• Capacidade da mochila, W (peso máximo que ela pode carregar).
• Uma lista de objetos, cada um com:
• Um peso, wi.
• Um valor, eu vi.
• Objetivo: Maximizar o valor total dos objetos selecionados sem ultrapassar a capacidade da mochila.

Tipos de problemas de mochila:

1. Mochila 0/1: Para cada item, você pode incluí-lo completamente na mochila ou não incluí-lo de jeito nenhum. Você não pode dividir objetos.
2. Mochila fracionária: São permitidos objetos fracionários, ou seja, você pode pegar uma parte de um objeto.

Exemplo:

Suponha que você tenha uma mochila com capacidade para 15 kg e os seguintes objetos:

• Objeto 1: Peso = 10 kg, Valor = 60.
• Objeto 2: Peso = 5 kg, Valor = 40.
• Objeto 3: Peso = 3 kg, Valor = 30.

Pergunta: Quais itens você deve incluir na mochila para maximizar o valor total, sem ultrapassar o limite de 15kg?

Solução 0/1 (sem fracionamento):

Se você selecionar os objetos 1 e 2, o peso total será de 15 kg e o valor será 60 + 40 = 100, que é a solução ideal para este caso.

Métodos para resolver o problema da mochila:

1. Algoritmos de Programação Dinâmica (para o caso 0/1): É uma abordagem eficiente para resolver exatamente este problema, utilizando uma tabela que armazena os resultados dos subproblemas.
2. Algoritmos Greedy (para o caso fracionário): Seleciona objetos com base no valor por unidade de peso, o que é ideal quando o fracionamento de objetos é permitido.

Importância:

Este problema é fundamental na otimização combinatória e suas aplicações incluem alocação de recursos, planejamento financeiro e outras áreas onde se busca maximizar os benefícios sujeitos a restrições.

E isso é tudo para a introdução à programação recursiva.

Esperamos que tenham gostado e que não se esqueçam de nos seguir no LinkedIN, onde anunciamos cada novo artigo, e nas restantes redes sociais onde começaremos a carregar conteúdos sobre ciência mas diferentes.

https://www.linkedin.com/company/the-science-driven-company/

https://www.instagram.com/science.driven/

https://www.tiktok.com/@science.driven

https://www.youtube.com/@ScienceDriven