Recursieve functies in Python begrijpen

Als professionele programmeur moet je uitstekend zijn in de basiszaken zoals variabelen, voorwaardelijke statements, datatypes, access specifiers, functieroepingen, scopes, enzovoort. Ongeacht wat voor programma je schrijft — of het nu middleware is, iets voor webontwikkeling of data science — dit zijn enkele van de meest fundamentele dingen die je als programmeur grondig moet kennen. Je bent eerst programmeur, en pas daarna Data Scientist, Webdeveloper, Machine Learning Engineer, enzovoort.

Een van die fundamentele concepten is recursie, en het is ontzettend belangrijk om te kennen wanneer je functies van een bepaald type schrijft. Je weet misschien al: "Het heet recursie wanneer een functie zichzelf aanroept." Maar wat gebeurt er onder de motorkap? Hoe wordt het fysieke geheugen beïnvloed door recursie? Kun je elke andere functie omzetten in een recursieve functie? In deze tutorial vind je antwoorden op deze basisvragen.

Anatomie van een recursieve functie:

Je bent de term recursie waarschijnlijk al tegengekomen in je opleiding Informatica of Information Technology. In deze sectie kijk je die concepten opnieuw na, maar dan op een interessante manier. Laten we beginnen.

Terug naar de definitie van recursie: "Het heet recursie wanneer een functie zichzelf aanroept". Laten we een voorbeeld nemen om deze definitie te ondersteunen:

void A(n){
    if(n>=1){
        A(n-1);
        print(n);
    }
}

Je ziet dat de functie A() zichzelf aanroept. Dit is een voorbeeld van recursie, en A() is een recursieve functie.

Laten we nu wat basisprincipes van een recursieve functie bestuderen.

Basis van een recursieve functie:

Een recursieve functie moet de volgende twee eigenschappen bevatten:

• Een recursievergelijking
• Een stopvoorwaarde

Neem de bovenstaande code om deze punten te begrijpen. Duidelijk heeft de functie een specifieke recursierelatie:

$n\le 1$ is de stopvoorwaarde / ankerconditie / basisgeval, en als daaraan is voldaan, stopt de recursie. Het opgeven van deze voorwaarde is essentieel. Anders belandt de functie in een oneindige lus.

(Let op: de bovenstaande code volgt geen specifieke programmeertaal. Het belangrijkste doel hier is om een voorbeeld van een recursieve functie te laten zien.)

Je denkt nu misschien: waarom zou iemand in hemelsnaam een recursieve functie schrijven als er betere alternatieven zijn? Ja, soms is het lastig om een recursie te volgen, maar als je er eenmaal aan gewend bent, zul je recursie mooi vinden qua leesbaarheid en variabelengebruik. Recursie heeft geen extra variabelen nodig om te kunnen draaien, maar vereist wel een goede stopvoorwaarde om te eindigen. Vaak is het lastig om de juiste stopvoorwaarde te vinden. Maar goed, "Oefening baart kunst". Later in deze tutorial zie je hoe elegant en kort een programma kan zijn als het met recursie wordt geïmplementeerd in plaats van op de conventionele manier. Nu ga je verder met de geheugenrepresentatie van een recursieve functie.

Geheugenrepresentatie van een recursieve functie:

In deze sectie bestudeer je hoe recursieve functies fundamenteel in het geheugen worden weergegeven met behulp van bomen en stacks. Neem de volgende recursieve functie A() om dit te begrijpen:

void A(n){
    if(n>=1){
        A(n-1);
        print(n);
    }
}

Eerst begrijp je de geheugenrepresentatie met bomen. Het klinkt misschien lastig, maar het is eigenlijk vrij eenvoudig. Als je elke functieroep in een boomstructuur zou tekenen, hoe zou dat eruitzien?

Zoiets als het volgende?

Een paar opmerkingen hierbij:

• De functie wordt aangeroepen met A(3) en daarvoor worden hier 4 (3+1) functieroepen gedaan. Algemeen geldt: als A(n) wordt aangeroepen, zijn er in totaal (n+1) functieroepen nodig.
• P()-aanroepen zijn de prints die door print(n) worden geproduceerd.
• De functie stopt bij de aanroep A(0) omdat de if-statement (na de aanroep A(0)) n < 1 krijgt, wat ervoor zorgt dat de functie beëindigt.

Je zag eerst deze boomrepresentatie, omdat je die nodig hebt om een recursieve functie op een stack weer te geven. Dat zie je nu.

(Een stack is een datastructuur die het last-in-first-out-principe (LIFO) volgt)

Voor de stackrepresentatie moet je de boom doorlopen van boven naar beneden en van links naar rechts. De volgende afbeelding maakt dit duidelijk.

