C - Fonction récursive pour max d'un tableau

[FBMeca]

Bonjour à tous,

J'ai commencé à apprendre le langage C il y a quelques mois, donc je suis encore un débutant.

On me demande d'implémenter une fonction int max(int n, int* t) de manière récursive. Cette fonction doit prendre en argument un tableau d’entiers et la taille de ce tableau, et retourner la valeur maximale de ce tableau.

Je crois comprendre la logique, mon idée est la suivante : je pourrais peut-être, tout en décrémentant la valeur de n, comparer deux tableaux, celui qu'on a de base, t[n], et le tableau t[n-1]. Ce que je ferais donc est que j'appellerais la fonction de cette manière.

Il me faut une condition de terminaison : le moment où je compare plus un tableau avec un autre tableau, mais deux valeurs. A ce moment là, je retourne le plus grand des deux.
Ainsi, en "remontant" toute la chaîne des rappels récursifs, je pense que ca devrait jouer ?

Bon, maintenant la partie difficile est de mettre ca en code, mais j'ai beaucoup de mal à le faire (pas seulement pour celle-ci, mais les fonctions récursives en général). Je comprends quand je vois en code, mais en faire un tout seul ça me surpasse..
Les fonctions récursives je ne les trouve pas très intuitifs non plus, mais j'ai vraiment envie de bien comprendre la logique, et surtout bien m'entraîner pour m'y habituer.

Si quelqu'un pouvait m'aider à m'expliquer la chose un peu plus clairement, car je crains que ce que j'ai maintenant est globalement correct, mais ne va pas me suffir.

Merci d'avance à tous!
-----

[pm42]

Si je te donne un tableau t, tu prends son 1er élément t[0]. Puis tu calcules le max du tableau hors le 1er élément, t[1...n]
Quel est le maximum de t ?
Si t est de taille 1, quel est son maximum ?

Pour coder du récursif, le plus simple est souvent de d'écrire les choses mathématiquement.
Dans ton cas, cela donne :

max(t) = le plus grand entre t[0] et max(t[1..n]) si longueur(t) > 1
max(t) = t[0] si longueur(t) = 1

Puis tu transformes ça en code ce qui est quasiment mécanique avec un peu d'habitude.

[FBMeca]

Merci pour ta réponse.
Désolé, mais c'est toujours un peu flou.

Le début est plutôt facile :

// ma condition de terminaison

