transformation d'une boucle en fonction récursive

Version imprimable

Tout est dans le titre.

J'essaie de transformer une fonction itérative en fonction récursive mais je bloque vraiment depuis un moment.

Voici mon programme:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class ITRF2004 { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int getA() throws NumberFormatException, IOException { System.out.printf("\n valeur de A :"); int A = Integer.parseInt(in.readLine()); return A; } int getB() throws NumberFormatException, IOException { System.out.printf("\n valeur de B :"); int B = Integer.parseInt(in.readLine()); return B; } int calcul(int A, int B) throws NumberFormatException, IOException { int x, y; x = A; y = 1; while (y < B) { if ((B / y) >= 2) { x = x * x; y = 2 * y; } else { x = x * A; y++; } System.out.printf("x= %d, y= %d\n", x, y); } return x; } public static void main(String [] args) throws NumberFormatException, IOException { ITRF2004 it = new ITRF2004(); int A, B, y; A = it.getA(); B = it.getB(); System.out.printf("\n\n Le résultat est %d", it.calcul(A, B)); } }
En règle générale, en récursivité, il y a une base. Or, ici, je ne la trouve pas.

Au départ, j'ai pensé à y<B et ai déclaré if (y>=B) return x; mais ça bloque le programme au bout d'un essai et me donne tout de suite le premier résultat.

De plus, si la fonction s'appelle elle-même, y est toujours réinitialisé à 1, ce qui n'est pas bon. J'en conclus qu'il faut le sortir de la fonction pour qu'il soit initialisé une première fois puis, en appelant la fonction, qu'il augmente.

Donc, voilà, je cogite, je cogite, mais je ne trouve pas encore la solution.

Quelqu'un aurait-il une petite idée pour me faire avancer?

Merci par avance,
Johnny

Tout d'abord, trouver ce que doit renvoyer la fonction récursive. Ici, c'est "x".
Ensuite, la condition d'arrêt de la récursion :

Code:

if( y >= B )

Enfin, ce que va calculer la récursion :
Code:

1 2 3 4 5 6 7 8 9 if ((B / y) >= 2) { x = x * x; y = 2 * y; } else { x = x * A; y++; }
Enfin, les paramètres à transmettre à la fonction :

Code:

calculRecursif( int x, int y, int A, int B )

Il faut construire une méthode public, avec la même signature que la fonction itérative, et une méthode privée, qui aura la signature décrite ci-dessus.
Le code final donne :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 public int calRec( int A, int B ) { return calculRecursif( A, 1, A, B ); } private int calculRecursif( int x, int y, int A, int B ) { System.out.printf("x= %d, y= %d\n", x, y); if( y >= B ) { return x; } else { if( B >= 2 * y ) { return calculRecursif( x * x, y * 2, A, B ); } else { return calculRecursif( x * A, y + 1, A, B ); } } }

Merci!

J'avais trouvé cela qui ne fonctionnait que dans certains cas:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class ITRF2004 {
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
 
	int getA() throws NumberFormatException, IOException
	{
		System.out.printf("\nvaleur de A :");
		int A = Integer.parseInt(in.readLine());
		return A;
	}
 
	int getB() throws NumberFormatException, IOException
	{
		System.out.printf("\nvaleur de B :");
		int B = Integer.parseInt(in.readLine());
		return B;
	}
 
	int calculIteratif(int A, int B, int y) throws NumberFormatException, IOException
	{
		int x;
		x = A;
		while (y < B)
		{
			if ((B / y) >= 2)
			{
				x = x * x;
				y = 2 * y;
			} else
			{
				x = x * A;
				y++;
			}
			System.out.printf("x= %d, y= %d\n", x, y);
		}
		return x;
	}
 
	int calculRecursif(int A, int B, int y) throws NumberFormatException, IOException
	{
		int x;
		x = A;
		if (y>=B) return x;
		while (y < B)
		{
			if ((B / y) >= 2)
			{
				return calculRecursif (x*x, B, 2*y);
			} else
			{
				return calculRecursif (x*A, B, y+1);
			}
		}
		System.out.printf("\nx= %d, y= %d\n", x, y);
		return x;
	}
 
	public static void main(String [] args) throws NumberFormatException, IOException
	{
		ITRF2004 it = new ITRF2004();
		int A, B, y;
		A = it.getA();
		B = it.getB();
		y = 1;
		System.out.printf("\n\nLe résultat est %d", it.calculIteratif(A, B, y));
		System.out.printf("\n\nLe résultat est %d", it.calculRecursif(A, B, y));
	}
}

Décidément, j'ai encore du boulot en récursivité. Merci pour l'aide, j'apprécie, car je n'aurai jamais le corrigé (c'est un exercice d'une annale ITRF de 2004, concours que je prépare pour la première fois cette année)