Alguna vegada t'has vist atrapat en un cicle aparentment inacabable on un problema segueix ramificant-se en fragments més petits?
Si és així, potser us heu trobat amb l'apassionant món de la recursivitat. Tot i que pot semblar difícil d'entendre, no us preocupeu! En aquesta publicació, farem un viatge interessant per conèixer els tipus de recursivitat.
Així que s'ha de posar el cinturó mentre explorem nombrosos enfocaments recursius. Prepareu-vos per entrar al fascinant regne de la recursivitat i observeu la seva notable capacitat per resoldre problemes complicats.
Què són exactament les recursències?
En paraules bàsiques, la recursivitat és una tècnica de programació potent que inclou una funció que es crida a si mateixa durant l'execució. És com mirar-se en un mirall i veure una imatge dins d'una imatge, donant lloc a un cicle autoreferencial.
Podem abordar grans problemes mitjançant la recursivitat dividint-los en subproblemes més petits i més manejables.
És semblant a muntar un trencaclosques, on una peça s'enllaça amb altres parts per produir una imatge completa. La recursivitat ens permet resoldre problemes d'una manera elegant i eficient repetint el mateix conjunt d'instruccions amb diverses entrades.
1-Recursió directa
La recursivitat directa és el tipus més bàsic de recursivitat, en què una funció s'anomena directament. Implica dividir un problema problemàtic en subproblemes més petits fins que s'aconsegueix un cas base, que condueix a la terminació.
La funció recursiva s'anomena amb diverses entrades, permetent que es repeteixi l'execució del mateix conjunt d'instruccions. Cada invocació es basa en l'anterior, acostant-se progressivament al cas base que fa que finalitzi la recursió.
Comprovem aquest exemple.
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1)
countdown(5)
sortida:
5
4
3
2
1
2-Recursió indirecta
La recursivitat indirecta afegeix un gir intrigant al camí recursiu. A diferència de la recursivitat directa, que implica una funció que s'anomena explícitament a si mateixa, la recursivitat indirecta inclou una cadena de trucades de funcions.
Una funció en crida una altra, que després pot cridar la funció original o qualsevol altra funció que finalment torni a l'original. Aquesta xarxa interconnectada de trucades de funcions produeix un ball apassionant en què diverses funcions col·laboren per solucionar un problema.
Exemple:
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)
sortida:
A: 3
B: 2
A: 1
3-Recursió lineal
Penseu en un viatge per una ruta recta, un pas a la vegada, fins que arribeu al vostre objectiu. Aquesta tècnica seqüencial s'incorpora per recursivitat lineal, en la qual una funció realitza una única crida recursiva en cada iteració de funció.
Amb cada trucada recursiva, el procés recursiu s'acosta a un cas base reduint la mida del problema. Procedeix d'una manera clara i lineal, resolent subproblemes un a un fins que s'arriba a la resposta definitiva.
Exemple:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
result = factorial(5)
print(result)
sortida:
120
4-Recursió d'arbres
Quan una funció es ramifica en diverses crides recursives, entrem al món de la recursivitat en arbre. Una funció en recursivitat d'arbre genera moltes trucades recursives, cadascuna de les quals resol un subproblema separat, tal com ho fan les branques d'un arbre.
Aquesta estructura de ramificació permet la investigació simultània de diverses rutes, desglossant eficaçment els problemes complicats en components més petits i interrelacionats.
Exemple:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
result = fibonacci(6)
print(result)
sortida:
8
5-Recursió niuada
La recursivitat niuada afegeix un emocionant grau de complexitat a l'univers recursiu. En aquesta forma de recursivitat, una funció incorpora una crida recursiva com a argument dins d'una altra crida recursiva.
La crida recursiva interna actua sobre un valor que depèn de la crida recursiva externa. La complexitat creix amb cada invocació imbricada, culminant amb un patró intrigant de trucades recursives imbricades.
Exemple:
def nested_recursion(n):
if n > 100:
return n - 10
return nested_recursion(nested_recursion(n + 11))
result = nested_recursion(95)
print(result)
Resultat:
91
6-Recursió de la cua
La recursivitat de la cua és una tècnica d'optimització per a algorismes recursius que poden millorar el seu rendiment. La crida recursiva apareix com l'acció final d'una funció amb recursivitat de cua, fent.
Com que no hi ha operacions pendents després de la crida recursiva, el compilador o intèrpret pot simplificar la recursivitat substituint-la per un simple salt.
Aquest enfocament d'optimització, conegut com a optimització de la trucada de cua, redueix el requisit de cada trucada recursiva per conservar un marc de pila, donant com a resultat una velocitat millorada i un menor ús de memòria.
Exemple:
def tail_factorial(n, result=1):
if n == 0:
return result
return tail_factorial(n - 1, result * n)
result = tail_factorial(5)
print(result)
Sortida:
120
7-Recursió sense cua
A diferència de la recursivitat de la cua, la recursivitat sense cua implica activitats addicionals realitzades després de la crida recursiva dins d'una funció. Abans que es puguin realitzar més accions, cada trucada recursiva s'ha de completar i tornar.
Com a conseqüència, fins que s'arribi al cas base i s'acabi la recursivitat, es manté una pila d'operacions pendents. La recursivitat sense cua sovint utilitza més memòria i és menys eficient que la recursivitat amb cua, però segueix sent una eina útil per abordar una varietat de problemes.
Exemple:
def non_tail_sum(n):
if n == 0:
return 0
return n + non_tail_sum(n - 1)
result = non_tail_sum(5)
print(result)
sortida:
15
Embolicar
La recursivitat és un concepte intrigant en la programació. Ens permet abordar problemes complicats d'una manera recursiva i autoreferencial.
Ofereix un mètode diferent per pensar i resoldre problemes, dividint-los en fragments més petits i més manejables. Quan es treballa amb recursivitat, però, és fonamental utilitzar prestar atenció a alguns punts.
Hauríeu d'identificar casos bàsics adequats que permetin acabar la recursivitat. Si no hi són presents, la funció pot continuar anomenant-se per sempre.
En segon lloc, segons l'escenari en qüestió, seleccionar el tipus de recursivitat adequat pot conduir a solucions més eficients i elegants. Intenta trobar el que funciona millor per al problema de la mà. Quan treballeu amb grans profunditats de recursió, tingueu en compte els perills potencials, com ara el desbordament de la pila.
Deixa un comentari