De l'itératif au récursif

Version imprimable

Bonjour, je voudrais savoir comment je peux transformer ce programme itératif en un programme récursif. Je vous remercie d'avance :)

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
 
public int chercheEntierConsecutif_v2(int nb) {
        int x0 = -1;
        if (nb > 0 && nb <= tab.length) {
            int i = 0;
            while (x0 < 0 && i <= (tab.length - nb)) {
                if (compteOccurrences(i) >= nb) {
                    x0 = tab[i];
                }
                i++;
            }
 
        }
        return x0;
    }
 
    public int compteOccurrences(int i) {
        boolean b = true;
        int c = 0;
        int x = tab[i];
        while (b && i < tab.length) {
            b = (tab[i] == x);
            if (b) {
                c++;
                i++;
            }
        }
        return c;
    }

28/05/2013, 07h26
andry.aime

Bonjour,

En remplaçant la boucle par l'appel de la même fonction.

A+.
28/05/2013, 09h02
EnigmaClub

Je vous remercie de votre réponse, mais ça je le savais déjà, le problème c'est que j'arrive pas à le faire sur ce bout de code. Vous auriez pas une proposition ? Merci
28/05/2013, 09h15
toutgrego

Salut,

que doit faire ta méthode exactement ?

Voici ma méthode en un seul code, elle doit trouver un entier qui apparait dans nb cases consécutives d'un tableau.

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
 
public int chercheEntierConsecutif(int nb) {
        int x0 = -1;
        if (nb > 0 && nb <= tab.length) {
            int i = 0;
            while (x0 < 0 && i <= (tab.length - nb)) {
                int x = tab[i];
                int c = 1;
                boolean b = true;
                i++;
                while (b && i < tab.length && c < nb) {
                    b = (tab[i] == x);
                    if (b) {
                        c++;
                        i++;
                    }
                }
                if (c >= nb) {
                    x0 = x;
                }
            }
 
        }
        return x0;
    }

Salut,

voici le code en récursif pour trouver le nombre d’occurrences maximum consécutives d'un élément nb dans un tableau tab :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int chercheMaxOccur(Integer[] tab, int i, int maxOccur, int nb) {
        if (i >= tab.length) {
            return maxOccur;
        } else {
            int count = 0;
            while (i < tab.length && tab[i] == nb) {
                count++;
                if (count > maxOccur) {
                    maxOccur = count;
                }
                i++;
            }
            i++;
        }
        return chercheMaxOccur(tab, i, maxOccur, nb);
    }

J'ai fait ça vite fait, y'a surement moyen d'améliorer.

Toutgrego

28/05/2013, 09h48
EnigmaClub

Merci beaucoup, ça va vraiment m'aider à avancer, juste une question, normalement il doit y avoir aucune boucle dans une méthode récursive, est ce que je me trompe ?
28/05/2013, 09h55
toutgrego

Salut,

si tu peux très bien en avoir mais il faut savoir que toute boucle est 'transformable' en une fonction récursive terminale.
Ici c'est un peu plus galère parce qu'on a besoin du tableau, de i et de maxOccur mais c'est tout à fait faisable.
Pour t’entraîner à la récursivité tu peux t'amuser à transformer des boucles simple en méthode récursive.

Pense à mettre au début de ta méthode la condition d'arrêt puis dans le corps la condition de récursivité. Tu dois obligatoirement avoir un variant (comme dans une boucle).

Tchao!
28/05/2013, 10h25
EnigmaClub

Je vous remercie pour cette explication. Bonne journée :)