Python rekursive funksjoner

Rekursive funksjoner er funksjoner som kaller seg i sin definisjon. Fordi en rekursiv funksjon kaller på seg til å utføre sin oppgave, det kan gjøre jobbene som inneholder identiske arbeid på flere dataobjekter lettere å konseptualisere, planlegge og skrive. Imidlertid kan rekursjon være systemkrevende eller ende opp overbelastning av systemet hvis rekursjon ikke stopper. Skrive rekursive funksjoner i Python er lik ved hjelp av rekursive funksjoner i andre programmeringsspråk, med de samme fordelene og fallgruver.

Eksempel Rekursjon

Rekursive funksjoner kaller seg som en del av deres definisjon. For eksempel:

def faktor (x):

. . . faktor (x)

Denne funksjonen vil fortsette å kalle seg frem til systemet ikke lenger kan holde mengden av funksjonskall laget (funksjonskall ligge i minnet som alle andre data). Men forenkler denne hvordan en rekursive funksjoner arbeider konseptuelt: En funksjon (faktor) kaller seg (faktor (x)) som en del av sin definisjon.

Base Cases

En rekursiv funksjon må ha det som kan kalles "basis tilfeller", eller forhold som forteller funksjonen til å stoppe sin rekursjon. Dette kan være en hvilken som helst tilstand at funksjonen kan ha oppfylt som en del av sin drift. Som et klassisk eksempel, finner fakultet funksjon fakultetet av et antall n (n !, eller n n-1 n-2... 0). Så fakultetet av tre vil beregne til 3 2 1 = 6. En programmerer kan bruke tallet 0 som base case av denne funksjonen:

hvis x == 0:

. . . returnere en

rekursjon

Dersom fakultetet funksjonen har nå en base case (x == 0), rekursjon vil stoppe ved denne tilstanden. Så ville det bare være et spørsmål om å bruke rekursjon til å utføre fakultetet drift:

ellers:

. . . returnere x * faktor (x-1)

Hvis x ikke lik 0, så rekursjon vil begynne / fortsette. Avkastningen uttalelsen vil kalle "faktor" og vent. Hver ny funksjon samtale vil gjøre det samme, ringer og vente til den siste funksjonen samtale (når x == 0) returnerer 1. Deretter vil hver forrige samtale ferdig avkastningen uttalelse (multiplisere den returnerte verdien fra "faktor" av x) til fakultetet er returnert.

Python Rekursjon

Rekursjon på alle språk kan ende opp i en uendelig løkke: Det er, en rekursiv struktur som aldri tar slutt før systemet stopper det på grunn av mangel på ressurser. Python stopper denne "uendelig" rekursjon på 1.000 samtaler (slik funksjon kan kalle seg i en 1000 eksempel lang rekursiv kjeden før Python stopper prosessen). Programmereren kan endre denne verdien gjennom systembiblioteker, som dette eksempelet:

import sys

sys.setrecursionlimit (2000)

Men på det punktet programmerere kan spørre seg selv om rekursjon er den beste løsningen på problemet.