Python-rekursjon (rekursiv funksjon)

I denne opplæringen lærer du å lage en rekursiv funksjon (en funksjon som kaller seg selv).

Hva er rekursjon?

Rekursjon er prosessen med å definere noe i form av seg selv.

Et fysisk eksempel på verden ville være å plassere to parallelle speil mot hverandre. Ethvert objekt i mellom dem vil reflekteres rekursivt.

Python rekursiv funksjon

I Python vet vi at en funksjon kan kalle andre funksjoner. Det er til og med mulig for funksjonen å kalle seg selv. Disse typene konstruksjon blir betegnet som rekursive funksjoner.

Følgende bilde viser hvordan en rekursiv funksjon kalles recurse.

Rekursiv funksjon i Python

Følgende er et eksempel på en rekursiv funksjon for å finne faktoren til et heltall.

Faktor av et tall er produktet av alle heltallene fra 1 til det tallet. For eksempel er faktoren 6 (betegnet som 6!) 1 * 2 * 3 * 4 * 5 * 6 = 720.

Eksempel på en rekursiv funksjon

 def factorial(x): """This is a recursive function to find the factorial of an integer""" if x == 1: return 1 else: return (x * factorial(x-1)) num = 3 print("The factorial of", num, "is", factorial(num))

Produksjon

 Fabrikken til 3 er 6

I eksemplet ovenfor factorial()er en rekursiv funksjon som den kaller seg selv.

Når vi kaller denne funksjonen med et positivt heltall, vil den rekursivt kalle seg selv ved å redusere antallet.

Hver funksjon multipliserer tallet med faktoren for tallet under den til den er lik en. Denne rekursive samtalen kan forklares i trinnene nedenfor.

 fabrikk (3) # første samtale med 3 3 * fabrikk (2) # 2. samtale med 2 3 * 2 * fabrikk (1) # 3. samtale med 1 3 * 2 * 1 # retur fra 3. samtale som nummer = 1 3 * 2 # retur fra 2. samtale 6 # retur fra første samtale

La oss se på et bilde som viser en trinnvis prosess av hva som skjer:

Arbeider med en rekursiv faktorfunksjon

Rekursjonen slutter når tallet reduseres til 1. Dette kalles basistilstanden.

Hver rekursiv funksjon må ha en basistilstand som stopper rekursjonen, ellers kaller funksjonen seg uendelig.

Python-tolken begrenser dybden av rekursjon for å unngå uendelige rekursjoner, noe som resulterer i stabeloverløp.

Som standard er maksimal dybde på rekursjon 1000. Hvis grensen krysses, resulterer den i RecursionError. La oss se på en slik tilstand.

 def recursor(): recursor() recursor()

Produksjon

 Sporing (siste samtale sist): Fil "", linje 3, i fil "", linje 2, i en fil "", linje 2, i en fil "", linje 2, i en (Forrige linje gjentatt 996 ganger til ) RecursionError: maksimal rekursjonsdybde overskredet

Fordeler med rekursjon

  1. Rekursive funksjoner gjør at koden ser ren og elegant ut.
  2. En kompleks oppgave kan brytes ned i enklere delproblemer ved hjelp av rekursjon.
  3. Sekvensgenerering er lettere med rekursjon enn å bruke noen nestede iterasjoner.

Ulemper ved rekursjon

  1. Noen ganger er logikken bak rekursjon vanskelig å følge gjennom.
  2. Rekursive samtaler er dyre (ineffektive) da de tar mye minne og tid.
  3. Rekursive funksjoner er vanskelig å feilsøke.

Interessante artikler...