Interpreteer dit vreemd uitziende ding (boom). Onthoud dat een stack twee operaties heeft: 1. Push, waarmee je een element op de stack plaatst, en 2. Pop, waarmee je een element van de stack haalt.

Nu begin je de boomtraversal van boven naar beneden en van links naar rechts:

• Telkens wanneer je een functieroep ziet, push je die op de stack.
• Als je een print()/P()-aanroep ziet, print je simpelweg het bijbehorende element.

De volgende elementen komen op de stack als resultaat van de boomtraversal van A(3) naar A(0) in enkel de top-down-richting:

Nu start je de tweede helft van de boomtraversal, dus de links-rechts-volgorde. Telkens wanneer je een functieroep voor de tweede keer ziet, pop je die. Verrassend genoeg is het eerste element van de stack (A(0)) dat eraf gepopt wordt, het laatste dat op de stack is gekomen (LIFO, weet je nog?). Onderweg kom je drie P()-aanroepen tegen — P(1), P(2) en P(3). Je print deze in de volgorde waarin ze tijdens de traversal verschijnen. De volgorde wordt:

Als je klaar bent met de traversal, is de stack volledig leeg. Om de pop-operatie nog beter te begrijpen, zie je hier een afbeelding van de stack nadat alles is gepopt.

Je zag hoe je een eenvoudige recursieve functie op het geheugen kunt weergeven met een boom en een stack. Nu zie je hoe je een recursie kunt traceren.

Een recursie traceren:

In deze sectie leer je hoe je een recursie systematisch kunt traceren. Bekijk de volgende recursieve functie:

void A(n){
    if(n>0){
        print(n-1);
        A(n-1);
    }
}

Een cruciaal punt hier is dat telkens wanneer een functie wordt aangeroepen, er in het geheugen een activatierecord wordt aangemaakt met de lokale variabelen van die functie en een instructiepointer (die aangeeft welke taak als volgende moet worden uitgevoerd wanneer de aanroep naar die functie terugkeert). Stel dat een functie main() de bovenstaande functie A() aanroept als A(3). Nummer de regels van A() vanaf de if-statement voor beter begrip:

void A(n){
    1. if(n>0)
    2. {
        3. print(n-1);
        4. A(n-1);
    5. }
}

De activatierecords zien er als volgt uit:

Zoals eerder vermeld hebben functies hun eigen kopieën van de lokale variabelen en de instructiepointers (in dit geval het regelnummer). Na A(0) zal de functie A() beëindigen en vindt het poppen plaats. Merk op dat hier een horizontale stack wordt gebruikt, die precies hetzelfde is als de stacks die je eerder in de tutorial zag. Terwijl de records op de stack worden gepusht, vinden de prints ook plaats en worden de volgende elementen geprint:

Instructiepointers zijn hier belangrijk, omdat in een recursieve functie de controle vaak teruggaat naar dezelfde functie maar met een andere variabelewaarde. Om alles synchroon te houden, helpen deze pointers echt. Je kunt exact dit proces volgen om een recursie te traceren met behulp van een boomrepresentatie.

Nu bestudeer je hoe je een ruimte-tijd-analyse van een recursieve functie uitvoert.

Ruimte-tijd-analyse van een recursieve functie:

DataCamp heeft een uitstekend artikel over Asymptotische analyse in Python, en het is aan te raden dat je dat bekijkt voordat je deze sectie leest. Laten we snel herhalen wat wordt bedoeld met ruimte- en tijdanalyses van een functie (ook wel ruimtecomplexiteit en tijdcomplexiteit genoemd):

Voor een gegeven input moet een functie een bepaald output opleveren. Hoeveel tijd kost het de functie om dat te doen? De maat tijdcomplexiteit benadert deze tijd en wordt ook wel de runtime van de functie genoemd. Op vergelijkbare wijze benadert de ruimtecomplexiteit de ruimte- (geheugen-) vereisten van een functie, d.w.z. voor een gegeven input. Maar waarom zijn deze überhaupt nodig?

• In plaats van een functie uit te voeren op inputs met verschillende groottes, kun je gemakkelijk benaderen hoe een functie zich gedraagt op verschillende inputs met uiteenlopende groottes.
• Als je twee functies hebt die hetzelfde doel bereiken, welke kies je dan? Welke maatstaven neem je mee in je beslissing? Precies. Je vergelijkt ze door hun ruimte- en tijdcomplexiteiten te analyseren en te zien welke beter presteert.

Laten we nu een eenvoudige recursieve functie nemen en de ruimte- en tijdcomplexiteit analyseren.

void A(n){
    if(n>1) // Anchor condition
    {
       return A(n-1);
    }
}

