Récursivité et tableaux

Version imprimable

Bonsoir ,

j'ai un devoir pour demain et je n'arrive pas a comprendre la récursivité

Je cherche une solution pour ces fonctions :

- Une fonction récursive qui permet de remplir un tableau de n entiers
- Une fonction récursive qui permet d'afficher ce tableau
- Une fonction récursive qui permet d'inverser ce tableau
- Une fonction récursive qui permet de calculer la somme des éléments de ce tableau

Quelqu'un pourrait m'aider ?
Merci 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 30 31 32 33 34 #include<stdio.h> int remplir (int *t , int n , int i ) { if (i<n) { printf ("t[%d]=",i) ; scanf ("%d",&t[i]); remplir(t,n,i+1); } } void affiche (int *t, int n , int i ) { if (i<n) { printf("| %d ",t[i]) ; affiche (t,n,i+1) ; } } void affiche_inv (int *t, int n , int i ) { if (i<n) { affiche_inv(t,n,i+1) ; printf("| %d ",t[i]) ; } } void main () { int t[5],n=5; remplir(t,n,0) ; affiche(t,n,0) ; printf ("\n"); affiche_inv(t,n,0); }

Voici la solution :mrgreen: :mrgreen:

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
#include <stdio.h>
#include <stdlib.h> /* srand, rand */
#include <time.h>   /* time */
 
 
#define TAB_NB_ELEMENTS 10
 
typedef void (*t_callback) (int* /*result*/);
 
 
/* forward declarations - private functions */
 
void p_tab_display(int* /*tab*/, size_t /*index*/, size_t /*nb_elements*/);
 
void p_tab_fill(
            int*       /*tab*/,
            size_t     /*index*/,
            size_t     /*nb_elements*/,
            t_callback /*func_get_value*/);
 
void p_tab_reverse(int* /*tab*/, size_t /*start_index*/, size_t /*end_index*/);
 
void p_tab_reverse_display(int* /*tab*/, size_t /*index*/, size_t /*nb_elements*/);
 
int p_tab_sum(int* /*tab*/, size_t /*index*/, size_t /*nb_elements*/);
 
 
/* callback functions and global */
static int g_value = 0;
 
void callback_add_one(int* result) {
//  if (init_value != NULL) {
        (*result) = g_value;
        ++g_value;
//  }
}
 
void callback_get_g_value(int* result) {
//  if (init_value != NULL) {
        (*result) = g_value;
//  }
}
 
void callback_get_zero(int* result) {
//  if (init_value != NULL) {
        (*result) = 0;
//  }
}
 
void init_g_value(int init_value) {
    g_value = init_value;
}
 
 
/* public functions */
 
void tab_display(int* tab, size_t nb_elements) {
    if ((tab != NULL) && (nb_elements > 0)) {
        p_tab_display(tab, 0, nb_elements);
    }
}
 
 
void tab_fill(
            int*       tab,
            size_t     nb_elements,
            t_callback func_get_value) {
 
    if ((tab != NULL) && (nb_elements > 0) && (func_get_value != NULL)) {
        p_tab_fill(tab, 0, nb_elements, func_get_value);
    }
}
 
 
void tab_reverse(int* tab, size_t nb_elements) {
    if ((tab != NULL) && (nb_elements > 1)) {
        p_tab_reverse(tab, 0, (nb_elements - 1));
    }
}
 
 
void tab_reverse_display(int* tab, size_t nb_elements) {
    if ((tab != NULL) && (nb_elements > 0)) {
        p_tab_reverse_display(tab, 0, nb_elements);
    }
}
 
 
unsigned char tab_sum(int* tab, size_t nb_elements, int* result) {
 
    unsigned char ret;
 
    if ((tab != NULL) && (nb_elements > 0)) {
        (*result) = p_tab_sum(tab, 0, nb_elements);
 
        ret = 1;
    } else {
        ret = 0;
    }
 
    return ret;
}
 
 
/* private functions - no need to test the input parameters */
 
