Antwoord.

Achtergrond:

Recursie wordt ondersteund in C sinds het ontstaan ervan – het past natuurlijk in de paradigma van de taal, waardoor compacte oplossingen mogelijk zijn, vooral voor taken met bomen, lijsten en complexe decompositie-algoritmen.

Probleem:

De belangrijkste risico's van het gebruik van recursie zijn overmatig stapelverbruik, de mogelijkheid van stapeloverloop (stack overflow) en een niet voor de hand liggend effect op de prestaties (in vergelijking met een cyclische implementatie). In C is er geen standaardmethode om automatisch de diepte van geneste aanroepen te controleren.

Oplossing:

Beoordeel vóór het gebruik van recursie het maximale mogelijke niveau van genestheid, gebruik indien mogelijk staartrecursie (voor optimalisatie door de compiler) en voeg bescherming tegen overflow toe, bijvoorbeeld een expliciete diepte-teller voor recursie. Een alternatieve methode is om recursieve aanroepen te vervangen door cycli voor eenvoudige taken.

Voorbeeldcode:

#include <stdio.h>
#define MAX_DEPTH 1000

int factorial(int n, int depth) {
    if (depth > MAX_DEPTH) {
        printf("Error: maximale recursiediepte overschreden!\n");
        return -1;
    }
    if (n == 0) return 1;
    return n * factorial(n - 1, depth + 1);
}

int main() {
    printf("%d\n", factorial(5, 0)); // 120
    return 0;
}

Belangrijkste kenmerken:

Er is geen garantie voor automatische beperking van de diepte van recursie
Recursie verbruikt stapel, die beperkt kan zijn
Staartrecursie kan door de compiler worden geoptimaliseerd, maar niet altijd

Vragen met een haakje.

Zal de stapel worden geleegd als binnen de recursieve functie een return wordt uitgevoerd voordat alle aanroepen zijn beëindigd?

Ja, de stapel wordt vrijgegeven bij het verlaten van de huidige functie. Er zullen geen "hangende" gegevens op de stapel blijven staan, zolang de stapel niet is overgelopen.

Kun je statische lokale variabelen binnen de body van een recursieve functie declareren, en wat gebeurt ermee?

Ja, zulke variabelen zijn gemeenschappelijk voor alle recursieve aanroepen, hun waarde blijft behouden tussen aanroepen, wat vaak tot fouten leidt als dit gedrag niet wordt meegenomen.

Beïnvloedt de C-compiler de diepte van de recursie en kan deze deze beperken?

De compiler beperkt recursie niet direct. De diepte van de recursie is beperkt door de grootte van de stapel van het besturingssysteem of externe factoren.

Typische fouten en anti-patronen

Onbeperkte recursie zonder dieptecontrole
Niet-geïnitialiseerde of statische lokale variabelen in de body van een recursieve functie
Gebruik van recursie waar een lus eenvoudiger en efficiënter is

Voorbeeld uit het leven

Er is een recursieve doorzoeking van een zoekboom geïmplementeerd zonder dieptebeperking:

Voordelen:

De code is beknopt, gemakkelijk te lezen

Nadelen:

Bij een grote diepte van de boom eindigde het programma met een stapeloverloopfout.

In de verbeterde versie is een diepte-teller ingevoerd en werd er overgestapt op een stapel-gebaseerde doorzoeking bij grote boomgroottes: