Tot el que heu de saber sobre la recursió a Python

Aquest article us ajudarà a obtenir un coneixement detallat i complet sobre la recursió a Python. Com funciona? i quin és el seu propòsit?

En paraules simples, la recursió és una manera de resoldre el problema fent que una funció es digui a si mateixa, la paraula ' recursiu 'Prové del verb llatí' recidivar ”, Que vol dir refer alguna cosa. Això és el que fa la funció recursiva, refà el mateix una i altra vegada, és a dir, es recorda a si mateixa. En aquest article, aprendrem sobre la recursió a Python. A continuació es detallen els temes tractats en aquest bloc:



Què és la recursió a Python?

La recursió és el procés de determinar alguna cosa en termes d’ella mateixa. Sabem que a Python, qualsevol funció pot cridar qualsevol altra funció, una funció també es pot cridar a si mateixa. Aquests tipus de funcions que s’anomenen fins que no es compleix la condició determinada s’anomenen funcions recursives.



Recursion-in-Python

agafem uns quants exemples per veure com funciona, si se us dóna un enter positiu n, el factorial seria.



  • n! = n * (n-1) * (n-2), etc.
  • 2! = 2 * (2-1)
  • 1! = 1
  • 0! = 0
  • 4! = 4 * 3!
  • 3! = 3 * 2!
  • 2! = 2 * 1!

La substitució dels valors anteriors donarà lloc a la següent expressió

  • 4! = 4 * 3 * 2 * 1

Hem de definir una funció que permeti dir fact (n) que pren com a paràmetre un enter enter positiu o 0 i retorna l’enèsim factorial, com podem fer-ho mitjançant la recursió?

A veure, per fer-ho mitjançant recursivitat hem d’examinar la següent equació



  • n! = n. (n-1). (n-2) i hellip3.2.1

  • n! = n. (n-1) #podem tornar a escriure la declaració anterior tal com apareix en aquesta línia

  • Ara aquí si passem 2 com a paràmetre obtindrem:

    • 2! = 2.1! = 2

  • De la mateixa manera, si passem 1 obtindrem:

    • 1! = 1.0! = 1

  • Però si passem 0, es trenca

    • 0! = 0. (- 1) i aquí el factorial per a -1 no està definit, de manera que només funciona per a valors> 0

  • Per tant, hem d’escriure dos casos

    • 1. n! = n. (n-1) si n> = 1

    • 2. 1 si n = 0

Aquesta és una solució completa per a tots els enters positius i 0.

el millor ide de Java per Linux

Condició de finalització

Una funció recursiva ha de complir una condició important per acabar. En avançar cap a una condició en què el problema es pugui resoldre sense més recursivitat, una funció recursiva finalitzarà, minimitzant el problema en els sub-passos més petits. Una recursió pot acabar en un bucle infinit si la condició de finalització no es compleix a les trucades.

Condicions factorials:

  • factorial de n = n * (n-1) sempre que n sigui superior a 1.
  • 1 si n = 0

Convertirem les condicions factorials anteriors en codi python:

def fact (n): if n == 1: return n else: return n * fact (n-1)

Posem un exemple, diguem que volem trobar un factorial de 4:

fact (4) #this retornarà 4 * fact (3) i així fins a n == 1.
 Sortida: 24

S’utilitza tan sovint com a exemple de recursivitat per la seva simplicitat i claredat. Resoldre casos més petits d’un problema a cada pas que s’anomenava recursivitat en informàtica.

Límit de recursió de Python

En alguns idiomes, podeu crear un bucle recursiu infinit, però, a Python, hi ha un límit de recursió. Per comprovar el límit, executeu la següent funció des del mòdul sys. que donarà el límit de la recursió establert per a python.

importa sys sys.getrecursionlimit ()
 Sortida: 1000

També podeu canviar el límit mitjançant les funcionsrecreció del límit () del mòdul sys segons el vostre requisit. Ara creem una funció que es crida recursivament fins que supera el límit i comprova què passa:

def recursiu (): recursiu () si __nom__ == '__main__': recursiu ()

Si executeu el codi anterior, obtindreu una excepció en temps d'execució: RuntimeError: s'ha superat la profunditat màxima de recursió. Python impedeix crear una funció que acabi en un bucle recursiu sense fi.

Llistes d'aplanament amb recursivitat

Altres coses que podeu fer mitjançant la recursivitat, excepte els factorials, suposem que voleu crear-ne un únic a partir d'una llista que està imbricada, es pot fer mitjançant el codi següent:

def aplana (a_list, flat_list = none): si flat_list no és cap: flat_list = [] per a l'element d'una llista: if isinstance (item, list): aplana (item, flat_list) else: flat_list.append (item) return flat_list if __name__ == '__main__': imbricat = [1,2,3, [4,5], 6] x = aplanar (imbricat) imprimir (x)
 Sortida: [1,2,3,4,5,6]

L'execució del codi anterior donarà lloc a una llista única en lloc d'una llista sencera que conté una llista sencera que hem utilitzat com a entrada. També podeu fer el mateix utilitzant altres maneres, Python té una cosa anomenada itertools.chain (), podeu comprovar el codi utilitzat per crear una cadena de funcions (), és un enfocament diferent fer el mateix que nosaltres.

Avantatges de la recursivitat

  • El codi és net i elegant amb una funció recursiva.

  • Una tasca composta es pot desglossar en subproblemes més senzills mitjançant la recursivitat.

  • La generació de seqüències és més fàcil amb la recursió que no pas amb una iteració imbricada.

Desavantatges de la recursivitat

  • Seguir la lògica darrere de la funció recursiva pot ser difícil de vegades.

  • Les trucades recursives són costoses (ineficients), ja que ocupen molta memòria i temps.

  • Les funcions recursives són difícils de depurar.

En aquest article vam veure què és la recursivitat i com podem desenvolupar funcions recursives a partir de la declaració de problemes, com matemàticament es pot definir una afirmació de problema. Hem resolt un problema del factorial i hem descobert les condicions necessàries per trobar factorials a partir dels quals hem pogut convertir aquestes condicions en codi python, donant-vos la comprensió del funcionament de la recursió. Crec que és bo que Python tingui un límit incorporat per a la recursió per evitar que els desenvolupadors creïn funcions recursives mal construïdes. Una cosa important a tenir en compte és que la recursivitat és difícil de depurar, ja que la funció continua cridant-se a si mateixa.