import java.util.*;

public class Exo2 {
    /*
      Question 2:
        Attention: on peut écrire le troisième cas comme
	  if (m>n) return f(m-n,n);
	mais ce n'est pas vraiment une traduction de la définition dans laquelle
	il est explicitement écrit "sinon". Bien entendu, le résultat est le
	même, mais la méthode de calcul n'est pas tout à fait la même, un test
	(inutile) y serait systématiquement fait qui ne changerait rien au
	résultat.
	Attention: on peut aussi rajouter un test
	  if (m<1 || n<1) return -1; en première ligne
	afin de faire quelque chose de la définition mathématique indiquant
	que n et m appartiennent à l'ensemble des naturels strictement positifs
	mais ce n'est pas la bonne façon de faire! En efet, ceci n'est qu'une
	simple précondition ui doit être vérifiée sous peine d'obtenir n'importe
	quoi. Et d'ailleurs le "return -1" est assez arbitraire et n'existe
	pas dans la définition de la fonction mathématique. C'est de la
	responsabilité de celui qui calcule que de vérifier que les données
	avec lesquelles il calcule appartiennent à l'ensemble de définition...
    */
    public static int f(int n,int m) {
	// Juste pour voir les choses se faire (Question 1)
	System.out.println("f("+n+","+m+")");
	if (n==m) return n;
	if (m<n)  return f(n-m,m);
	else      return f(m-n,n);
    }

    // Quelques tests
    public static void main(String []args) {
	int r = f(1,5);
	System.out.println("Le résultat de f(1,5) est "+r);
	r = f(24,30);
	System.out.println("Le résultat de f(24,30) est "+r);

	r = f_traduite_recursive(24,30);
	System.out.println("f_traduite_recursive(24,30)="+r);

	r = f_traduite_recursive_bis(24,30);
	System.out.println("f_traduite_recursive_bis(24,30)="+r);

	r = f_traduite_recursive_ter(24,30);
	System.out.println("f_traduite_recursive_ter(24,30)="+r);

	r = f_traduite_finale(24,30);
	System.out.println("f_traduite_finale(24,30)="+r);
    }

    /*
      Question 3: version récursive...
        on peut constater que la récursion est effectivement terminale car
	après avoir fait un appel récursif AUCUN calcul n'est fait avec
	la valeur de retour. Ce qui s'observe dans le code des
	cases 12-15 et 20-23. On remarquera d'ailleurs que ces deux portions
	sont strictement identiques, on aurait donc pu "optimiser" en supprimant
	21-23 et en remplacement 20 par :
	  instruction=12; break;
	mais mieux même l'appel est identique on aurait donc pu supprimer 19-23
	et remplacer la dernière ligne du cas 18 par
	  instruction=11; break;
	Cette modification est observable dans la version nommée
	f_traduite_recursvie_bis
	RDV à la version f_traduite_recursive_ter pour le traitement de
	la récursion terminale...
    */
    public static int f_traduite_recursive(int n,int m) {
	// Convention memoire[0] = n, memoire[1] = m,
	//            memoire[2] variable temporaire
	int []memoire = new int[3];
	int instruction = 1;
	boolean termine=false;
	Frame f = null;
	Stack<Frame> pile = new Stack<Frame>();
	while (!termine) {
	    switch(instruction) {
	    case 1: // appel à f(n,m)
		pile.push(new Frame(2,0,n,m));
		instruction=4; break;
	    case 2: // on revient de l'appel initial
		f = pile.pop();
		instruction++; break;
	    case 3: // ok on sort
		termine = true;
		break;
	    case 4: // entrée de f(int n,int m)
		f = pile.peek();
		// Juste pour observer que tout se passe normalement
		System.out.println("f_simulée("+f.n+","+f.m+")");
		instruction++; break;
	    case 5:
	        memoire[0] = f.n;
		instruction++; break;
	    case 6:
		memoire[1] = f.m;
		instruction++; break;
	    case 7: // test n==m
		if (memoire[0]==memoire[1]) instruction++;
		else                        instruction=9;
		break;
	    case 8: // cas n==m on renvoie n et retour là où il faut
		f.valeur = memoire[0];
		instruction = f.retour;	break;
	    case 9: // test m<n
		if (memoire[1]<memoire[0]) instruction++;
		else                       instruction=16;
		break;
	    case 10: // cas m<n
		memoire[0] -= memoire[1];
		instruction++; break;
	    case 11: // appel récursif
		pile.push(new Frame(12,0,memoire[0],memoire[1]));
		instruction=4; break;
	    case 12: // retour de l'appel
		f = pile.pop();
		instruction++; break;
	    case 13: // on récupère la valeur de retour
		memoire[0] = f.valeur;
		instruction++; break;
	    case 14: // on positionne le retour de l'appel et fait le return
		f = pile.peek();
		instruction++; break;
	    case 15:
		f.valeur = memoire[0];
		instruction = f.retour; break;
	    case 16: // cas sinon
		memoire[2] = memoire[0];
		instruction++; break;
	    case 17:
		memoire[0] = memoire[1]-memoire[0];
		instruction++; break;
	    case 18:
		memoire[1] = memoire[2];
		instruction++; break;
	    case 19: // appel recursif
		pile.push(new Frame(20,0,memoire[0],memoire[1]));
		instruction=4; break;
	    case 20: // retour de l'appel
		f = pile.pop(); instruction++; break;
	    case 21: // on récupère la valeur de retour
		memoire[0] = f.valeur;
		instruction++; break;
	    case 22: // on positionne le retour de l'appel et fait le return
		f = pile.peek(); instruction++; break;
	    case 23:
		f.valeur = memoire[0]; instruction = f.retour; break;
	    }
	}
	return f.valeur;
    }