void p_tab_display(int* tab, size_t index, size_t nb_elements) {
    if (index < nb_elements) {
        printf("%d | ", (*tab));
 
        p_tab_display((tab + 1), (index + 1), nb_elements);
    } else {
        printf("\n");
    }
}
 
 
void p_tab_fill(
            int*       tab,
            size_t     index,
            size_t     nb_elements,
            t_callback func_get_value) {
 
    func_get_value(tab);
 
    if (index < nb_elements) { p_tab_fill((tab + 1), (index + 1), nb_elements, func_get_value); }
}
 
 
void p_tab_reverse(int* tab, size_t start_index, size_t end_index) {
    if (start_index < end_index) {
        int temp;
 
        temp            = tab[end_index];
        tab[end_index]  = tab[start_index];
        tab[start_index]= temp;
 
        p_tab_reverse(tab, (start_index + 1), (end_index - 1));
    }
}
 
 
void p_tab_reverse_display(int* tab, size_t index, size_t nb_elements) {
    if (index < nb_elements) {
        p_tab_reverse_display((tab + 1), (index + 1), nb_elements);
 
        printf("%d | ", (*tab));
    }
 
    if (index == 0) { printf("\n"); }
}
 
 
int p_tab_sum(int* tab, size_t index, size_t nb_elements) {
    return ((index < nb_elements)? ((*tab) + p_tab_sum((tab + 1), (index + 1), nb_elements)): 0);
}
 
 
int main(int argc, char* argv[])
{
    int tab[TAB_NB_ELEMENTS];
    int result;
 
/*****************************************************************************/
    tab_fill(tab, TAB_NB_ELEMENTS, callback_get_zero);
    tab_display(tab, TAB_NB_ELEMENTS);
    tab_reverse_display(tab, TAB_NB_ELEMENTS);
 
    if ( tab_sum(tab, TAB_NB_ELEMENTS, &result) ) {
        printf("Sum zero : %d\n\n", result);
    } else {
        printf("Sum zero : [error]\n\n");
    }
 
/*****************************************************************************/
    init_g_value(24);
 
    tab_fill(tab, TAB_NB_ELEMENTS, callback_add_one);
    tab_display(tab, TAB_NB_ELEMENTS);
    tab_reverse_display(tab, TAB_NB_ELEMENTS);
 
    if ( tab_sum(tab, TAB_NB_ELEMENTS, &result) ) {
        printf("Sum : %d\n\n", result);
    } else {
        printf("Sum : [error]\n\n");
    }
 
/*****************************************************************************/
    tab_reverse(tab, TAB_NB_ELEMENTS);
    tab_display(tab, TAB_NB_ELEMENTS);
 
    if ( tab_sum(tab, TAB_NB_ELEMENTS, &result) ) {
        printf("Sum reverse : %d\n\n", result);
    } else {
        printf("Sum reverse : [error]\n\n");
    }
 
/*****************************************************************************/
/*  initialize random seed */
    srand (time(NULL));
 
/*  range 1 to 999 */
    init_g_value(1 + (rand() % 999));
 
    tab_fill(tab, TAB_NB_ELEMENTS, callback_get_g_value);
    tab_display(tab, TAB_NB_ELEMENTS);
 
    if ( tab_sum(tab, TAB_NB_ELEMENTS, &result) ) {
        printf("Sum pow : %d\n\n", result);
    } else {
        printf("Sum pow : [error]\n\n");
    }
 
    return 0;
}

Édit : avec des pointeurs de fonctions pour remplir son tableau :mrgreen:

Citation:

Envoyé par foetus

Voici la solution :mrgreen: :mrgreen:avec des pointeurs de fonctions pour remplir son tableau :mrgreen:

Tiens... ça me rappelle ce topic où l'intervenant voulait lui aussi une solution finie. il a été servi :mouarf:

