Hva er rekursjon?

Rekursjon er prosessen med å definere noe i form av seg selv.et fysisk verdenseksempel ville være å plassere to parallelle speil mot hverandre. Ethvert objekt i mellom dem ville bli reflektert rekursivt.

Python Rekursiv Funksjon

I Python vet vi at en funksjon kan kalle andre funksjoner. Det er også mulig for funksjonen å kalle seg selv. Disse typer konstruksjoner kalles rekursive funksjoner.

følgende bilde viser arbeidet med en rekursiv funksjon kalt recurse.

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

Factorial av et tall er produktet av alle heltallene fra 1 til det tallet. For eksempel, faktorialet av 6 (betegnet som 6!) er 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 = 3print("The factorial of", num, "is", factorial(num))

Output

The factorial of 3 is 6

i eksemplet ovenfor erfactorial() en rekursiv funksjon som den kaller seg selv.

når vi kaller denne funksjonen med et positivt heltall, vil det rekursivt kalle seg ved å redusere tallet.

hver funksjon multipliserer tallet med faktorialet til tallet under det til det er lik en. Dette rekursive anropet kan forklares i de følgende trinnene.

factorial(3) # 1st call with 33 * factorial(2) # 2nd call with 23 * 2 * factorial(1) # 3rd call with 13 * 2 * 1 # return from 3rd call as number=13 * 2 # return from 2nd call6 # return from 1st call

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

vår rekursjon slutter når tallet reduseres til 1. Dette kalles grunnbetingelsen.

hver rekursiv funksjon må ha en grunnbetingelse 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 er krysset, resulterer den i RecursionError. La oss se på en slik tilstand.

def recursor(): recursor()recursor()

Utgang

Traceback (most recent call last): File "<string>", line 3, in <module> File "<string>", line 2, in a File "<string>", line 2, in a File "<string>", line 2, in a RecursionError: maximum recursion depth exceeded

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 nestet iterasjon.

Ulemper Ved Rekursjon

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