bonjour je suis entrain de faire un exo ou l'on m'assigne d'utiliser une fonction recursive pour rechercher si un entier tape par l’utilisateur se trouve sur le tableau entre un indice de depart et un indice de fin du tableau tape aussi par l'utilisateur. J'ai utilise une fonction void et ensuite j'ai cree un boolean mais je ne sais pas si j'ai repondu a la question a savoir utiliser une fonction recursive...sinon comment je peux resoudre l'exo en utilisant une fonction recursive proporement.

voici le code:

<

-
Edité par rcypher179 25 mai 2019 à 19:37:58

Hello !

Ou est le code ?

Merci d'utiliser la balise de code (&lt/>) pour afficher du code.

Je ne vois pas l'appel récursif, où est-il ? Sais-tu ce qu'est une fonction récursive ? Ta boucle while devrait être remplacé par if + appel récursif.

rebonsoir

jo_link_noir mon probleme c'est que je ne sais pas comment faire appel recursif de la fonction en sachant que j'ai un bollean.

le code il marche bien mais c une fonction void et moi je voudrais utiliser la recursivite.

voici le code:

<

#include <iostream>
using namespace std;
#include<array>

const int TAILLE=10;
void remplirTableau(array<int,TAILLE>&tab )
{
    for(int i=0;i<TAILLE;i++)
    {
    tab[i]=rand()%(6-1)+1;
    }
    for(int i=0;i<TAILLE;i++)
    {
    cout<<"tab["<<i<<"]="<<tab[i]<<endl;
    }

}

void rechercherTabEntreDeuxIndices(array<int,TAILLE> &tab, int valeur, int indiceDepart, int indiceFin)
{
bool trouve=false;
int i=indiceDepart;

while(i<indiceFin and not trouve)
{
    if(tab[i]==valeur)
    {
    trouve=true;
    }
    else
    {
    i++;
    }
}
if(trouve)
{
    cout<<"vrai";
}
else
{
    cout<<"faux";
}

}


int main()
{

    int v, debut, fin;

 
    array<int,TAILLE>tab;

    remplirTableau(tab);


    cout<<"Valeur : ";
    cin>>v;
    cout<<"Entrer indiceDebut : ";
    cin>>debut;
    cout<<"Entrer idiceFin: ";
    cin>>fin;

    rechercherTabEntreDeuxIndices(tab,v,debut,fin);


    return 0;
}>

-
Edité par rcypher179 24 mai 2019 à 20:31:24

Bonjour rcypher179

Une fonction récussive, c'est une fonction qui s'appelle elle même:

typeretour foo (param)
{
    if (condition) {
        faire quelque chose;
        valRetour = foo (parametre modifié);
        faite autre chose;
        return (valeurDeSortie);
     } else {
        return (Autre chose encore)
    }
}

comme tu le vois, la fonctions foo s'appelle elle même à chaque fois, et dès qu'on atteints la première fois la condition "fause", on dépile tous les appel qui se sont empilé.
L'exercice que l'on te demande, c'est de remplacer les boucles "FOR", par des appel a une fonction qui fait une action, et s'appelle elle même pour faire les autres actions qui suivent.

-
Edité par Dedeun 25 mai 2019 à 9:29:47

Bonjour Dedeun

Ok je comprends ce que tu dis la sauf quand tu me parles de la boucle for. Deja dans l'exercice le tableau est suppose etre deja rempli. C'est moi qui l'ai rempli juste pour tester mon code avec le programme principal.

Ce que tu as ecris la aussi est une fonction non-void qui fait un return. Donc pour reussir mon code je dois changer le type de ma fonction void a non-void ????

L'explication que je veuille c'est comment utliiser le boolean que j'ai la en haut avec la récursivité???est ce possible????Sinon de quelle facon je peux reecrire le code pour faire appel a la recursivite????

Hello,

Il n'y a pas de lien entre une fonction qui retourne un booléen / une procédure void et puis la récursivité; Déjà,  : Ces 2 fonctions sont équivalentes!

bool foo (param)
{
    travail...

    bool ret = ???;

    return (ret);
}

et

void foo (param; bool & ret)
{
    travail...

    ret = ????;
}

On est d'accord ?

