PDF - VERSÃO DE IMPRESSÃO

Lição 9 - Recursividade: funções recursivas e pontos de fuga

objetivo

Olá, estudante, tudo bem com você?

Depois de compreender todo o paradigma de orientação a objetos, mais uma vez, agora com a linguagem de programação Python, chegou a hora de lhe fornecer uma compreensão sólida da recursividade na programação. A recursividade é um conceito fundamental em programação, em que uma função pode chamar a si mesma para resolver um problema menor e, eventualmente, chegar à solução do problema original. Isso é semelhante a uma abordagem dividir e conquistar, em que um problema é quebrado em subproblemas menores e mais gerenciáveis.

Compreender a recursividade é fundamental para se tornar um programador mais habilidoso, pois ela é uma técnica poderosa para resolver uma ampla variedade de problemas de maneira eficiente e elegante. Ao final desta lição, você estará bem equipado para utilizar a recursividade em suas próprias soluções de programação em Python.

problematização

Um problema muito comum que pode ser resolvido de forma elegante usando recursividade na programação está relacionado à hierarquia organizacional de uma empresa. A maioria das pessoas está familiarizada com essa estrutura, que inclui cargos, como CEO, gerentes de departamento, supervisores e funcionários. Gerenciar e representar essa hierarquia de maneira eficiente em sistemas de software pode ser desafiador, mas a recursividade oferece uma solução poderosa.

A recursividade pode ser usada para representar a hierarquia organizacional de forma aninhada, em que cada funcionário é tratado como um “nó” que pode ter subordinados. O caso base que se tem é que cada funcionário possui um identificador exclusivo e uma lista de subordinados. O caso base ocorre quando um funcionário não tem subordinados, o que encerra a recursão. Já a chamada recursiva ocorre quando um funcionário tem subordinados, a recursão é usada para explorar a hierarquia em níveis mais profundos, ou seja, o subordinado, também, tem subordinados e assim por diante. O último elemento é o chamado ponto de fuga, que ocorre quando um funcionário não tem subordinados ou quando todos os subordinados foram processados.

case

Hoje, você conhecerá um case fictício sobre uma startup chamada Social Insight, que está desenvolvendo um software avançado de análise de redes sociais para ajudar empresas a entenderem melhor o comportamento de seus clientes nas plataformas de mídia social. Eles se deparam com o desafio de rastrear e analisar as conexões entre usuários e suas interações em uma variedade de plataformas de mídia social.

O problema central era criar uma estrutura de dados que pudesse representar grafos complexos de redes sociais. Cada usuário poderia ter vários amigos, e esses amigos, por sua vez, também, teriam amigos. Além disso, as interações entre usuários deveriam ser rastreadas, incluindo curtidas, comentários e compartilhamentos. A equipe de desenvolvimento da Social Insight optou por usar a recursividade para lidar com essa complexidade. Eles criaram uma estrutura de dados chamada Grafo Social, em que cada nó representava um usuário e cada aresta representava uma conexão de amizade.

O uso da recursividade foi direcionado na criação do grafo social, em que eles começaram com um usuário central, como um cliente da empresa. A partir desse ponto, com a recursividade, exploraram os amigos desse usuário e, por sua vez, os amigos dos amigos, construindo o grafo de maneira dinâmica. Além disso, conseguiram, também, efetuar o rastreamento de interações e análises complexas, como encontrar usuários com interesses semelhantes ou identificar influenciadores nas redes sociais.

Sendo assim, com esse case, mesmo sendo fictício, podemos ver uma situação em que os conteúdos da lição de hoje podem ser aplicados. Porém, para que você futuro desenvolvedor consiga solucionar problemas semelhantes a esse, é necessário que você domine esse assunto! Portanto, vamos nos aprofundar?

Conceitualização

A recursividade em programação se refere à capacidade de uma função se chamar a si mesma como parte de sua própria execução. Segundo Groner (2018), a recursão é um método para resolução de problemas que consiste em solucionar partes menores do mesmo problema até resolvermos o problema original, mais amplo. Em geral, ela envolve chamar a própria função. Para que a recursividade funcione, é essencial ter dois elementos principais:

Caso Base: esse é o ponto de parada da recursão. É uma condição que indica quando a função recursiva deve parar de se chamar a si mesma e começar a retornar valores. O caso base evita que a recursão entre em um loop infinito.
Chamada Recursiva: essa é a parte em que a função se chama a si mesma com argumentos diferentes, geralmente, reduzindo o problema original em um problema menor e mais simples. Isso leva à convergência em direção ao caso base.

A recursividade é, frequentemente, usada para resolver problemas que podem ser naturalmente divididos em subproblemas semelhantes e menores. É uma técnica poderosa, mas requer cuidado na definição do caso base e na garantia de que a recursão eventualmente alcance o caso base para evitar loops infinitos.