    public static int f_traduite_recursive_bis(int n,int m) {
	// Convention memoire[0] = n, memoire[1] = m,
	//            memoire[2] variable temporaire
	int []memoire = new int[3];
	int instruction = 1;
	boolean termine=false;
	Frame f = null;
	Stack<Frame> pile = new Stack<Frame>();
	while (!termine) {
	    switch(instruction) {
	    case 1: // appel à f(n,m)
		pile.push(new Frame(2,0,n,m));
		instruction=4; break;
	    case 2: // on revient de l'appel initial
		f = pile.pop();
		instruction++; break;
	    case 3: // ok on sort
		termine = true;
		break;
	    case 4: // entrée de f(int n,int m)
		f = pile.peek();
		// Juste pour observer que tout se passe normalement
		System.out.println("f_simulée_bis("+f.n+","+f.m+")");
		instruction++; break;
	    case 5:
	        memoire[0] = f.n;
		instruction++; break;
	    case 6:
		memoire[1] = f.m;
		instruction++; break;
	    case 7: // test n==m
		if (memoire[0]==memoire[1]) instruction++;
		else                        instruction=9;
		break;
	    case 8: // cas n==m on renvoie n et retour là où il faut
		f.valeur = memoire[0];
		instruction = f.retour;	break;
	    case 9: // test m<n
		if (memoire[1]<memoire[0]) instruction++;
		else                       instruction=16;
		break;
	    case 10: // cas m<n
		memoire[0] -= memoire[1];
		instruction++; break;
	    case 11: // appel récursif
		pile.push(new Frame(12,0,memoire[0],memoire[1]));
		instruction=4; break;
	    case 12: // retour de l'appel
		f = pile.pop();
		instruction++; break;
	    case 13: // on récupère la valeur de retour
		memoire[0] = f.valeur;
		instruction++; break;
	    case 14: // on positionne le retour de l'appel et fait le return
		f = pile.peek();
		instruction++; break;
	    case 15:
		f.valeur = memoire[0];
		instruction = f.retour; break;
	    case 16: // cas sinon
		memoire[2] = memoire[0];
		instruction++; break;
	    case 17:
		memoire[0] = memoire[1]-memoire[0];
		instruction++; break;
	    case 18:
		memoire[1] = memoire[2];
		instruction=11; break;
	    }
	}
	return f.valeur;
    }