Si on est d'accord, on continue, si non dit le moi!

Donc je comprends que c'est ta procédure rechercherTabEntreDeuxIndices (tab,v, debut,fin) qu'il faut rendre récurcive.

(D'ailleur, il serait sûrement bon quelle retourne un booleen, qui dit si elle a trouvé ou pas !, non, tu crois pas? Sinon, comment va tu exploiter que tu a trouvé ou pas ? le "if(trouve) { cout<<"vrai"; } else {  cout<<"faux"; }"c'est pas optimal! Il serait peut être mieux dans le main (), parce que si un jour tu veux réutiliser ta procédure pour faire le test pour une autre action que d'écrire à la console (un test avant d'ajouté un élément de ton tableau par exemple) ta procédure elle est déjà écrite, et testé,  pas besoin de la réécrire! Mais là, c'est pas un problème de la récursion! Donc ta procédure pourrait être :

bool rechercherTabEntreDeuxIndices(array<int,TAILLE> &tab, int valeur, int indiceDepart, int indiceFin)
{
 .....
  return (trouve);
}

Une procédure récursive, c'est fait pour remplacer une boucle. Tu remplaces une fonction "avec une grande étendu de donnée", par une petite action simple + l'appel de cette même procédure avec "une étendu de donnée un peu plus petite", et un tests qui dit que c'est finit et qu'il ne faut plus appeler la procedure.

Donc, il faut que tu fasse une procedure rechercherTabEntreDeuxIndices (tab,v, debut,fin), qui fait une petite action (un test), s'appelle elle même (mais pas exactement avec les mêmes arguments) et qui a aussi une condition d’arrêt (sûrement en vérifiant les arguments qu'on lui passe)

Dit moi si tu comprends ce que je te dits.

Je te laisse chercher un peu ... Aller, Hop! Au travail!

-
Edité par Dedeun 25 mai 2019 à 18:17:16

Hello Dedeun,

J'ai compris et j'ai pas compris...

donc ce que j'ai compris dans ce que tu as dit c je peux pas utiliser une fonction void pour faire une boolean recursif...

je vais mettre le "a faire" dans le if au niveau du main ca aussi j'ai compris

ce que j'ai pas pige c'est:

si je dois faire appel a la fonction ce sera quoi exactement avec les 4 parametres que j'ai.

genre  je dois etablir la condition et ensuite faire un 'return rechercherTabEntreDeuxIndices (tab,v, debut,fin);' ou quoiii ? comment je dois faire cette condition sachant que j'ai fait un bool trouve;

mon probleme c comment exprimer le boolean avec les conditions que je dois verifier jusqu'au return.

pourtant je viens de faire un autre exercice celui ci en dessous avec la recursivite et je l'ai resssi mais je ne comprends pas celui d'en haut avec le boolean.

Exercice
Soit la suite (un) définie ainsi :

Un =1 si n = 0
Un =0 si n = 1
Un = U(n-1) + 2*U(n-2)

Écrire la fonction récursive suiteRec correspondant à la définition précédente.

<

#include <iostream>
using namespace std;

int suiteRec(int n)
{
    if (n==0)
    {
        return 1;
    }
    else if (n==1)
    {
        return 0;
    }
    else
    {
        return suiteRec(n-1 ) + 2*suiteRec(n-2);
    }
   
}

int main()
{
    int n;

    cout<<"Entrer un entier n: ";
    cin>>n;
    cout<<"La suite 'SuiteRec' donne "<<suiteRec(n);


    return 0;
}>

-
Edité par rcypher179 25 mai 2019 à 19:36:32

Donc On ne se comprend pas:

Je t'ai écrit: "Il n'y a pas de lien entre une fonction qui retourne un booléen / une procédure void et puis la récursivité!", donc je te confirme et te le redis: Il n'y a aucun lien!

Maintenant, si tu veux utiliser une fonction qui retourne un booléen, libre à toi, il y a pas de PB!

Donc le prototype de ta fonction sera:

bool rechercherTabEntreDeuxIndices(array<int,TAILLE> &tab, int valeur, int indiceDepart, int indiceFin)

Il faut que écrive de façon récursive ta boucle while ()!

Cette fonction doit:

• si on n'est pas à la fin du tableau
•   Vérifier si l’élément du tableau actuel vaut la valeur cherchée
•   si oui retourner qu'on a trouvé
•   si non, parcourir le reste du tableau et retourner si la valeur se trouve dans le reste du tableau
• si on est à la fin du tableau, retourné qu'on a pas trouvé

Dedeun, rebonsoir

et merci pour le temps et les efforts que tu fais pour que je comprenne

je comprends ce que tu dis donc...on ne peut pas utiliser un boolean avec la recursivite de meme qu'en en etablissant une boucle while avec la récursivité.

Si tel n'est pas l cas comment je pourrai balayer le tableau pour trouver la valeur 'valeur' entree par l'utilisateur?Par un for?????

Pour plus simple et que je comprenne mieux peux tu me resoudre l'exercice en ta façon. C'est a partir de la ou je pourrai voir ou mon erreur se situe et mieux comprendre.

sinon regarde cette boucle for que j'ai remplacee au while pour me dire si c bon...sauf que le probleme c'est que je ne crois pas qu'elle est recursive...

<

bool rechercherTabEntreDeuxIndices(array<int,TAILLE> &tab, int valeur, int indiceDepart, int indiceFin)
{
bool trouve=false;
for(int i=indiceDepart; i<indiceFin; i++)
{
    if(tab[i]==valeur)
    {
    trouve =true;
    }
    else
    {
    trouve=false;
    }

} >

return trouve;

Est ce que cette fonction est recursive???????

-
Edité par rcypher179 25 mai 2019 à 23:18:46

rcypher179 a écrit:

... Pour plus simple et que je comprenne mieux peux tu me resoudre l'exercice en ta façon. C'est a partir de la ou je pourrai voir ou mon erreur se situe et mieux comprendre....

Non! C'est ton exercice pas le mien!
Mais en fait je l'ai déjà fait, je t'ai donné l'algo, dans mon post précédent. Tu as déjà la solution!

Cette fonction doit:

• si on n'est pas à la fin du tableau
•   Vérifier si l’élément du tableau actuel vaut la valeur cherchée
•   si oui retourner qu'on a trouvé
•   si non, parcourir le reste du tableau et retourner si la valeur se trouve dans le reste du tableau
• si on est à la fin du tableau, retourné qu'on a pas trouvé

rcypher179 a écrit:

... sinon regarde cette boucle for que j'ai remplacée au while pour me dire si c bon...sauf que le probleme c'est que je ne crois pas qu'elle est recursive...

En effet, à la place de ta boucle "while" tu as une boucle "for", mais dans les 2 cas, ce n'est pas récursif. Pour être récursif, il faut que ta procédure rechercherTabEntreDeuxIndices s'appelle elle même avec des arguments modifiés. Ce n'est pas le cas, donc ce n'est pas récursif.

Bon allez au travail! (Courage)

PS: Quand tu mets du code sur le forum, utilise le bouton </>, c'est plus clair.

-
Edité par Dedeun 26 mai 2019 à 8:32:28

Hello,

Une fois sur ordi je vois le code, mais franchement, fait un effort de mise en forme.

Ce que Dedeun dit, est que ta fonction doit s’appeler elle même.

Quand tu fait une fonction recursive, tu doit pouvoir t’arrêter a un moment, il faut donc le prendre en compte.

Les fonctions recursives sont très simple, et permettent de résoudre des problèmes facilement, tel que le parcours d'arbre.

Bonjour,

Merci d'utiliser la balise code

Les forums d'Openclassrooms disposent d'une fonctionnalité permettant de colorer et mettre en forme les codes source afin de les rendre plus lisibles et faciles à manipuler par les intervenants. Pour cela, il faut utiliser le bouton de l'éditeur, choisir un des langages proposés et coller votre code dans la zone prévue. Si vous utilisez l'éditeur de messages en mode Markdown, il faut utiliser les balises <pre class="brush: cpp;">Votre code ici</pre>.

Rebonjour

Est ce correct comme ca ????Et j'ai toujours du mal a utiliser vos balises. Le codde ne s'affiche jamais correctement

-
Edité par rcypher179 26 mai 2019 à 15:18:17

Non, ton code (mise en forme) est encore affreux.

Conseil, oublie les variables, n'utilise que des constantes, et pas de boucle.

-
Edité par necros211 26 mai 2019 à 15:34:08

Ici, l’intérêt d'une récursion est de réduire l'espace de recherche. Si le tableau n'est pas trié, l'intérêt est quasiment nul, par contre si il est trié, tu obtiens une recherche dichotomique qui est très efficace. L'idée c'est que rechercher dans un tableau de taille n revient à rechercher dans le sous tableau qui contient la première moitié du tableau d'entrée puis dans le sous tableau qui contient la deuxième moitié si tu n'as pas trouvé dans la première moitié. A chaque récursion tu divises la taille de l'espace de recherche par 2. Si le tableau est trié, les mathématiques nous disent que le nombre de récursions pour dire si l'élément est présent ou pas dans le tableau sera de l'ordre de ln(n). Or la fonction ln(logarithme néperien) est une fonction dont la croissance est très aplatie, en gros elle suit, le facteur des puissances de 2, c'est à dire que tu pourras répondre en environ 10 comparaisons sur un tableau de 1000 éléments (2^10 = 1024), au lieu de 1000 comparaisons avec une recherche séquentielle (un bête for). 

C'est une technique particulièrement intéressante à connaître, mais elle n'est pas forcément la panacée non plus. Une récursion possède un coût machine qui n'est pas négligeable. Sur un tableau de 1000000000 d'éléments ce sera rentable presque à coup sûr, sur un tableau de 100000 éléments, le séquentiel sera probablement plus rapide.

necros211

Comment je pourrai parcourir l tableau sans utiliser de boucle ????

Est-ce que par hasard tu n'aurais pas oublié, dans l'énoncé, qu'il faut chercher si un nombre se trouve dans un tableau ordonné ?

@int21 :  fais des tests pour comparer.  Et si on écrit une fonction comme la rechercher dichotomique sous forme récursive, le coimpilateur gcc est assez malin pour détecter une récursion terminale, et la transformer en boucle.

-
Edité par michelbillaud 26 mai 2019 à 15:47:33

int21h

Je ne suis pas trop avance en C++ au point de comprendre ce que tu dis vraiment desole !J'ai un bas niveau

michelbillaud

L'element a chercher on doit voir si ca se trouve dans le tableau entre 2 indice du tableau que l'utlisateur va auss entrer. On ne m'a pas parle de tri ni de ordonee.

exemple de deroulement du programme.

tab[0]=2
tab[1]=3
tab[2]=5
tab[3]=1
tab[4]=5
tab[5]=5
tab[6]=4
tab[7]=4
tab[8]=3
tab[9]=5
Valeur : 1
Entrer indiceDebut : 2
Entrer idiceFin: 5

Et la ma fonction recursive va retourner vrai(1) si 1 se trouve entre t[1] et t[4] et faux(0) sinon.

-
Edité par rcypher179 26 mai 2019 à 15:49:37

rcypher179 comment font les langages comme Haskell pour ne pas avoir de boucles ? ;) 

