Partage
  • Partager sur Facebook
  • Partager sur Twitter

Fonction récursive et segmentation fault

Sujet résolu
    17 mars 2022 à 16:41:41

    Bonjour,

    J'ai eu comme consigne d'écrire une fonction récursive permettant d'obtenir le plus grand indice où apparait une valeur dans un tableau d'entier ou de renvoyer -1. J'ai donc codé ce code (voir ci-dessous), mais j'obtiens une segmentation fault.

    Le problème est que je comprends cette erreur, cependant je ne sais pas comment la résoudre, je fais ainsi appelle à vous pour m'aider si vous le pouvez, je vous remercie d'avance pour votre temps.

    #include <stdio.h>
    
    #include <stdlib.h>
    
    #include <assert.h>
    
    
    int recherche_recur(int tab[],int taille,int val){
    
        int i=0;
    
        int iter;
    
        if (taille>1){
    
            for (i=0;i<taille;i++){
    
                iter=-1;
    
                if (tab[i]==val){
    
                    int iter=i;
    
                }recherche_recur(tab,taille,val);
    
            }return iter;
    
        }
    
    }
    
    int main(){
    
        int tab[6]={1,2,5,78,11,99};
    
        assert(recherche_recur(tab,6,78)==6);
    
        printf("%d\n",recherche_recur(tab,6,78));
    
        return 0;
    
    }



    -
    Edité par Yanissb 17 mars 2022 à 17:32:02

    • Partager sur Facebook
    • Partager sur Twitter
      17 mars 2022 à 17:20:33

      Utilises le bouton code </> du forum pour poster ton code ! (tu peux modifier ton post, lien modifier en haut à droite du post).
      • Partager sur Facebook
      • Partager sur Twitter
        17 mars 2022 à 17:20:42

        Hello,


        Merci.

        -
        Edité par edgarjacobs 17 mars 2022 à 17:21:12

        • Partager sur Facebook
        • Partager sur Twitter
          17 mars 2022 à 17:30:10

          Je vois que tu as posté une fonction de recherche par itération, or elle ne fonctionne pas !

          Tu veux donc déjà faire par récursivité alors que tu n'y arrives pas par itération ?

          Autrement dans une recherche par récursivité, il n'y a pas de boucle, c'est la récursivité qui remplace la boucle !

          PS : Actives les warnings, ça te donnera des indications !

          • Partager sur Facebook
          • Partager sur Twitter
            17 mars 2022 à 17:36:28

            rouIoude a écrit:

            Je vois que tu as posté une fonction de recherche par itération, or elle ne fonctionne pas !

            Tu veux donc déjà faire par récursivité alors que tu n'y arrives pas par itération ?

            Autrement dans une recherche par récursivité, il n'y a pas de boucle, c'est la récursivité qui remplace la boucle !

            PS : Actives les warnings, ça te donnera des indications !


            Bonjour, la première fonction est celle en version itérative, d'après le compilateur et les tests, elle fonctionne, pourrais-tu me donner plus de détails sur pourquoi elle ne fonctionne pas stp ? La deuxième, elle ne fonctionne pas. Pour les warnings je n'en avais aucun sur VS code ni en compilant sur le terminal mais merci de m'avertir. 

            • Partager sur Facebook
            • Partager sur Twitter
              17 mars 2022 à 17:47:28

              Pour l'itérative, tu l'as effacée, je la poste :

              int recherche_iter(int tab[], int taille, int val)
              {
                  for (int i=0; i<taille; i++)
                  {
                      if (tab[i]==val)
                      {
                          return i;
                      }
                      return -1;
                  }
              }

              Tu remarqueras que ton return -1 et mal placé ! Puisqu'il est exécuté dès le premier tour de boucle ! (Tes tests n'ont pas du être très rigoureux) !

              Pour la fonction récurcive, je ne vais pas te faire un cours, alors je te poste la solution :

              int recherche_recur(int tab[], int taille, int val)
              {
                  if(taille==0) return -1;
                  if(*tab==val) return taille;
                  return recherche_recur(tab+1, taille-1, val);
              }

              Comme je t'ai dit il n'y a pas de boucle. Fait en bon usage !


              Pour les Warnings il faut les activer dans les options du compilateur. (sous gcc au minimum -Wall -Wextra).

              • Partager sur Facebook
              • Partager sur Twitter
                17 mars 2022 à 17:51:49

                rouIoude a écrit:

                Pour l'itérative, tu l'as effacée, je la poste :

                int recherche_iter(int tab[], int taille, int val)
                {
                    for (int i=0; i<taille; i++)
                    {
                        if (tab[i]==val)
                        {
                            return i;
                        }
                        return -1;
                    }
                }

                Tu remarqueras que ton return -1 et mal placé ! Puisqu'il est exécuté dès le premier tour de boucle ! (Tes tests n'ont pas du être très rigoureux) !

                Pour la fonction récurcive, je ne vais pas te faire un cours, alors je te poste la solution :

                int recherche_recur(int tab[], int taille, int val)
                {
                    if(taille==0) return -1;
                    if(*tab==val) return taille;
                    return recherche_recur(tab+1, taille-1, val);
                }

                Comme je t'ai dit il n'y a pas de boucle. Fait en bon usage !


                Pour les Warnings il faut les activer dans les options du compilateur. (sous gcc au minimum -Wall -Wextra).
                D'accord je te remercie, c'est la première fonction récursive que j'écris en c, et j'avais déjà du mal avec la récursivité en python.

                Je vais essayer de m'entrainer plus pour mieux maitriser le sujet !



                • Partager sur Facebook
                • Partager sur Twitter
                  17 mars 2022 à 18:11:30

                  @rouIoude:
                  Es-tu certain que ton code fonctionne? Qu'est-ce que ça donne si la valeur est dans le dernier? Est-ce que taille ne vaut pas 1 alors?
                  Voici ma solution:
                  -
                  #include <stdio.h>
                  int re(int tab[], int taille, int val, int i) {
                      if(i>=taille) return -1;
                      int it= -1;
                      if(tab[i]==val)
                          it = i;
                      int j = re(tab, taille, val, i+1);
                      if(it>j) return it;
                      return j;
                  }
                  int main(void) {
                      int tab[6]={1, 2, 3, 2, 4, 6};
                      printf("%d\n", re(tab, 6, 6, 0));
                  }

                  -
                  Edité par PierrotLeFou 17 mars 2022 à 18:25:27

                  • Partager sur Facebook
                  • Partager sur Twitter

                  Le Tout est souvent plus grand que la somme de ses parties.

                    17 mars 2022 à 18:30:19

                    PierrotLeFou a écrit:

                    @rouIoude:
                    Es-tu certain que ton code fonctionne? 

                    Tu as raison, il l'a fait à l'envers !

                    Edit : Il marche, mais il faut faire 

                    #include <stdio.h>
                    
                    int recherche_recur(int tab[], int taille, int val)
                    {
                        if(taille==0) return -1;
                        if(*tab==val) return taille;
                        return recherche_recur(tab+1, taille-1, val);
                    }
                    
                    int main(void)
                    {
                        int tab[6]= {1, 2, 5, 78, 11, 99};
                        printf("%d\n", 6 - recherche_recur(tab, 6, 1));
                        return 0;
                    }

                    reEdit :

                    Je rajoute une fonction pour corriger le défaut :

                    #include <stdio.h>
                    
                    int recherche_r(int tab[], int taille, int val)
                    {
                        if(taille==0) return -1;
                        if(*tab==val) return taille;
                        return recherche_r(tab+1, taille-1, val);
                    }
                    
                    int recherche_recur(int tab[], int taille, int val)
                    {
                        return taille-recherche_r(tab, taille, val);
                    }
                    
                    int main(void)
                    {
                        int tab[6]= {1, 2, 5, 78, 11, 99};
                        printf("%d\n", recherche_recur(tab, 6, 99));
                        return 0;
                    }

                    -
                    Edité par rouIoude 17 mars 2022 à 18:43:50

                    • Partager sur Facebook
                    • Partager sur Twitter
                      17 mars 2022 à 19:51:11

                      Dans la fonction récursive, ligne 22, il faut supprimer le int (qui crée une variable locale), sinon la variable retournée (qui est celle déclarée ligne 12) ne sera pas modifiée.... et qui vaudra n'importe quoi. Et je ne suis pas sur que cette fonction soit correcte.

                      Edit: bon, j'ai pas lu tous les posts, désolé si ça a été dit

                      -
                      Edité par edgarjacobs 17 mars 2022 à 19:54:18

                      • Partager sur Facebook
                      • Partager sur Twitter
                        18 mars 2022 à 0:19:02

                        Yanissb a écrit:
                        > J'ai eu comme consigne d'écrire une fonction récursive permettant d'obtenir le plus grand indice où apparait une valeur dans un tableau d'entier ou de renvoyer -1.
                        Le plus grand indice? Alors, pourquoi ne pas partir de la fin? Ce sera plus facile.
                        -
                        #include <stdio.h>
                        int rechercheRecursive(int tableau[], int taille, int valeur) {
                            if(--taille < 0)  return -1;
                            if(tableau[taille] == valeur)  return taille;
                            return rechercheRecursive(tableau, taille-1, valeur);
                        }
                        int main(void) {
                            int tableau[6]={1, 2, 3, 2, 4, 6};
                            printf("%d\n", rechercheRecursive(tableau, 6, 2));
                        }
                        • Partager sur Facebook
                        • Partager sur Twitter

                        Le Tout est souvent plus grand que la somme de ses parties.

                          18 mars 2022 à 1:04:27

                          Bonjour,

                          on peut même imiter un divide&conquer :

                          #include <stdio.h>
                          
                          int maxi(size_t size, int array[size], int value);
                          
                          int main(void)
                          {
                              int array[]= {1,2,5,78,11,99,2,0};
                              size_t size=sizeof array/sizeof *array;
                          
                              printf("array = [ ");
                              for(size_t i=0; i<size; i++) {
                                  printf("(%zu):%d ", i, array[i]);
                              }
                              printf("]\n");
                          
                              for(size_t i=0; i<size; i++) {
                                  printf("maxi(%d) = %d\n", array[i], maxi(size, array, array[i]));
                              }
                              printf("maxi(%d) = %d\n", 1000, maxi(size, array, 1000));
                          
                              return 0;
                          }
                          
                          
                          int maxi_r(size_t from, size_t to, int array[], int value);
                          
                          int maxi(size_t size, int array[size], int value)
                          {
                              return maxi_r(0, size, array, value);
                          }
                          
                          int maxi_r(size_t from, size_t to, int array[], int value)
                          {
                              if (from+1==to) {
                                  return array[from]==value?(int)from:-1;
                              } else {
                                  size_t mid=from+(to-from)/2;
                                  int right=maxi_r(mid, to, array, value);
                                  if (right!=-1) {
                                      return right;
                                  }
                                  return maxi_r(from, mid, array, value);
                              }
                          }
                          

                          on «divise» le tableau en 2 on cherche d'abord la partie droite puis, si on ne trouve rien, la gauche … je donne ça juste pour montrer un peu autre chose (et l'on peut être encore plus créatif ^_^).



                          • Partager sur Facebook
                          • Partager sur Twitter
                            18 mars 2022 à 1:33:10

                            @White Crow:
                            J'aime bien ...
                            Je me suis mêlé les pinceaux au début (il m'arrive de mélanger droite et gauche ...)
                            Effectivement, il faut commencer par la droite (et la droite de la droite ...)
                            J'avais trouvé un algo semblable pour rechercher le maximum d'un tableau.

                            On pourrait suggérer la méthode itérative en commençant par la fin du tableau

                            int i;

                            for(i=taille-1; i<=0; i--)

                            et on sort dès qu'on a trouvé

                            -
                            Edité par PierrotLeFou 18 mars 2022 à 2:01:47

                            • Partager sur Facebook
                            • Partager sur Twitter

                            Le Tout est souvent plus grand que la somme de ses parties.

                            Fonction récursive et segmentation fault

                            × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                            • Editeur
                            • Markdown