Conceito de função recursiva do Python: tutorial do Python para iniciantes

No mundo da ciência da computação, a recursão refere-se à técnica de definir uma coisa em seus próprios termos. Em outras palavras, uma função recursiva chama a si mesma para processamento. Neste artigo, vamos entender o conceito de função recursiva em Python , uma linguagem de programação muito utilizada no século XXI.

O que é Recursão Python ?

Em Python, um grupo de instruções relacionadas que executam uma tarefa específica é chamado de 'função'. Assim, as funções dividem seu programa em pedaços menores. E é de conhecimento comum que uma função pode chamar outras funções em Python.

Mas algumas outras funções podem chamar a si mesmas. Estas são conhecidas como funções recursivas. Considere dois espelhos paralelos colocados um de frente para o outro. Agora, qualquer objeto mantido entre os espelhos seria refletido recursivamente.

Vamos entrar em detalhes sobre a função recursiva para entender claramente seu funcionamento.

A função recursiva

Sabemos que uma função recursiva em Python chama a si mesma conforme é definida por meio de expressões auto-referenciais, ou seja, em termos de si mesma. Ele continua repetindo seu comportamento até que uma condição específica seja atendida para retornar um valor ou resultado. Vejamos agora um exemplo para aprender como funciona.

Leia também: Perguntas e respostas da entrevista em Python

Suponha que você queira descobrir o fatorial de um inteiro. O fatorial nada mais é do que o produto de todos os números, começando de 1 até aquele inteiro. Por exemplo, o fatorial de 5 (escrito como 5!) seria 1*2*3*4*5*6, ou seja, 720. Temos uma função recursiva calc_factorial(x), que é definida da seguinte forma:

def calc_factorial(x):

#Função recursiva para encontrar o fatorial de um inteiro

se x == 1:

retornar 1

outro

return (x * calc_factorial(x-1))

O que aconteceria se você chamasse essa função com um inteiro positivo como 4? Bem, cada chamada de função adicionará um quadro de pilha até chegarmos ao caso base (quando o número reduz para 1). A condição base é necessária para que a recursão termine e não continue indefinidamente. Assim, no caso dado, o valor 24 será retornado após a quarta chamada.

Implementação de função recursiva em Python

Pode haver aplicações variadas de funções recursivas em Python. Por exemplo, você quer fazer um gráfico com um padrão repetido, digamos um floco de neve Koch. A recursão pode ser usada para gerar padrões fractais, que são compostos de versões menores do mesmo design.

Outro exemplo é o da resolução de jogos. Você pode escrever algoritmos recursivos para resolver Sudoku e vários jogos complexos. A recursão é mais comumente usada em problemas de busca, classificação e travessia.

Uma característica marcante da função é que a implementação recursiva permite retrocesso. Assim, a recursão trata de construir uma solução de forma incremental e remover aquelas soluções que não satisfazem as restrições do problema em nenhum estágio. Duas coisas são necessárias para conseguir isso – manter o estado e a estrutura de dados adequada. Continue lendo para se familiarizar com esses termos.

Leia: Salário do desenvolvedor Python na Índia

Mantendo o estado

Cada chamada recursiva em Python tem seu próprio contexto de execução. Ao lidar com funções recursivas em Python, você precisa encadear o estado por meio de cada chamada recursiva. Com isso, o estado atual passa a fazer parte do contexto de execução da chamada atual. Você também pode manter o estado no escopo global.

Por exemplo, se você estiver usando recursão para calcular 1+2+3+4+…….+10. Aqui, o número atual que você está adicionando e a soma acumulada até esse ponto formam o estado que você precisa manter. Manter o estado envolve passar o estado atual atualizado como argumentos em cada chamada. Veja como você pode fazer isso.

def sum_numbers(current_number, acumulado_sum)

#Caso base

#Retorna o estado final

se o número atual==11:

retornar soma_acumulada

#caso recursivo

#Thread o estado por meio de chamada recursiva

Outro:

return sum_numbers(current_number + 1, acumulado_sum + current_number)

Como alternativa, você pode usar o estado mutável global. Para manter o estado usando esse método, você mantém o estado no escopo global.

número_atual = 1

soma_acumulada = 0

def sum_numbers():

número_atual global

soma_acumulada global

#Caso base

se número_atual==11

retornar soma_acumulada

#caso recursivo

outro:

soma_acumulada = soma_acumulada + número_atual

número_atual = número_atual + 1

return sum_numbers()

Estruturas de dados recursivas

Uma estrutura de dados é considerada recursiva se puder ser definida em termos de versões menores e mais simples de si mesma. Exemplos de estruturas de dados recursivas incluem listas, árvores, estruturas hierárquicas, dicionários, etc. Uma lista pode ter outras listas como elementos. Uma árvore tem subárvores, nós folha e assim por diante.

É importante notar aqui que a estrutura de funções recursivas é frequentemente modelada após as estruturas de dados que ela recebe como entradas. Assim, estruturas de dados recursivas e funções recursivas andam de mãos dadas.

Recursão na Computação de Fibonacci

O matemático italiano Fibonacci definiu pela primeira vez os números de Fibonacci no século 13 para modelar o crescimento populacional de coelhos. Ele deduziu que a partir de um par de coelhos no primeiro ano, o número de pares de coelhos nascidos em um determinado ano é igual ao número de pares de coelhos nascidos em cada um dos últimos dois anos. Isso pode ser escrito como: Fn = Fn-1 + Fn-2 (Casos base: F0=1 e F1=1).

Quando você escreve uma função recursiva para calcular o número de Fibonacci, isso pode resultar em recursão ingênua. Isso acontece quando a definição da função recursiva é seguida ingenuamente, e você acaba recalculando valores desnecessariamente. Para evitar a recomputação, você pode aplicar o decorador lru_cache à função. Ele armazena em cache os resultados e evita que o processo se torne ineficiente.

Leia mais: As 10 principais ferramentas Python que todo desenvolvedor Python deve conhecer

Prós e contras do recursivo

A recursão ajuda a simplificar uma tarefa complexa dividindo-a em subproblemas. Funções recursivas tornam o código mais limpo e também descomplicam a geração de sequências. Mas a recursão não vem sem suas limitações. Às vezes, as chamadas podem ser caras e ineficientes, pois consomem muito tempo e memória. Funções recursivas também podem ser difíceis de depurar.

Empacotando

Neste artigo, abordamos o conceito de recursão do Python , demonstramos usando alguns exemplos e também discutimos algumas de suas vantagens e desvantagens. Com todas essas informações, você pode explicar facilmente funções recursivas em sua próxima entrevista em Python!

Se você está curioso para aprender sobre ciência de dados, confira o PG Diploma in Data Science do IIIT-B & upGrad, que é criado para profissionais que trabalham e oferece mais de 10 estudos de caso e projetos, workshops práticos práticos, orientação com especialistas do setor, 1- on-1 com mentores do setor, mais de 400 horas de aprendizado e assistência de trabalho com as principais empresas.