Um exemplo clássico de recursão é o cálculo do fatorial (operação matemática que consiste em multiplicar todos os números inteiros positivos de um até um número específico. Ex: 5!=5×4×3×2×1=120) de um número, em que o fatorial de um número n é calculado multiplicando n pelo fatorial de n-1, até que o caso base (fatorial de 0 ou 1) seja alcançado.

Chamada da função recursiva

A compreensão de como uma função pode chamar a si mesma é fundamental para entender o conceito de recursividade em programação. Quando uma função chama a si mesma, isso cria um processo repetitivo que permite que a função resolva um problema de maneira iterativa, dividindo-o em partes menores e mais gerenciáveis. Veja uma explicação passo a passo de como isso funciona:

Chamada inicial da função
- Tudo começa com a chamada inicial da função a partir do código principal ou de outra função.
- Essa primeira chamada é como qualquer outra chamada de função, com seus próprios parâmetros e variáveis locais.
Execução da função
- A função começa a ser executada a partir do início, como qualquer função normal.
- À medida que a função executa suas instruções, ela pode encontrar um ponto em que precisa resolver um subproblema semelhante ao problema original, mas em uma escala menor.
Chamada recursiva
- Quando a função encontra a necessidade de resolver um problema semelhante, ela não calcula o resultado diretamente.
- Em vez disso, a função faz uma chamada a si mesma com argumentos apropriados para resolver o subproblema.
- Essa chamada recursiva cria uma nova instância da função no topo da pilha de chamadas.
Pilha de chamadas
- Ao usar recursão, as chamadas de função serão empilhadas umas sobre as outras.
- Cada chamada da função é colocada na pilha de chamadas.
- Cada instância da função possui suas próprias variáveis locais e parâmetros.
Execução recursiva
- As chamadas recursivas continuam a se empilhar na pilha de chamadas, criando uma cadeia de execuções.
- Cada instância da função trabalha em seu próprio subproblema.
Caso base
- Eventualmente, uma chamada recursiva atinge um ponto em que o subproblema é tão simples que pode ser resolvido diretamente.
- Esse ponto é chamado de “caso base”. É uma condição que indica quando a recursão deve parar.
Retorno e desenfileiramento
- Quando um caso base é alcançado, a função começa a retornar um valor.
- À medida que as chamadas recursivas começam a retornar valores, elas são desenfileiradas da pilha de chamadas, liberando a pilha gradualmente.
Resultados combinados
- À medida que as chamadas recursivas são desenfileiradas e retornam valores, esses valores podem ser combinados para calcular o resultado do problema original.
Fim da recursão
- Eventualmente, todas as chamadas recursivas são desenfileiradas, e a função atinge o fim da sua execução.
- O resultado do problema original é retornado à chamada inicial da função.

Essa é a essência da recursividade, resolver um problema dividindo-o em partes menores, chamando a função a si mesma para resolver essas partes e combinando os resultados para obter a solução completa. É importante ter um caso base adequado para evitar recursões infinitas e garantir que a recursão termine bem.

Ponto de fuga

Em uma função recursiva, o ponto de fuga é o ponto ou condição em que a recursão para de ocorrer, e a função começa a retornar valores. Também, é conhecido como o ponto em que a recursão “escapa” ou termina. O ponto de fuga é essencial para evitar que a função entre em um loop infinito, uma vez que, sem ele, a recursão continuaria indefinidamente.

O ponto de fuga é, geralmente, definido em um caso base na função recursiva. O caso base é uma condição que, quando satisfeita, indica que a função deve parar de se chamar a si mesma e começar a retornar valores. O caso base atua como um mecanismo de parada que quebra o processo recursivo e permite que a função retorne resultados.

Em resumo, o ponto de fuga em uma função recursiva é o momento em que a recursão é interrompida, e a função começa a retornar valores. É um componente crítico para garantir que a recursão seja controlada e que a função termine de maneira apropriada.

O ponto de fuga em uma função recursiva está diretamente relacionado ao caso base. O caso base é a condição que determina quando a recursão deve parar, e o ponto de fuga é o momento em que a função começa a retornar valores de volta à pilha de chamadas. Esses dois conceitos estão intimamente ligados e desempenham papéis complementares no processo recursivo.

Vamos resumir as informações sobre caso base, ponto de fuga e a relação entre eles? Acompanhe:

● Caso Base

O caso base é uma condição específica que é verificada em cada chamada recursiva da função.
Quando a condição do caso base é atendida, a função não faz chamadas recursivas adicionais e começa a retornar um valor imediatamente.
O caso base é fundamental para evitar recursões infinitas, pois fornece uma maneira de sair do processo recursivo.

● Ponto de Fuga

