Jusqu'à présent, nous avons surtout utilisé la méthode main() d'une classe principale Exo: cette méthode permet de décrire le code qui devra être exécuté lorsqu'un appel à java Exo sera lancé. La machine virtuelle charge alors le bytecode de la classe Exo et exécute toutes les instructions décrites dans la méthode main().
Pour des raisons qui peuvent paraître obscures jusqu'à présent, cette méthode doit avoir exactement le profil public static void main(String[] args):
Ces instructions contenues dans la fonction main peuvent être des déclarations de variables, des initialisations ou encore des structures de contrôle (conditionnelles, boucles, aiguillages, etc.). Mais elles peuvent aussi être des appels à d'autres fonctions.
Dans certains cas, il est possible qu'une fonction s'appelle elle-même dans le corps de sa définition. Cela correspond souvent à des définitions mathématiques récursives. On dit également que la programmation de ces fonctions est récursive. Comme dans chaque récursion, il est indispensable d'avoir un ou plusieurs cas de terminaison de la récursion, et que les appels récursifs fassent converger les arguments de la fonction vers ces cas de terminaison.
Un exemple classique de fonction récursive est la factorielle dont la définition mathématique est la suivante (pour des entiers positifs):
fact(n) = 1 si n = 0
fact(n) = n * fact(n-1) sinon
Sa programmation sous la forme d'une fonction récursive est immédiate,
et peut s'utiliser comme ceci:
public class Recursion {
public static int fact(int n) {
if (n == 0)
return 1;
else
return n * fact(n-1);
}
public static void main(String[] args) {
int i = Integer.parseInt(args[0]);
if (i>=0) {
int iFact = fact(i);
System.out.println(iFact);
}
}
}
Que se passe t-il alors lors d'un appel à fact(i) si i vaut 3? L'appel fact(3) teste si 3 est égal à 0. Comme ce n'est pas le cas, elle doit empiler la valeur 3 sur la pile d'appel, qui sera à multiplier avec le résultat de fact(2). Pour connaître cette valeur, il lui faut empiler à nouveau la valeur 2, à multiplier par le résultat de fact(1), etc. jusqu'à fact(0). Dans ce dernier cas, le test (n == 0) est vrai et la valeur de retour est 1. Il ne reste plus qu'à multiplier ce 1 avec la valeur sur le dessus de la pile (1 également). Le résultat est donc 1, à multiplier par la valeur sur le dessus de la pile qui est 2. Le résultat est 2, à multiplier par la valeur sur le dessus de la pile qui est 3. Le résultat final est 6.
Le jeu des tours de hanoi comprend 3 tours, nommées A, B et C. On considère qu'un ensemble de disques (n=5 dans l'exemple) sont enfilés sur une de ces tours, disons A. L'objectif du jeu est de se retrouver avec tous les disques empilés sur la tour C en respectant les contraintes suivantes:
