Rekursion

Definition: ein Unterprogramm heißt rekursiv, wenn es sich selbst aufruft.

Beispiel: Verarbeitung von rekursiven Datenstrukturen

int size (Tree b) {
  if (b ist Blatt) { return 1; } 
  else { return 
    1 + size (links(b)) + size (rechts(b)); 
} }

Beispiel (John McCarthy): Berechne f(7); f(77); für

static int f (int x) {
  if (x > 100) {    return x - 10; } 
  else { return f (f (x + 11));  }
}