Laten we eerst de tijdcomplexiteit analyseren. Neem aan dat de totale tijd die de bovenstaande functie A() kost $T(n)$ is. Nu is $T(n)$ de som van de tijd voor de vergelijking of n groter is dan 1 en de tijd om A(n-1) uit te voeren. Dus, $T(n)$ kan worden uitgedrukt als —

1 is de tijd voor de vergelijking (je kunt daar elke constante nemen). Wat is nu de tijd (in termen van $T(n)$) voor het uitvoeren van A(n-1)?

Op dezelfde manier,

enzovoort.

Als je goed naar de vergelijkingen kijkt, zijn ze allemaal verbonden. Toch? Als je ze achtereenvolgens substitueert, krijg je —

$T(n)$ = 1 + (1 + $T(n-2)$) = 2 + $T(n-2)$ = 3 + $T(n-3)$ = .... = k + $T(n-k)$ (na het draaien van de functie voor k termen)

Nu moet je bepalen op welk punt de functie gaat stoppen. Volgens de gegeven ankerconditie kun je schrijven —

Neem aan dat de functie na k termen stopt. Dan moet het zo zijn dat —

$n - k = 1 => k = n - 1$

Vervang nu de waarde van k (= n - 1) in $T(n) = k + T(n-k)$:

$T(n) = (n-1) + T(n-(n-1))$
$=> T(n) = (n-1) + T(1)$
$=> T(n) = n-1 + 1 = n$ // Voor T(1) is alleen een vergelijking nodig

Volgens de regels van de asymptotische analyse kan $T(n) = n$ worden herschreven als $T(n) = \mathcal{O}(n)$. Dit betekent dat de (worstcase) tijdcomplexiteit van de functie $\mathcal{O}(n)$ is.

Neem hier gerust even de tijd om elke stap zorgvuldig te bekijken. Het is sterk aan te raden dit met pen en papier te doen, zodat je alles goed begrijpt.

De ruimtecomplexiteit van de functie is eenvoudig. De functie draait in het geheugen en gebruikt geen extra variabelen. Je kunt dus concluderen dat de ruimtecomplexiteit van de functie $\mathcal{O}(n)$ is.

Nu ga je alles samenbrengen en een eenvoudige recursieve functie in Python implementeren.

Een eenvoudige recursieve functie in Python implementeren:

Je schrijft een recursieve functie om de faculteit van een gegeven getal te bepalen. Vervolgens schrijf je een iteratieve versie van dezelfde functie. Laten we beginnen.

# Recursive function factorial_recursion()

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

# Call the function

num = 7
print("The factorial of ",num," is ",factorial_recursion(num))

The factorial of  7  is  5040

Weet je nog de twee belangrijkste ingrediënten voor het schrijven van een recursieve functie?

• Recursievergelijking
• Stopvoorwaarde

In dit geval kan de recursierelatie zijn —

$f(n) = n!$
$f(n) = n * f(n-1)$ enzovoort.

De stopvoorwaarde is wanneer n gelijk is aan 1.

Eenvoudig, toch?

Nu implementeer je de iteratieve versie van dezelfde functie.

def factorial_iterative(num):
    factorial = 1
    if num < 0:
        print("Sorry, factorial does not exist for negative numbers")
    elif num == 0:
        print("The factorial of 0 is 1")
    else:
        for i in range(1,num + 1):
           factorial = factorial*i
        print("The factorial of",num,"is",factorial)

factorial_iterative(7)

The factorial of 7 is 5040

Je ziet duidelijk het verschil tussen de twee versies. De recursieve versie is veel eleganter dan de iteratieve versie. Toch?

Gefeliciteerd!

Je bent tot het einde gekomen. In deze tutorial heb je recursieve functies uitgebreid bestudeerd. Van de absolute basis tot het analyseren van de ruimte- en tijdcomplexiteit van een recursieve functie: je hebt het allemaal behandeld. Je zag ook hoe recursie nuttig kan zijn voor het oplossen van problemen met een bepaald kenmerk. Je zou nu in staat moeten zijn om problemen (met een recursievergelijking en een stopvoorwaarde) met recursie op te lossen. Misschien wil je het probleem van het vinden van Fibonaccigetallen binnen een bereik met recursie oplossen.

Ik raad je aan om een paar klassieke problemen zoals binaire zoekopdracht, mergesort, de Torens van Hanoi, enz. met recursie op te lossen en ook een ruimte-tijd-analyse uit te voeren. Dit zal je zeker een betere programmeur maken.

Voor een introductie zijn de onderwerpen die je hebt behandeld voldoende. Maar als je meer over recursie wilt leren, bezoek dan zeker de volgende links:

• Recursion and Dictionaries door Prof. Grimson
• Dynamisch programmeren om de prestaties van recursieve functies te optimaliseren

Wil je meer leren over Python? Volg dan DataCamp’s gratis cursus Intro to Python for Data Science.