Linux C Programmeren Handleiding Deel 18: Recursieve functies

Ongeacht de programmeertaal die je gebruikt, naarmate je meer en meer gaat coderen, leer je concepten die je code kernachtig en gemakkelijk leesbaar/begrijpbaar maken. Ook in de C taal zijn er verschillende van zulke concepten. Eén ervan is ‘recursieve functies,’ die we hier in dit artikel zullen bespreken.

Een recursieve functie is een functie die zichzelf aanroept. De aanroep kan direct vanuit het lichaam van de functie gebeuren, of indirect vanuit een andere functie die door de functie in kwestie aangeroepen wordt.

Hier volgt een voorbeeld van directe recursie:

int func (int a)
{
//statements

func(a-1);

// statements

return 0;
}

En hier volgt een voorbeeld van indirecte recursie:

int func (int a)
{
//statements

func_new(a);

// statements

return 0;
}

int func_new(int b)
{
//statements

func(b-1);

//statementsur

return 0;
}

Zoals in het begin al gezegd, helpt recursie je om compacte code te krijgen, een code die niet alleen gemakkelijk te schrijven is, maar ook gemakkelijk te begrijpen en te beoordelen. Laten we een voorbeeld nemen om dit voordeel duidelijker te maken.

Je zult allemaal wel gehoord hebben van het concept factorial. Voor wie het niet weet, is factorie het resultaat dat je krijgt als je een geheel getal vermenigvuldigt met alle positieve gehele getallen die er minder van zijn. Bijvoorbeeld, de factorial van 5 is 5x4x3x2x1, wat gelijk is aan 120.

Hier is een eenvoudige code om de factorie van een getal te vinden:

#include <stdio.h>

int main()
{
int a = 0, i = 0, fact = 1;
printf("Enter a number: ");

scanf("%d", &a);

for(i=1; i<=a; i++)
{
fact = fact * i;

}
printf("Factorial of the number is: %d ", fact);
return 0;
}

Merk op dat deze code alleen is om je te laten weten hoe de factorie van een getal berekend kan worden met behulp van een C programma. Het programma houdt geen rekening met hoekgevallen die de nauwkeurigheid van het resultaat dat het geeft kunnen beïnvloeden.

Dit is dus een van de vele manieren waarop je de factoriaal van een getal kunt berekenen zonder een recursieve functie te gebruiken. Laten we nu eens een stukje code bekijken dat recursie gebruikt om een factorie te berekenen.

#include <stdio.h>

int factorial (int b)
{
if(!b)
return 1;

return (b * factorial(b-1));
}

int main()
{
int a = 0, fact = 1;
printf("Enter a number: ");

scanf("%d", &a);

fact = factorial(a);

printf("Factorial of the number is: %d ", fact);
return 0;
}

Zo zie je dat de functie ‘factorial’ die eigenlijk de factorial berekent, heel compact is. En als je goed oplet, is het ook heel gemakkelijk te begrijpen.

Voor wie niet weet wat er gebeurt: de waarde die de gebruiker heeft ingevoerd, zeg 5, wordt doorgegeven aan de ‘factorial’ functie als die voor het eerst wordt aangeroepen vanuit de ‘main’ functie. Binnenin de ‘factorial’ functie wordt gecontroleerd of de invoerwaarde nul is, wat niet waar is als de functie de eerste keer wordt aangeroepen met invoerwaarde ‘5’.

Dan bevat de return-statement een uitdrukking die 5 vermenigvuldigt met de return-waarde van ‘factorial(4)’. Dus nu voert de ‘factorial’ functie opnieuw uit, en we komen bij de volgende uitdrukking: return (4 * factorial(3)). En dan herhalen deze stappen zich weer.

Als je dus ruim kijkt, zie je hier hoe deze functie-aanroepen op elkaar gestapeld worden:

  • 5 * factorial(4)
  • 4 * factorial(3)
  • 3 * factorial(2)
  • 2 * factorial (1)
  • 1 * factorial (0)

Als nu factorial(0) wordt uitgevoerd, wordt de ‘if’ voorwaarde in de ‘factorial’ functie waar, en de waarde ‘1’ wordt teruggegeven. Zo voltooien nu de hierboven opgesomde aanroepen (vergelijk de laatste ingang in de vorige lijst met de eerste ingang in deze lijst, enzovoort):

  • 1 * 1
  • 2 * (1*1)
  • 3 * (2*(1*1))
  • 4 * (3*(2*(1*1)))
  • 5 * (4 * (3*(2*(1*1))))

Wat in feite 5 * 4 * 3 * 2 * 1 is, wat op zijn beurt 120 is, de factorie van 5.

Dit is dus hoe recursieve functies werken. Hoewel er geen twijfel bestaat over de recursieve functie voordelen die we tot nu toe opsomden, zijn er ook enkele nadelen.

Bijvoorbeeld, in ons voorbeeld hierboven wachtten, tot de aanroep ‘factorial(0)’ voltooid was, alle voorgaande ‘factorial’ aanroepen tot de functieverwerking voltooid was. En dan hebben we het nog niet eens over het feit dat automatische of lokale variabelen geheugen innemen voor elke recursieve aanroep die gedaan wordt.

Er is dus effectief geen besparing van opslagruimte als je recursie gebruikt. Plus, er is ook geen garantie dat je code sneller wordt in uitvoering. Het echte voordeel van een recursieve functie is wanneer je met gegevensstructuren te maken hebt, waarover later meer in het kader van deze doorlopende C leerreeks.

Conclusie

Concluderend, hoewel je recursieve functies misschien niet vaak gebruikt in je dagelijkse codeertaken, is het toch een belangrijk concept waarvan je je bewust moet zijn. Probeer het voorbeeld dat we hier noemden uit, en pas het aan om het concept van recursieve functies nog beter te begrijpen.