Quer aprender tudo sobre recursão em programação? Este tutorial sobre recursão em Python ajudará você a começar.
A recursão é uma técnica de resolução de problemas muito útil para adicionar à caixa de ferramentas do seu programador. Embora inicialmente muitas vezes seja difícil entender, a recursão pode ajudá-lo a encontrar soluções mais elegantes para problemas complexos.
Neste tutorial, adotaremos uma abordagem baseada no código para aprender recursão usando Python. Em particular, abordaremos:
- O básico da recursão
- Funções recursivas e como funcionam
- Implementação Python de funções recursivas
- Diferenças entre abordagens iterativas e recursivas para resolução de problemas
Vamos começar!
últimas postagens
O que é recursão?
A recursão é uma técnica de programação em que uma função chama a si mesma repetidamente para resolver um problema.
Basicamente, a recursão é uma abordagem de resolução de problemas que envolve dividir um problema complexo em subproblemas menores e idênticos. Essencialmente, permite resolver um problema em termos de versões mais simples dele mesmo.
Então, como implementamos a recursão no código? Para fazer isso, vamos entender como funcionam as funções recursivas.
Compreendendo funções recursivas
Definimos uma função recursiva que chama a si mesma dentro de sua definição. Cada chamada recursiva representa uma versão menor ou mais simples do problema original.
Para garantir que a recursão eventualmente termine, as funções recursivas devem incluir um ou mais casos base – condições sob as quais a função para de chamar a si mesma e retorna um resultado.
Vamos detalhar isso ainda mais. Uma função recursiva consiste em:
- Caso Base: O caso base é uma condição (ou condições) que determinam quando a recursão deve parar. Quando o caso base é atendido, a função retorna um resultado sem fazer mais chamadas recursivas. Um caso base é essencial para evitar recursão infinita.
- Caso recursivo: O caso recursivo define como dividir o problema em subproblemas menores. Nesta parte da função, a função chama a si mesma com entradas modificadas. Cada chamada recursiva é, portanto, um passo em direção ao caso base.
A seguir, vamos discutir o que acontece quando você chama uma função recursiva.
Como a recursão funciona nos bastidores
Quando uma função é chamada, um registro do seu contexto de execução é colocado na pilha de chamadas. Este registro inclui informações sobre os argumentos da função, variáveis locais e o local para retornar quando a função terminar a execução.
No caso de funções recursivas, quando uma função chama a si mesma, um novo registro é colocado na pilha de chamadas, suspendendo efetivamente a execução da função atual. A pilha permite que o Python acompanhe todas as chamadas de função pendentes, incluindo aquelas de chamadas recursivas.
Até que o caso base seja alcançado, a recursão continua. Quando o caso base retorna um resultado, as chamadas de função são resolvidas uma por uma — com cada função retornando seu resultado ao nível anterior da pilha de chamadas. Este processo continua até que a chamada de função inicial seja concluída.
Implementando Recursão em Python
Nesta seção, exploraremos três exemplos simples de recursão:
Para cada exemplo, apresentaremos o problema, forneceremos a implementação recursiva do Python e, em seguida, explicaremos como funciona a implementação recursiva.
#1. Cálculo fatorial usando recursão
Problema: Calcule o fatorial de um inteiro não negativo n, denotado como n!. Matematicamente, o fatorial de um número n é o produto de todos os inteiros positivos de 1 a n.
O cálculo fatorial se presta bem à recursão, conforme mostrado:
Aqui está a função recursiva para calcular o fatorial de um determinado número n:
def factorial(n):
# Base case
if n == 0 or n == 1:
return 1
# Recursive case: n! = n * (n-1)!
else:
return n * factorial(n - 1)
Vamos calcular 5! usando a função fatorial():
factorial_5 = factorial(5) print(factorial(5)) # Output: 120
Agora vamos ver como funciona a função:
- Temos um caso base que verifica se n é igual a 0 ou 1. Se a condição for atendida, as funções retornam 1. Lembre-se de que 0! é 1 e 1 também!.
- Se n for maior que 1, calculamos n! multiplicando n pelo fatorial de n-1. Isso é expresso como n * fatorial (n – 1).
- A função continua fazendo chamadas recursivas com valores decrescentes de n até atingir o caso base.
#2. Números de Fibonacci com recursão
Problema: Encontre o termo no n-ésimo índice do Sequência de Fibonacci. A sequência de Fibonacci é definida da seguinte forma: F(0) = 0, F(1) = 1 e F(n) = F(n-1) + F(n-2) para n >= 2.
def fibonacciSeq(n):
# Base cases
if n == 0:
return 0
elif n == 1:
return 1
# Recursion: F(n) = F(n-1) + F(n-2)
else:
return fibonacciSeq(n - 1) + fibonacciSeq(n - 2)
Vamos executar a função:
fib_5 = fibonacciSeq(5) print(fib_5) # Output: 5
Veja como funciona a função:
- Vamos começar discutindo os casos básicos. Se n for 0, retorna 0. E se n for 1, retorna 1. Lembre-se de F(0) = 0 e F(1) = 1.
- No caso recursivo, se n for maior que 1, a função calcula F(n) somando os termos F(n-1) e F(n-2). Isso é expresso como fibonacciSeq(n – 1) + fibonacciSeq(n – 2).
- A função continua fazendo chamadas recursivas com valores decrescentes de n até atingir os casos base.
#3. Implementação Recursiva de Pesquisa Binária
Problema: Implemente um algoritmo de pesquisa binária usando recursão para encontrar a posição de um elemento alvo em uma lista ordenada.
Aqui está a implementação recursiva da pesquisa binária:
def binarySearch(arr, target, low, high):
# Base case: target not found
if low > high:
return -1
mid = (low + high) // 2
# Base case: target found
if arr[mid] == target:
return mid
# Recursive case: search left or right half of the array
elif arr[mid] > target:
return binarySearch(arr, target, low, mid - 1)
else:
return binarySearch(arr, target, mid + 1, high)
A função binarySearch continua dividindo o intervalo de pesquisa pela metade com cada chamada recursiva até encontrar o alvo ou determinar que o alvo não está na lista.
Aqui está um exemplo de execução da função:
arr = [5, 8, 13, 24, 37, 49, 51, 64, 72, 88, 96] target = 37 idx = binarySearch(arr, target, 0, len(arr)-1) print(idx) # Output: 4
Vamos detalhar o que a função faz:
- Na implementação recursiva da pesquisa binária, temos dois casos base. Primeiro, se o valor baixo for maior que o alto, significa que o elemento alvo não está na lista. Portanto, retornamos -1 para indicar que o alvo não foi encontrado.
- O outro caso base verifica se o elemento no índice intermediário do intervalo de pesquisa atual é igual ao destino. Se corresponderem, retornamos o índice mid, indicando que encontramos o alvo.
- No caso recursivo, se o elemento do meio for maior que o alvo, pesquisamos recursivamente a metade esquerda do array chamando binarySearch(arr, target, low, mid – 1). Se o elemento do meio for menor que o alvo, procuramos a metade direita chamando binarySearch(arr, target, mid + 1, high).
Abordagem Recursiva vs. Iterativa
A abordagem iterativa – usando loops – é outra abordagem comum para resolução de problemas. Então, como isso é diferente da recursão? Vamos descobrir.
Primeiro, comparamos soluções recursivas e iterativas para um problema comum: calcular o fatorial de um número.
Aqui está a implementação recursiva do cálculo fatorial:
def factorialRec(n):
# Base case
if n == 0 or n == 1:
return 1
# Recursive case: n! = n * (n-1)!
else:
return n * factorial(n - 1)
Como sabemos que o fatorial de um número não negativo é o produto de todos os números de 1 a n, também podemos escrever uma implementação iterativa usando loops.
def factorialIter(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
Ambas as implementações fornecem resultados idênticos.
factorial_5 = factorialRec(5) print(factorial_5) # Output: 120 factorial_5 = factorialIter(5) print(factorial_0) # Output: 120
Mas será preferível uma abordagem iterativa à recursão? Quando há recursão profunda — com muitas chamadas de função — você pode encontrar erros por exceder a profundidade da recursão. O loop é uma opção melhor para problemas cuja implementação recursiva requer muitas chamadas de função para atingir o caso base.
Vamos resumir as diferenças entre implementações iterativas e recursivas:
RecursoAbordagem recursivaAbordagem iterativaEstruturaUsa chamadas de função recursivas e depende da pilha de chamadas.Usa loops para iteração sem chamadas de função adicionais.Casos baseRequer casos base explícitos para interromper a recursão.Normalmente usa condições de loop para encerramento.DesempenhoPode ser menos eficiente em termos de memória devido à pilha de chamadas . A recursão profunda às vezes pode levar a erros de estouro de pilha. Geralmente mais eficiente em termos de memória e menos propenso a erros de estouro de pilha. Depuração Pode ser difícil depurar devido a múltiplas chamadas de função e contextos de execução aninhados. .Abordagem Iterativa vs Recursiva
Conclusão
Neste artigo, começamos aprendendo o que é recursão e como definir funções recursivas com casos base e relações de recorrência.
Em seguida, escrevemos alguns códigos Python – implementações recursivas de problemas comuns de programação. Finalmente, aprendemos as diferenças entre abordagens iterativas e recursivas e os prós e contras de cada uma dessas abordagens.
A seguir, verifique esta lista de perguntas da entrevista sobre Python.