CKTIS / Java
Recursie en de aanroepstack
Recursie en de aanroepstack: Recursie ontstaat wanneer een methode zichzelf direct of indirect aanroept; elke aanroep heeft een stackframe, dus zijn een basisgeval en voortgang nodig.
Versie: Java SE 21 (JLS and Java SE API); examples verified on the repository Java runtime
Syntax
recursionRecursie ontstaat wanneer een methode zichzelf direct of indirect aanroept; elke aanroep heeft een stackframe, dus zijn een basisgeval en voortgang nodig.
Gebruik haar voor begrensde bomen en verdeel-en-heers; vervang een diepe lineaire doorloop door iteratie met Deque.
Java garandeert geen tail-call-optimalisatie, zodat correcte maar diepe recursie met StackOverflowError kan eindigen.
Lege invoer moet het basisgeval bereiken en een cyclische graaf heeft een visited-verzameling nodig om te eindigen.
Twee basisgevallen stoppen de aanroepen: factorial(5) schrijft 120 en de recursieve Euclidische gcd(48,18) schrijft 6.
Voorbeelden
public class Main {
static int factorial(int n) {
return n <= 1 ? 1 : n * factorial(n - 1);
}
static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
public static void main(String[] args) {
System.out.println(factorial(5));
System.out.println(gcd(48, 18));
}
}
Resultaat
120 6
Twee basisgevallen stoppen de aanroepen: factorial(5) schrijft 120 en de recursieve Euclidische gcd(48,18) schrijft 6.