Mais toi tu as été particulièrement immonde (mais en C t'es avantagé pour ça) :mrgreen:

Citation:

Envoyé par Sam246

et je n'arrive pas a comprendre la récursivité

Pour comprendre la récursivité, il faut arriver à se placer du point de vue de la fonction qui, généralement, ne s'occupe que d'une partie de l'élément qu'elle a à gérer. Et la suite, elle le passe à une autre instance d'elle-même qui, donc, s'occupera d'une autre partie.

Et si tu veux t'en sortir de façon générale, il faut alors adopter le schéma suivant pour tes fonctions :
Code:

1 2 3 4 5 6 7 8 9 10 fonction(param) { // Test fin de récursivité (pour éviter à la fonction de s'appeler à l'infini) // Si oui, return // Code qui s'occupe de l'élément à traiter ... // Appel de la fonction avec des paramètres différents (sinon l'autre instance ne peut pas détecter qu'elle est différente) fonction(param2) }
Citation:
Envoyé par Sam246
Code:

1 2 3 4 5 6 7 8 void affiche (int *t, int n , int i ) { if (i<n) { printf("| %d ",t[i]) ; affiche (t,n,i+1) ; } }
Ben à vue de nez elle me semble correcte cette fonction ???
Maintenant si on y applique le schéma ci-dessus, alors ça donnerait
Code:

1 2 3 4 5 void affiche (int *t, int n , int i ) { if (i == n) return; printf("| %d ", t[0]) ; affiche (t+1, n, i+1) ; }
Je pense que tu as mal testé ton truc. Il te faut
ecrire une fonction
tester la fonction
t'attaquer à la fonction suivante

et non écrire tout le code et tout tester en final sans pouvoir détecter ce qui ne va pas...

[edit]j'avais pas testé ton code mais là j'ai pu le tester et tout est ok. Donc finalement qu'est-ce qui ne va pas avec la récursivité ???

Citation:

Envoyé par Sam246

void main ()

Ouais, t'as raison !!!

Citation:

Envoyé par Sam246

j'ai un devoir pour demain

Ah ben tant pis. Fallait venir avant...

14/03/2019, 13h24
emixam16

Désolé, je ne peux pas résister.

https://imgs.xkcd.com/comics/dependencies.png

:dehors:
14/03/2019, 15h01
foetus

Citation:

Envoyé par Sve@r

Donc finalement qu'est-ce qui ne va pas avec la récursivité ???

Si tu regardes sa question :mrgreen:, dans son code, il manque la somme des éléments et inverser le tableau.

Calculer la somme en récursif c'est trivial (c'est un exercice de base), et on peut aborder la récursion terminale :mrgreen:

Mais c'est vrai qu'inverser un tableau récursivement :koi: ... ce n'est pas la fonction facile à voir/ appréhender, parce que c'est un peu contre nature.
Par contre il a codé l'affichage inversé ... peut-être pour s'aider :whistle: ... mais cela ne l'a apparemment pas aidé :aie:

Citation:

Envoyé par Sve@r

Et si tu veux t'en sortir de façon générale, il faut alors adopter le schéma suivant pour tes fonctions :

Ton schéma n'est pas trop général :whistle:, parce que souvent avec la récursion tu vas devoir coder 2 fonctions (ce que j'ai fait), avec une fonction frontale ('front-end') qui, en plus de tester les paramètres en entrée - préconditions, appelle une fonction arrière-plan ('back-end') ayant plus de paramètres/ moins de tests.

Citation:

Envoyé par foetus

Si tu regardes sa question :mrgreen:, dans son code, il manque la somme des éléments et inverser le tableau.
Mais c'est vrai qu'inverser un tableau récursivement :koi: ... ce n'est pas la fonction facile à voir/ appréhender, parce que c'est un peu contre nature.
Par contre il a codé l'affichage inversé ... peut-être pour s'aider :whistle: ... mais cela ne l'a apparemment pas aidé :aie:

Ben en fait, je pense que ce qu'il appelait "inverser un tableau" consistait en réalité à l'afficher à l'envers...
Donc selon moi, il ne manque que l'addition et je pense que s'il était revenu on aurait pu la lui faire coder.

Citation:

Envoyé par foetus

Ton schéma n'est pas trop général :whistle:, parce que souvent avec la récursion tu vas devoir coder 2 fonctions (ce que j'ai fait), avec une fonction frontale ('front-end') qui, en plus de tester les paramètres en entrée - préconditions, appelle une fonction arrière-plan ('back-end') ayant plus de paramètres/ moins de tests.

Là tu parles d'un test pour checker ce qui entre à l'origine. Test à ne faire bien évidemment qu'une fois. Ca moi je n'en ai pas parlé (déjà je n'y pensais pas et même si j'y avais pensé je ne l'aurais pas mentionné pour pas complexifier la chose).

Donc non, mon schéma général permet (il me semble) de coder tout algorithme récursif. On commence par tester si la récursivité est terminée, et sinon on l'applique.
Le seul défaut de ce schéma est qu'on applique la récursivité une fois de plus qu'il n'est nécessaire.
On peut l'éviter en le remplaçant par le schéma suivant
Code:

1 2 3 4 5 6 7 8 9 10 fonction(param) { // Code qui s'occupe de l'élément à traiter ... // Test récursivté terminée (pour éviter à la fonction de s'appeler à l'infini) // Si oui, return valeur calculée // Appel de la fonction avec des paramètres différents (sinon l'autre instance ne peut pas détecter qu'elle est différente) return fonction(param2) }
Le souci de ce schéma est qu'il faudra tester si la récursivité doit commencer donc (grosso-modo) réécrire le premier test dans la fonction primitive qui appelle la fonction récursive quand elle veut son calcul. Bref on a toujours des avantages et inconvénients à choisir telle ou telle solution...