Définitions récursives

Une définition de fonction est récursive si son corps contient une expression d'invocation d'elle-même, dite invocation récursive . Les définitions récursives permettent souvent de transcrire de façon quasiment littérale certaines définitions mathématiques, dites récurrentes. Ainsi la transcription de l'identité

33#33

donne immédiatement la définition récursive suivante :

package exemples;

class Récursion {
  static int sommerEntiers(int m) {
    return (m <= 0) ? 0 : sommerEntiers(m-1) + m;
                       // invocation récursive
  }
  public static void main(String[] args) {
    System.out.println("somme de 1 à 3 = " + sommerEntiers(3));  
                       // --> 6
  }
}

Le mécanisme d'invocation des fonctions s'applique en particulier aux fonctions définies récursivement. Par exemple, l'invocation sommerEntiers(3) dans le corps de main provoque la suite d'invocations :

34#34

et la suite de retours, qui retourne finalement 6 à main(...) :

35#35

L'évolution de la pile pendant cette invocation est la suivante :

36#36