/* Auteur: Nicolas JANEY          */
/* nicolas.janey@univ-fcomte.fr   */
/* Avril 2005                     */

public class NombreOccurencesRecursiveEnConsole {

  /* Fonction de tri a bulle                              */
  /* t : tableau a trier                                  */

  public static void triBulle(int [] t) {
    boolean stop = false;
    int ind = 0;
    while ( !stop ) {
      stop = true;
      for ( int i = 0 ; i < t.length-1-ind ; i++ )
        if ( t[i] > t[i+1] ) {
          stop = false;
          int v = t[i];
          t[i] = t[i+1];
          t[i+1] = v; }
      ind++; }
  }

  /* Fonction de creation d'un tableau d'entiers          */
  /* tires au hasard                                      */
  /* taille : nombre d'entiers du tableau                 */
  /* max    : valeur maximale des entiers tires au sort   */

  public static int [] initTableau(int taille,int max) {
    int [] t = new int[taille];
    for ( int i = 0 ; i < t.length ; i++ )
      t[i] =(int) (Math.random()*(max+1));
    return(t);
  }

  /* Fonction de calcul du nombre d'occurences d'un       */
  /* entier dans une partie d'un tableau d'entiers tries  */
  /* v : valeur recherchee                                */
  /* i : indice a partir duquel est recherche le nombre   */
  /*     d'occurences                                     */
  /* t : tableau d'entier ou est effectue la recherche    */

  public static int nombreOccurencesRecursive(int v,int i,int [] t) {
  /* Si tout le tableau a ete parcouru                    */
  /* ( i >= taille tableau ). -> On retourne 0            */
    if ( i >= t.length )
      return(0);
  /* Si l'entier d'indice i a une valeur superieure a v,  */
  /* il ne peut plus y avoir d'autre valeur egale a v     */
  /* car le tableau est trie. -> On retourne 0            */
    if ( t[i] > v )
      return(0);
  /* Calcul du nombre d'occurences de v de l'indice i+1   */
  /* a la fin du tableau                                  */
    int nb = nombreOccurencesRecursive(v,i+1,t);
  /* Si t[i] egal v on retourne nb+1, sinon,              */
  /* on retourne nb                                       */
    if ( t[i] == v )
      return(1+nb);
      else
      return(nb);
  }

  /* Fonction de calcul du nombre d'occurences            */
  /* d'un entier dans un tableau d'entiers tries          */
  /* v : valeur recherchee                                */
  /* t : tableau d'entier ou est effectue la recherche    */

  public static int nombreOccurences(int v,int [] t) {
  /* Appel a la fonction recursive depuis l'indice 0      */
    return(nombreOccurencesRecursive(v,0,t));
  }

  public static void main(String [] args) {
    Console.setTitle("NombreOccurencesRecursive");
  /* Affichage message et lecture au clavier de la taille */
  /* du tableau                                           */
    Console.out.print("Taille du tableau   : ");
    int n = Integer.valueOf(Console.in.readLine()).intValue();
  /* Affichage message et lecture au clavier de la valeur */
  /* maximale des entiers du tableau                      */
    Console.out.print("Valeur maximale     : ");
    int max = Integer.valueOf(Console.in.readLine()).intValue();
  /* Generation du tableau puis tri a bulle               */
    int [] t = initTableau(n,max);
    triBulle(t);
  /* Affichage du tableau                                 */
    for ( int i = 0 ; i < n ; i++ )
      Console.out.print(t[i]+" ");
    Console.out.println();
  /* Affichage message et lecture au clavier              */
  /* de la valeur recherchee                              */
    Console.out.print("Valeur recherchee   : ");
    int v = Integer.valueOf(Console.in.readLine()).intValue();
  /* Lancement de la fonction recursive de calcul         */
  /* et affichage du resultat                             */
    Console.out.println("Nombre d'occurences : "+nombreOccurences(v,t));
  }
}