int max(int n,int t[]) {
if (n==1) {
return t[0] ;
}
else {
?...?

J'ai de la peine avec le else. A chaque fois j'essaie d'y réfléchir par plusieurs manières mais ça rend la chose très floue et je me perds à chaque fois... Else, je vais retourner le max(n, t[n-1]), c'est ca ?

[pm42]

Ton début est correct.

Maintenant il faut que tu apprennes comment obtenir le tableau qui contient tout sauf le 1er élément en C.
Tu devrais avoir ça facilement dans ton cours sur les pointeurs.

Sinon, il y a une autre solution mais on va déjà essayer ça.

[A voir en vidéo sur Futura]

[FBMeca]

Super.

Mais comme je l'ai dit ici "Else, je vais retourner le max(n, t[n-1]), c'est ca ?", je peux pas simplement prendre le dernier élément et prendre tout le tableau sauf le dernier ? Ca serait pas plus simple ? Donc je prends t[n-1]..

[pm42]

Super.

Mais comme je l'ai dit ici "Else, je vais retourner le max(n, t[n-1]), c'est ca ?", je peux pas simplement prendre le dernier élément et prendre tout le tableau sauf le dernier ? Ca serait pas plus simple ? Donc je prends t[n-1]..

Oui tu peux faire ça. Ce n’est pas vraiment plus simple en C mais pour un débutant c’est une solution.

[FBMeca]

Ah oui d'accord, les pointeurs ca m'est encore totalement inconnu.. Donc,

int max(int n,int t[]) {
if (n==1) {
return t[0] ;
}
else {
return max(n,t[n-1]) ;
}
Ceci fonctionnera?

[pm42]

return max(n,t[n-1]) ;
}
Ceci fonctionnera?

Non bien sur. max attend une taille et un tableau. Tu lui passes une taille qui n'a pas changé et donc ne va jamais diminuer et t[n-1] qui n'est pas un tableau.
Donc déjà, cela ne compile pas. Si cela compilait, cela ferait une boucle sans fin.

Et si cela compilait et ne faisait pas une boucle sans fin, cela se contenterait d'aller chercher le 1er élément puisque tu essaies de prendre max du sous-tableau mais sans le comparer avec l'élément que tu as retiré.

Il faut être méthodique.

[FBMeca]

Oui ca n'avait pas de sens. Bon, alors :

int max(int n,int t[]) {
if (n==1) {
return t[0] ;
}
else {
if (t[n] >max(n-1, t)) { // ici le tableau devient le tableau de départ - le t[n] ?!
return t[n] ;
}
else {
return max(n-1,t) ;
}}

Oui, je comprends qu'il faut être méthodique, mais la méthode je l'ai à peine, c'est ca le problème.. Et comment vérifier sur papier que mon truc fonctionne ? Je trace une colonne n et une autre f(n), et je regarde ce que ca donne ?

[pm42]

Ca commence à être ça.
2 choses importantes :
- le dernier élément d'un tableau de taille n n'est pas t[n] mais t[n-1]
- Si t[n-1] <= max(n-1, t), tu va avoir appelé 2 fois max(n-1, t). Tu aurais intérêt à l'appeler 1 fois, mettre le résultat dans une variable et comparer.

Cela donne :

int submax = max(n-1, t);
if(t[n-1]> submax) return t[n-1] else return submax;

Oui, je comprends qu'il faut être méthodique, mais la méthode je l'ai à peine, c'est ca le problème..

C'est normal, cela vient avec la pratique.

Et comment vérifier sur papier que mon truc fonctionne ? Je trace une colonne n et une autre f(n), et je regarde ce que ca donne ?

C'est le principe mais faire tourner un algorithme récursif ou pas à la main pour vérifier qu'il fonctionne n'est pas vraiment facile ni efficace.

Tu ne peux pas installer un compilateur C ? Sinon, tu as des sites qui te permettent de faire tourner ton code sans rien installer sur ta machine comme https://www.onlinegdb.com/online_c_compiler (et d'autres).

[FBMeca]

Ah oui c'est bête de ma part, merci!

J'ai VS Code que j'utilise à chaque fois, mais je me suis dit que l'écrire directement ici était peut-être plus pratique et rapide.
Donc avec t[n-1] au lieu de t[n] ça fonctionne non? Je vais essayer ça en créant un petit programme main!

[pm42]

Donc avec t[n-1] au lieu de t[n] ça fonctionne non?

Oui.
Pour l'ensemble du programme, il faut que tu essaies : être sur qu'un truc fonctionne sans tester est très, très difficile.

[FBMeca]

Oui oui, tout à fait, mais je m'assure de la chose pour être certain

Merci!

[polo974]

Bonjour à tous,

J'ai commencé à apprendre le langage C il y a quelques mois, donc je suis encore un débutant.

On me demande d'implémenter une fonction int max(int n, int* t) de manière récursive. Cette fonction doit prendre en argument un tableau d’entiers et la taille de ce tableau, et retourner la valeur maximale de ce tableau.
...

Merci d'avance à tous!

Une chose est sûre, c'est que c'est à peu près le plus mauvais exemple d'application de la récursivité...

Bonne continuation pour le C...

[FBMeca]

Merci !
Justement, déjà que la récursion ce n'est pas un concept trivial, le max d'un tableau ça l'est encore moins.
Auriez-vous certains exemples intéressants que je pourrais essayer de faire ? J'ai déjà vu la somme d'entiers, le calcul d'un factoriel, et c'est un peu tout..

[Jack]

Ahhh, les tours de Hanoï ... Ma madeleine de Proust.

[FBMeca]

Orgh non, quelqu'un a une autre idée ?

[Jack]

La fonction prend 3 ou 4 lignes

[pm42]

Une chose est sûre, c'est que c'est à peu près le plus mauvais exemple d'application de la récursivité...

Cela peut être intéressant pour découvrir les limites de la récursivité si on a un grand tableau puis d'essayer de l'écrire en récursivité terminale puis de comparer la vitesse avec une boucle.
Mais par pour un débutant en effet.

Sinon, Fibonacci est facile à implémenter et ensuite, on essaie Ackermann : https://fr.wikipedia.org/wiki/Fonction_d%27Ackermann

[Jack]

Une fonction récursive pour calculer le min d'un tableau

[polo974]

Une fonction récursive pour calculer le min d'un tableau

allez, soyons fous: trier le tableau à condition de remplir/parcourir un arbre binaire...

[inviteaacf0517]

Bonjour,
voici la fonction reccursive qui nous permettent de determiner le max d'un tableau :

#include<stdio.h>
#define mx 50 
int max(int T[mx],int n);
main ()
{
	int T[mx],n,i;
	printf("Entrer La taille du tableau\n");
	scanf("%d",&n);
	for (i=0;i<n;i++)
	{
		printf("T[%d]=",i);
		scanf("%d",&T[i]);
	}
	printf("Le max de ce tableau est %d ",max(T,n));
}
int max(int T[mx],int n)
{
	int m=T[n-1];
	if(n==1)
	{
		return T[0];
	}
	if (m<=T[n-2])
	{
		return max(T,n-1);
	}
	else 
	{
		return m;
	}
}