Bonjour/bonsoir

Je suis entrain de voir la récursivité au cours de programmation et pour comprendre et faire qlq exercices,je me suis inspiré des exemples sur cette page -> https://openclassrooms.com/forum/sujet/la-recursivite-en-c-25836(Je viens tjrs sur openclassrooms pour compléter mon cours).

Je me suis donc lancé dans le tout premier exemple sur les produits expliqué sur la page, je l'ai un peu poussé plus loin (rien de foufou) et je me suis fais un petit code perso..

Mais il refuse de fonctionner et je ne comprend pas pourquoi..

Fin, c'est ma fonction produit() qui plante le prg..

Lorsque je court-circuite la fonction, mon main affiche bien les résultats attendu..

Je vous mets mon code, si une bonne âme pouvait me pointer l'erreur que je fais??

/*
Fonction recursive : produit
*/

/* LIBRAIRIE */
#include "stdlib.h"
#include "stdio.h"

int produit(int x, int y) {
	return produit(x - 1, y) + y;
}

int main(int argc, char *argv[]) {

	/* DECLARATION VARIABLE(S) ET CONSTANTE(S) */

	int a = 0;
	int b = 0;
	int x = 0;
	int y = 0;

	/* CODE */
	printf("Exercice langage c sur la recursivite -> Produit\n");
	printf("entrer 2 nombres :\n");
	printf("-> ");
	scanf("%d", &a);
	printf("-> ");
	scanf("%d", &b);

	if (a > 0 && b > 0) {
		if (a > b) {
			y = a;
			x = b;
		} else if (b >= a) {
			x = a;
			y = b;
		}
	printf("%d * %d = %d\n", a, b, produit(x, y));
	return 0;
	} else {
		printf("%d * %d = 0\n", a, b);
		return 0;
	}
}

 Merci

-
Edité par Dunkhan 18 février 2017 à 18:30:06

Salut,

• Tu n’as mis aucun cas terminal à ta fonction produit. ici, les cas terminaux devraient être x = 0 et x = 1. C’est sûrement ce qui cause ton erreur.
• De cette manière, tu ne gères pas les multiplications si x est négatif. Pour changer cela, il suffit de faire -produit(-x, y) si x est négatif.
• Utilise int main(void) si tu n’as pas besoin des arguments de main.

Salut,

Merci pour les conseilles.

J'ai repris mon code et je suis repartis de tes conseils, et aussi en suivant un peu plus "à la lettre" l'exemple montrer sur la page..

Apparemment c’était bien le problème de ma fonction qui ne renvoyait pas le cas terminal..

Pour ce qui est des cas négatifs.. est ce que cela veut dire que je dois faire 2 fonctions?? je pense que la réponse est oui.. et je pourrais le faire, mais du coup, il faut aussi que je prévois le cas ou y est aussi négatifs??

Le

int main(int argc, char *argv[])

vient directement du cours sur le c.. qu'est ce que cela change exactement??

ok.. j'ai ma réponse.. j'ai plus qu'a lire^^

http://tdinfo.phelma.grenoble-inp.fr/2Aproj/fiches/prototype_main.pdf

/*
Fonction recursive : produit
*/

/* LIBRAIRIE */
#include "stdlib.h"
#include "stdio.h"

int produit(int a, int b) {

	// Variable
	int x;
	int y;

	// Pq c'est moins "cher" de multiplier par le plus petit nombre
	if (a > 0 && b > 0) {
		if (a > b) {
			y = a;
			x = b;
		} else if (b >= a) {
			x = a;
			y = b;
		}
		return produit(x - 1, y) + y;
	}
	// Si l'un des nombres vaut zéro
	else {
		return 0;
	}
}

int main(void) {

	/* DECLARATION VARIABLE(S) ET CONSTANTE(S) */

	int a;
	int b;


	/* CODE */
	printf("Exercice langage c sur la recursivite -> Produit\n");
	printf("entrer 2 nombres :\n");
	printf("-> ");
	scanf("%d", &a);
	printf("-> ");
	scanf("%d", &b);
	printf("%d * %d = %d\n", a, b, produit(a, b));
	return 0;

}

Encore merci de prendre le temps

-
Edité par Dunkhan 18 février 2017 à 22:55:12

Dunkhan a écrit:

// Pq c'est moins "cher" de multiplier par le plus petit nombre

Si tu veux réduire la complexité de ta fonction, le moyen le plus simple serait d'utiliser la formule \(x \times y = (x - 1) \times (y - 1) + x + y - 1\). Ce qui te donnerait, en C:

unsigned int
product_u(unsigned int x, unsigned int y)
{
    if (x == 0 || y == 0)
    {
        return 0;
    }

    return product_u(x - 1, y - 1) + x + y - 1;
}

Dunkhan a écrit:

Pour ce qui est des cas négatifs.. est ce que cela veut dire que je dois faire 2 fonctions?? je pense que la réponse est oui.

C'est une bonne idée. Tu as une fonction qui implémente la multiplication pour les entiers non-signés, tu peux l'utiliser pour en faire une qui multiplie les entiers signés.

-
Edité par Mad scientist 19 février 2017 à 0:10:12

Mad scientist a écrit:

Dunkhan a écrit:

// Pq c'est moins "cher" de multiplier par le plus petit nombre

Si tu veux réduire la complexité de ta fonction, le moyen le plus simple serait d'utiliser la formule \(x \times y = (x - 1) \times (y - 1) + x + y - 1\). Ce qui te donnerait, en C:

unsigned int
product_u(unsigned int x, unsigned int y)
{
    if (x == 0 || y == 0)
    {
        return 0;
    }

    return product_u(x - 1, y - 1) + x + y - 1;
}

Rhaaaa.. ça ça fait mal^^ C'est dans ce genre de cas que je me dis qu'il faut vraiment que je reprenne des cours de math une bonne fois pour toute!!

Et je me suis permis de mettre ton tuto sur le C en marque page

-
Edité par Dunkhan 19 février 2017 à 0:53:04

Le raisonnement pour arriver à cette formule est assez simple: Il suffit de résoudre l'équation \(t = x \times y - (x - 1) \times (y - 1)\) pour trouver la valeur de \(t\). Maintenant, il existe d'autres manières de penser le problème.

On peut par exemple se dire qu'il suffit de faire une fonction qui va passer ses arguments à une fonction produit_impl, mais dans le bon ordre:

#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))

unsigned int
produit(unsigned int x, unsigned int y)
{
    return produit_impl(MIN(x, y), MAX(x, y);
}

Avec produit_impl la version corrigée (avec un prototype différent vu qu'on ne gère que les entiers positifs) de la fonction que tu présentes dans ton premier post:

unsigned int
produit_impl(unsigned int x, unsigned int y)
{
    if (x == 0)
    {
        return 0;
    }

    return produit_impl(x - 1, y) + y;
}

Il existe aussi d'autres version plus efficaces, comme celle-ci:

unsigned int
product_u(unsigned int x, unsigned int y)
{
    unsigned int acc = 0;

    for (unsigned int i = 0; i < WORD_BIT; ++i)
    {
        acc += x & 1u << i ? y << i : 0u;
    }

    return acc;
}

Avec WORD_BIT étant une macro définie dans <limits.h> par POSIX. Sa valeur est le nombre de bits qui constituent un unsigned int/int. On sait donc qu'on itère 32 fois si un unsigned int est constitué de 32 bits.

-
Edité par Mad scientist 19 février 2017 à 2:48:02

Heu.. oui.. je comprend le principe, mais c'est un peu trop haut niveau pour moi ca..

Et je suis vraiment intéressé par ca :

#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))

Comment est cela s'appelle??

Pas le #define ni le principe de macro, mais la comparaison que tu fais.. grâce au ? j'imagine

La 3ieme version est sans conteste plus efficace, mais c'est la récursivité qui m’intéresse..

" Pas le #define ni le principe de macro, mais la comparaison que tu fais.. grâce au ? "

C'est une condition ternaire.

ASW_ a écrit:

" Pas le #define ni le principe de macro, mais la comparaison que tu fais.. grâce au ? "

C'est une condition ternaire.

Merci..

Et en plus c'est expliqué dans le cours du c