O ponto de fuga é o ponto na execução da função em que ela começa a retornar valores à pilha de chamadas.
O ponto de fuga é ativado quando a função atinge o caso base ou quando uma chamada recursiva alcança o caso base e começa a retornar valores.
A partir do ponto de fuga, os valores retornados, pelas chamadas recursivas, são propagados de volta por meio da pilha de chamadas até a chamada inicial da função.

● Relação

O caso base é a condição que determina quando a função deve “escapar” da recursão.
Quando o caso base é alcançado, a função atinge o ponto de fuga, em que começa a retornar valores em vez de fazer chamadas recursivas.
O ponto de fuga está diretamente relacionado à decisão de parar a recursão e começar a desenfileirar as chamadas recursivas da pilha de chamadas.

A recursividade, como vimos anteriormente, é um conceito fundamental na programação. Essa abordagem permite a resolução eficiente de problemas complexos, decompondo-os em subproblemas mais simples. A importância dessa temática está na sua capacidade de simplificar a resolução de problemas, tornando o código mais legível e modular. A recursividade é frequentemente utilizada para lidar com problemas que podem ser decompostos em instâncias menores do mesmo problema. Ao compreender e aplicar corretamente funções recursivas e pontos de fuga, você conseguirá desenvolver soluções eficazes e escaláveis para uma variedade de desafios de programação.

saiba aplicar

A compreensão e aplicação da recursividade, incluindo funções recursivas e pontos de fuga, são essenciais para o profissional técnico em desenvolvimento de sistemas. Como estudamos, essa abordagem permite resolver problemas complexos de forma eficiente, contribui para um código mais legível e, como consequência, facilita a compreensão e manutenção. Com o conhecimento em recursividade, você, futuro técnico, pode, facilmente, identificar e corrigir erros e garantir a manutenção e o aprimoramento contínuo do sistema.

Agora, você implementará o cálculo fatorial, de forma recursiva, em Python. Para relembrá-lo, o cálculo de fatorial é um conceito matemático que envolve a multiplicação de todos os números inteiros positivos de um até um número específico. Por exemplo: para calcular o fatorial de 5, a conta seria:

5! = 1 * 2 * 3 * 4 * 5 = 120

Siga o passo a passo, a seguir, para a implementação:

Abra seu navegador web e acesse o site OnlineGDB em https://www.onlinegdb.com/.
Escolha a linguagem de programação que deseja usar. Selecione “Python”, na lista suspensa.
No editor de código, você pode escrever o código Python para calcular o fatorial de forma recursiva, conforme a Figura 1.

Figura 1 - Cálculo de fatorial em Python
Fonte: o autor.

#PraCegoVer: na figura, temos, na linha 1, def calcular_fatorial(n):; na linha 2, temos if n == 0:; na linha 3, temos return 1; na linha 4, temos else:; na linha 5, temos return n * calcular_fatorial(n - 1); na linha 7, temos resultado = calcular_fatorial(5); e, na linha 8, temos print(“O fatorial de 5 é:”, resultado). Na linha 6, não há conteúdo escrito.

Após escrever o código, você pode clicar no botão “Run”, na parte superior do editor. Isso executará o código Python e mostrará o resultado na janela de saída.
Na janela de saída, você verá a saída do seu programa, que, nesse caso, será “O fatorial de 5 é: 120”. Isso significa que o cálculo do fatorial de 5 foi feito com sucesso usando a recursão.

Segue algumas explicações de como o código da Figura 1 realiza o cálculo do fatorial de 5:

linha 1: define uma função chamada calcular_fatorial que aceita um argumento n, que é o número para o qual você quer calcular o fatorial.
linha 2: essa é a verificação do caso base. Verifica se n é igual a 0. Se for, significa que você chegou ao caso base, e a função retorna 1.
linha 3: se o caso base for atendido, a função retornará imediatamente 1 e encerra a recursão.
linha 4: se n não for igual a 0, significa que não estamos no caso base, então, continuamos para o bloco de código a seguir:
linha 5: essa é a parte da chamada recursiva. Aqui, você multiplicou n pelo resultado da chamada recursiva calcular_fatorial(n -1). Isso significa que você estará calculando o fatorial de n multiplicando-o pelo fatorial de n-1. Isso é feito de forma recursiva até que você atinja o caso base, que é quando n se torna 0.
linha 6: realiza a chamada da função calcular_fatorial(5) e armazena seu resultado na variável resultado.
linha 7: exibe na tela para o usuário “O fatorial de 5 é: 120”.

Você, agora, implementou, com sucesso, o cálculo fatorial, de forma recursiva, em Python usando o OnlineGDB. Esse é apenas um exemplo simples, e você pode modificar o código para calcular o fatorial de outros números. Certifique-se de experimentar e explorar mais sobre programação recursiva e suas aplicações.

REFERÊNCIAS

GRONER, L. Estruturas de dados e algoritmos com JavaScript. São Paulo: Novatec, 2018.

Page updated

Google Sites

Report abuse