import java.util.*;

class BlocF {
    public int parametreN;
    public int adresseDeRetour;
    public int valeurDeRetour;
    BlocF(int ar, int n) {
	adresseDeRetour = ar;
	parametreN = n;
	valeurDeRetour = -1;
    }
    public String toString() {
	return "{n="+parametreN+",retour="+adresseDeRetour+",valeur="+valeurDeRetour+"}";
    }
}

public class EX8_1 {
    public static void main(String []a) {
	boolean fin = false;
	int instruction = -2;
	int x=0;
	Stack pile = new Stack();
	BlocF bf, nouveauBloc, blocRetour;
	while (!fin) {
	    System.out.println("Je dois faire l'instruction "+instruction+" la pile est "+pile);
	    switch (instruction) {
	    case -2: // main, initialisation de x à 10
		x = 10;
		instruction = -1;
		break;
	    case -1: // appel à f(x)
		bf = new BlocF(0,x); // quand calcul de f() terminé, il faudra revenir en 0
		pile.push(bf); // transmission bloc d'activation
		instruction = 1; // saut vers première instruction de f()
		break;
	    case 0:
		bf = (BlocF)(pile.pop()); // suppression bloc activation créé à l'appel
		System.out.println("Résultat="+bf.valeurDeRetour);
		fin = true;
		break;
	    case 1: // première instruction de f()
		// cas f(0)
		bf = (BlocF)(pile.peek());
		if (bf.parametreN==0) {
		    bf.valeurDeRetour = 1; // prépare la valeur de retour pour que l'appelant puisse la retrouver
		    instruction = bf.adresseDeRetour; // saut vers l'instruction qui suit l'appel, on retourne là on l'on nous a dit de retourner
		} else {
		    instruction = 2;
		}
		break;
	    case 2: // cas N pair
		bf = (BlocF)(pile.peek());
		if (bf.parametreN%2==0) {
		    nouveauBloc = new BlocF(3,bf.parametreN/2); // quand calcul de f() terminé il faudra revenir en 3
		    pile.push(nouveauBloc); // transmission bloc activation
		    instruction = 1; // saut vers la première instruction de f()
		} else {
		    instruction = 4;
		}
		break;
	    case 3: // retour de F(n/2)
		blocRetour = (BlocF)(pile.pop()); // on enlève le bloc transmis au moment de l'appel récursif
		bf = (BlocF)(pile.peek()); // on récupère les paramètres de cet appel ci
		bf.valeurDeRetour = bf.parametreN*blocRetour.valeurDeRetour; // on calcule n*f(n/2) qu'on range dans le bloc d'activation courant
		instruction = bf.adresseDeRetour; // on retourne là où l'on nous a dit de retourner
		break;
	    case 4: // cas N impair
		bf = (BlocF)(pile.peek());
		nouveauBloc = new BlocF(5,(bf.parametreN-1)/2); // quand calcul de f() terminé il faudra revenir en 5
		pile.push(nouveauBloc); // transmission bloc d'activation
		instruction = 1; // saut vers la première instruction de f()
		break;
	    case 5: // retour de F(n-1/2)
		blocRetour = (BlocF)(pile.pop()); // on enlève le bloc transmis au moment de l'appel récursif
		bf = (BlocF)(pile.peek()); // on récupère les paramètres de l'appel courant
		bf.valeurDeRetour = 1+blocRetour.valeurDeRetour; // on calcule 1+f((n-1)/2) qu'on range dans le bloc d'activation courant
		instruction = bf.adresseDeRetour; // on retourne là où l'on nous a dit de retourner
		break;
	    }
	}
    }
}