Algunha vez estivo atrapado nun ciclo aparentemente interminable no que un problema segue ramificando en fragmentos máis pequenos?
Se é así, quizais che atopes co apaixonante mundo da recursividade. Aínda que poida parecer difícil de entender, non te preocupes! Nesta publicación, faremos unha viaxe interesante para coñecer os tipos de recursividades.
Así que abróchate o cinturón mentres exploramos numerosos enfoques recursivos. Prepárate para entrar no fascinante reino da recursividade e observa a súa notable capacidade para resolver problemas complicados.
Que son exactamente as recurrencias?
En palabras básicas, a recursión é unha poderosa técnica de programación que inclúe unha función que se chama a si mesma durante a execución. É como mirarse nun espello e ver unha imaxe dentro dunha imaxe, dando como resultado un ciclo autorreferencial.
Podemos abordar grandes problemas usando a recursividade dividíndoos en subproblemas máis pequenos e máis manexables.
É semellante a montar un rompecabezas, onde unha peza enlaza con outras partes para producir unha imaxe completa. A recursión permítenos resolver problemas de forma elegante e eficiente repetindo o mesmo conxunto de instrucións con varias entradas.
1-Recursión directa
A recursividade directa é o tipo máis básico de recursividade, no que unha función se chama a si mesma directamente. Implica dividir un problema problemático en subproblemas máis pequenos ata conseguir un caso base, o que leva á terminación.
A función recursiva chámase a si mesma con varias entradas, o que permite que se repita a execución do mesmo conxunto de instrucións. Cada invocación constrúese sobre a anterior, achegándose progresivamente ao caso base que fai que remate a recursividade.
Imos comprobar este exemplo.
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1)
countdown(5)
saída:
5
4
3
2
1
2-Recursión indirecta
A recursión indirecta engade un xiro intrigante ao camiño recursivo. En contraste coa recursividade directa, que implica unha función que se chama explícitamente a si mesma, a recursividade indirecta inclúe unha cadea de chamadas de función.
Unha función chama a outra, que logo pode chamar á función orixinal ou a calquera outra función que finalmente volva á orixinal. Esta rede interconectada de chamadas de función produce un baile apaixonante no que varias funcións colaboran para solucionar un problema.
Exemplo:
def function_A(n):
if n > 0:
print("A:", n)
function_B(n - 1)
def function_B(n):
if n > 0:
print("B:", n)
function_A(n - 1)
function_A(3)
saída:
A: 3
B: 2
A: 1
3-Recursión lineal
Considere unha viaxe por unha ruta recta, un paso á vez, ata chegar ao seu obxectivo. Esta técnica secuencial está plasmada pola recursividade lineal, na que unha función realiza unha única chamada recursiva en cada iteración da función.
Con cada chamada recursiva, o proceso recursivo achégase a un caso base reducindo o tamaño do problema. Procede dun xeito claro e lineal, resolvendo subproblemas un a un ata chegar á resposta definitiva.
Exemplo:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
result = factorial(5)
print(result)
saída:
120
4-Recursión da árbore
Cando unha función se ramifica en varias chamadas recursivas, entramos no mundo da recursión en árbore. Unha función na recursión en árbore xera moitas chamadas recursivas, cada unha das cales resolve un subproblema separado, tal e como fan as ramas dunha árbore.
Esta estrutura de ramificación permite a investigación simultánea de varias rutas, desglosando de forma efectiva os problemas complicados en compoñentes máis pequenos e interrelacionados.
Exemplo:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
result = fibonacci(6)
print(result)
saída:
8
5-Recursión aniñada
A recursión anidada engade un grao de complexidade emocionante ao universo recursivo. Nesta forma de recursión, unha función incorpora unha chamada recursiva como argumento dentro doutra chamada recursiva.
A chamada recursiva interna actúa sobre un valor que depende da chamada recursiva externa. A complexidade crece con cada invocación aniñada, culminando nun patrón intrigante de chamadas recursivas aniñadas.
Exemplo:
def nested_recursion(n):
if n > 100:
return n - 10
return nested_recursion(nested_recursion(n + 11))
result = nested_recursion(95)
print(result)
Resultado:
91
6-Recurso de cola
A recursión de cola é unha técnica de optimización para algoritmos recursivos que poden mellorar o seu rendemento. A chamada recursiva aparece como a acción final dunha función con recursión de cola, facendo.
Como non hai operacións pendentes despois da chamada recursiva, o compilador ou intérprete pode simplificar a recursividade substituíndoa por un simple salto.
Este enfoque de optimización, coñecido como optimización de chamadas de cola, reduce o requisito de que cada chamada recursiva manteña un cadro de pila, o que dá como resultado unha maior velocidade e un menor uso da memoria.
Exemplo:
def tail_factorial(n, result=1):
if n == 0:
return result
return tail_factorial(n - 1, result * n)
result = tail_factorial(5)
print(result)
Saída:
120
7-Recursión sen cola
En contraste coa recursividade de cola, a recursividade sen cola implica actividades extra realizadas despois da chamada recursiva dentro dunha función. Antes de realizar máis accións, cada chamada recursiva debe completarse e volver.
Como consecuencia, ata que se alcance o caso base e remate a recursividade, mantense unha pila de operacións pendentes. A recursividade sen cola usa con frecuencia máis memoria e é menos eficiente que a recursividade na cola, pero segue sendo unha ferramenta útil para abordar unha variedade de problemas.
Exemplo:
def non_tail_sum(n):
if n == 0:
return 0
return n + non_tail_sum(n - 1)
result = non_tail_sum(5)
print(result)
saída:
15
Envolver
A recursión é un concepto intrigante na programación. Permítenos abordar problemas complicados de forma recursiva e autorreferencial.
Ofrece un método distinto para pensar e resolver problemas, dividíndoos en anacos máis pequenos e máis manexables. Cando se traballa con recursividade, non obstante, é fundamental prestar atención a algúns puntos.
Debería identificar casos base axeitados que permitan que finalice a recursividade. Se non están presentes, a función pode seguir chamándose a si mesma para sempre.
En segundo lugar, segundo o escenario en cuestión, a selección do tipo de recursividade adecuado pode levar a solucións máis eficientes e elegantes. Tenta atopar o que funciona mellor para o problema na man. Cando traballes con grandes profundidades de recursión, teña en conta os perigos potenciais, como o desbordamento da pila.
Deixe unha resposta