    /*
	Puisque qu'AUCUN calcul n'est fait avec la valeur de retour lors des
	appels récursifs, nous sommes dans le cas d'une récursion terminale.
	Dans ce type de récursion terminale où AUCUN calcul n'est fait au retour
	d'un appel, il est inutile de conserver les valeurs des arguments
	passés en les empilants. Ce que nous avons fait ici en transformant
	la Frame (qui ne contient plus que la valeur de retour et l'adresse
	de retour). Que nous éliminerons ensuite!
	Attention, ceci dégénère les case 5 et 6 (qu'on éliminera tout à la
	fin!)
	L'optimisation suivante consiste donc à éliminer totalement la pile.
	D'abord il ne sert à rien d'empiler la valeur de retour puisque c'est
	une valeur totalement inchangée qui est trimballée à chaque retour!
	Autant la stocker dans une memoire dédiée disons memoire[3] par
	exemple!
	D'autre part on observe la stupidité des instruction 11 et 12 dans
	lesquelles on "pushe" toujours l'instruction de retour 12 afin d'y
	revenir sauf dans le cas ou n==m où l'on doit sortir de l'appel initial.
	Donc évitons cet appel et remplaçons le par un simple saut.
	Toutes ces modifications sont à observer dans f_traduite_finale.
	Bien entendu les valeurs des sauts, etc devront être modifiés en
	conséquence...
    */
    public static int f_traduite_recursive_ter(int n,int m) {
	// Convention memoire[0] = n, memoire[1] = m,
	//            memoire[2] variable temporaire
	int []memoire = new int[3];
	int instruction = 1;
	boolean termine=false;
	Frame_reduite f = null;
	Stack<Frame_reduite> pile = new Stack<Frame_reduite>();
	while (!termine) {
	    switch(instruction) {
	    case 1: // appel à f(n,m)
		memoire[0] = n;
		memoire[1] = m;
		pile.push(new Frame_reduite(2,0));
		instruction=4; break;
	    case 2: // on revient de l'appel initial
		f = pile.pop();
		instruction++; break;
	    case 3: // ok on sort
		termine = true;
		break;
	    case 4: // entrée de f(int n,int m)
		f = pile.peek();
		// Juste pour observer que tout se passe normalement
		System.out.println("f_simulée_ter("+memoire[0]+","+memoire[1]+")");
		instruction++; break;
	    case 5:
		instruction++; break;
	    case 6:
		instruction++; break;
	    case 7: // test n==m
		if (memoire[0]==memoire[1]) instruction++;
		else                        instruction=9;
		break;
	    case 8: // cas n==m on renvoie n et retour là où il faut
		f.valeur = memoire[0];
		instruction = f.retour;	break;
	    case 9: // test m<n
		if (memoire[1]<memoire[0]) instruction++;
		else                       instruction=16;
		break;
	    case 10: // cas m<n
		memoire[0] -= memoire[1];
		instruction++; break;
	    case 11: // appel récursif
		pile.push(new Frame_reduite(12,0));
		instruction=4; break;
	    case 12: // retour de l'appel
		f = pile.pop();
		instruction++; break;
	    case 13: // on récupère la valeur de retour
		memoire[0] = f.valeur;
		instruction++; break;
	    case 14: // on positionne le retour de l'appel et fait le return
		f = pile.peek();
		instruction++; break;
	    case 15:
		f.valeur = memoire[0];
		instruction = f.retour; break;
	    case 16: // cas sinon
		memoire[2] = memoire[0];
		instruction++; break;
	    case 17:
		memoire[0] = memoire[1]-memoire[0];
		instruction++; break;
	    case 18:
		memoire[1] = memoire[2];
		instruction=11; break;
	    }
	}
	return f.valeur;
    }

    /*
        Les curieux pourront s'amuser à éliminer encore quelques petites choses
	ici...
	Note : cette solution ou toute variante raisonnable est acceptable
	comme réponse sans avoir à expliquer toutes les transformations
	précédentes; mais il faut ABSOLUMENT être conscient de celles-ci afin
	de bien comprendre et pouvoir justifier l'élimination de la récursion
	terminale.
    */
    public static int f_traduite_finale(int n,int m) {
	// Convention memoire[0] = n, memoire[1] = m,
	//            memoire[2] variable temporaire
	int []memoire = new int[3];
	int instruction = 1;
	boolean termine=false;
	Stack<Frame_reduite> pile = new Stack<Frame_reduite>();
	Frame_reduite f = null;
	while (!termine) {
	    switch(instruction) {
	    case 1: // appel intial à f(n,m)
		memoire[0] = n;
		memoire[1] = m;
		pile.push(new Frame_reduite(2,0));
		instruction=4; break;
	    case 2: // on revient de l'appel initial
		f = pile.pop();
		instruction++; break;
	    case 3: // ok on sort
		termine = true;
		break;
	    case 4: // entrée de f(int n,int m)
		f = pile.peek();
		instruction++; break;
	    case 5: // test n==m
		// Juste pour observer que tout se passe normalement
		System.out.println("f_simulée_finale("+memoire[0]+","+memoire[1]+")");
		if (memoire[0]==memoire[1]) instruction++;
		else                        instruction=7;
		break;
	    case 6: // cas n==m on renvoie n et retour là où il faut
		f.valeur = memoire[0];
		instruction = f.retour;	break;
	    case 7: // test m<n
		if (memoire[1]<memoire[0]) instruction++;
		else                       instruction=10;
		break;
	    case 8: // cas m<n
		memoire[0] -= memoire[1];
		instruction++; break;
	    case 9: // appel itératif
		instruction=5; break;
	    case 10: // cas sinon
		memoire[2] = memoire[0];
		instruction++; break;
	    case 11:
		memoire[0] = memoire[1]-memoire[0];
		instruction++; break;
	    case 12:
		memoire[1] = memoire[2];
		instruction=9; break;
	    }
	}
	return f.valeur;
    }
}

class Frame {
    public int retour;
    public int valeur;
    public int n;
    public int m;
    public Frame(int i,int v,int n,int m) {
	retour = i;
	valeur = v;
	this.n = n;
	this.m = m;
    }
}

class Frame_reduite {
    public int retour;
    public int valeur;
    public Frame_reduite(int i,int v) {
	retour = i;
	valeur = v;
    }
}