Un appel récursif est comme une boucle, tu peux traduire n'importe quelle boucle en récursif, l'inverse est probablement vrais.

rcypher179 a écrit:

Est ce correct comme ca ????Et j'ai toujours du mal a utiliser vos balises. Le codde ne s'affiche jamais correctement

Si seulement tout ceci était expliqué dans les règles d'utilisation du forum ... Oh wait.

necros211 a écrit:

rcypher179 comment font les langages comme Haskell pour ne pas avoir de boucles ? ;) 

Un appel récursif est comme une boucle, tu peux traduire n'importe quelle boucle en récursif, l'inverse est probablement vrais.

Oui, en introduisant une représentation de la pile, d'une façon ou d'une autre.

rcypher179,

Dans une procédure récursive, il ne faut pas de boucle.

Dans ton cas, il faut que tu ne tests qu'une case de ton tableau, et pour les autres cases, dans ta fonction tu rappelles ta fonction avec l'indice suivant du tableau comme début, et toujours le même indice de fin. Et tu fais ça que jusqu'a ce que l'indice du début est égale à l'indice de fin.

C'est plus clair comme Ca ? Relit l'algo que je t'avais donné ...

(PS: Au dessus du carré ou tu tappe tes remarques, il y a plein de bouton Gras, Italique, couleur, ... il y en a un qui est comme çà: </>. C'est celui là qu'il faut utiliser pour mettre du code sur le forum.

C'est pas qu'il ne faut pas de boucle, mais qu'il faut se poser les questions de façon différente : Comment ramener le traitement d'un truc à celui d'un truc plus petit.

Exemple, dans une recherche par dichotomie, chercher dans le tableau, ça se ramène à chercher dans sa moitié gauche. Ou droite. Selon que.

Bon Merci pour vos interventions tous autant que vous etes specialement a Dedeun ....Vous avez fait du temps pour moi et je vous suis reconnaissant.

Je vais patienter jusqu’à la semaine prochaine et poser des questions au prof pour qu'il m'explique plus la récursivité.

J'essaie de comprendre vos explications mais c trop dur pour quelqu'un qui a un niveau bas en programmation, qui vient de commencer cette leçon et en plus du francais trop lourd que vous employer etant donne qu c pas ma langue. 

Merci pour tout et bonne chance pour la suite.

Salut,

Une fonction récursive, c'est une fonction qui s'appelle elle-même, ce qui va occasionner "une certaine sorte" de boucle.

Le problème est alors que chaque appel de la fonction va nécessiter de placer "quelques données" dans ce que l'on appelle la "pile d'appels" (la "stack") et que, si on effectue suffisamment d'appels à la fonction, cela va finir par saturer cette pile d'appels, et provoquer une erreur de type stack overflow (dépassement de pile).

De plus, la fonction que tu dois créer est -- très clairement -- destinée à rechercher "quelque chose".  Tu t'attend donc forcément à ce qu'elle renvoie un résultat du type "j'ai trouvé" ou "j'ai pas trouvé".  Et, si tu ne fais pas en sorte que la fonction finisse "tôt out tard" par renvoyer cette information, la fonction pourrait s'effectuer  (s'il n'y avait pas le problème de dépassement de pile) jusqu'à la fin des temps, que cela lui irait encore très bien.

La première chose que tu dois faire, c'est déterminer ce que l'on appelle le "cas de base".  C'est le cas dans lequel la fonction ne va pas être appelée une fois de plus.

Ton problème comporte en réalité deux cas de base:

• Soit la valeur recherchée a été trouvée (soyons précis : si l'élément que tu testes dans ton tableau correspond à la valeur que tu cherches), et tu dois donc renvoyer "j'ai trouvé" (ou ce qui en tient lieu).
• Soit tu n'a plus aucune chance de trouver la valeur recherchée, et tu dois donc renvoyer "je n'ai pas trouvé" (ou ce qui en tient lieu)

Après, la manière dont tu indique ces deux possibilités dépend exclusivement de toi et de tes besoins, car tu peux décider de renvoyer

• un booléen égal à true si l'élément est trouvé et à false si l'élément n'est pas trouvé
• la valeur recherchée si elle est trouvée, une valeur "connue pour être invalide" (ex : 0xFFFFFFFF) si elle n'est pas trouvée
• l'indice à laquelle se trouve la valeur, un indice "connu pour etre invalide" (ex :  n'importe quelle valeur plus grande que la taille du tableau) si elle n'est pas trouvée
• l'itérateur sur la valeur recherchée si elle est trouvée, l'itérateur renvoyé par la fonction end en si elle n'est pas trouvée
• j'en passe, et sans doute de meilleures

Une fois que tu auras décidé la forme que prendra le retour de la fonction, tu pourras commencer à écrire ta fonction.  La règle est simple : on teste le(s) cas de base en tout début de la fonction.  Ainsi, ta fonction prendra une forme proche de

TYPE find(/* les paramètres nécessaires */){
   if(valeur trouvée)
       return "j'ai trouvé";
   if(valeur inexistante)
       return "je n'ai pas trouvé;
   /*le reste */
}

Et le commentaire que j'ai indiqué comme étant "le reste" va correspondre à la partie réellement récursive de la fonction, qui n'a qu'un seul but, qui est de ... mener progressivement la fonction vers l'un des deux cas de base que nous venons de voir.