IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Turbo Pascal Discussion :

Fonction produit récursive


Sujet :

Turbo Pascal

  1. #1
    Nouveau Candidat au Club
    Homme Profil pro
    Collégien
    Inscrit en
    Janvier 2017
    Messages
    1
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : Tunisie

    Informations professionnelles :
    Activité : Collégien
    Secteur : Enseignement

    Informations forums :
    Inscription : Janvier 2017
    Messages : 1
    Points : 1
    Points
    1
    Par défaut Fonction produit récursive
    Bonjour !

    Soit une fonction récursive définie comme suit :

    0)DEF FN produit(X, Y*: entier)*:entier
    1)Si X = 0 alors produit← 0
    Sinon
    si X mod 2 =0 alors
    produit← 2 * produit(X div 2, Y)
    Sinon produit ← produit(X -1, Y) +Y
    Fin si
    Fin si
    2)Fin produit
    Quelle est la solution itérative pour cette fonction?

  2. #2
    Rédacteur/Modérateur

    Avatar de Roland Chastain
    Homme Profil pro
    Enseignant
    Inscrit en
    Décembre 2011
    Messages
    4 058
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Décembre 2011
    Messages : 4 058
    Points : 15 339
    Points
    15 339
    Billets dans le blog
    9
    Par défaut
    Bonjour !

    Je ne suis pas sûr de bien comprendre l'énoncé. Si je comprends bien, le seul cas où la récursion s'arrête, c'est lorsque le premier paramètre vaut zéro, auquel cas la fonction renvoie également zéro. Donc il me semble que l'appel initial de la fonction, s'il renvoie quelque chose, renverra toujours zéro.

    Du coup la version non récursive de la fonction ne devrait pas être trop difficile à écrire.

    Mais je ne vois pas de quelle itération il est question.
    Mon site personnel consacré à MSEide+MSEgui : msegui.net

  3. #3
    Membre confirmé
    Homme Profil pro
    .
    Inscrit en
    Juin 2002
    Messages
    239
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : .
    Secteur : Enseignement

    Informations forums :
    Inscription : Juin 2002
    Messages : 239
    Points : 567
    Points
    567
    Par défaut
    Bonjour.

    J'ai quelques remarques à faire ...

    1) Tout d'abord, ce post n'a aucun rapport avec Turbo Pascal, ni avec le langage Pascal.

    Il s'agit d'une question de nature algorithmique.

    Sa place naturelle est donc dans le forum dédié à l'algorithme.
    Adresse : http://www.developpez.net/forums/f60...algorithmique/

    2) La fonction est présentée sous une forme récursive.

    Cette fonction est correcte : elle retourne 0 si X est nul, mais elle ne retourne pas 0 dans tous les cas.

    Dans cette fonction, la condition X = 0 n'est pas la condition de sortie de la fonction, c'est le test d'arrêt de la récursion.

    Après tous les appels successifs de la fonction, depuis un X quelconque, c'est la condition qui permet d'arrêter les appels en donnant une valeur explicite.
    Il faut bien comprendre que cette valeur explicite n'est pas le résultat final : c'est juste la valeur qui figure au bout de la liste des appels successifs.
    Maintenant, il faut dépiler tous les appels qui ont permis d'arriver à X=0 et construire la valeur finale, celle que retournera la fonction.

    Une image pour illustrer la récursion : quelqu'un qui plonge dans l'eau, descend jusqu'au fond, rebondit et remonte à la surface.
    Le test d'arrêt de la récursion, c'est le fond, ce qui permet de rebondir.
    Ce n'est pas le retour à la surface.

    3) Cette fonction calcule le produit de X et Y en utilisant la somme, le produit par 2 et la division par 2.

    Son intérêt n'apparaît vraiment que si on se place au niveau élémentaire des octets, où le produit par 2 ou la division par 2 se font très simplement par des décalages de bits.

    4) Ce que demande Progart est bien connu en algorithmique : il s'agit de la dérécursification d'une fonction.

    C'est-à-dire traduire une fonction ou une procédure récursive sous une forme itérative.

    Une recherche sur Internet avec "dérécursification" ou "dérécursifié" donne des tas de liens intéressants.
    Le sujet est même traité sur le site Developpez.com : http://recursivite.developpez.com/?page=page_9

  4. #4
    Rédacteur/Modérateur

    Avatar de Roland Chastain
    Homme Profil pro
    Enseignant
    Inscrit en
    Décembre 2011
    Messages
    4 058
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Décembre 2011
    Messages : 4 058
    Points : 15 339
    Points
    15 339
    Billets dans le blog
    9
    Par défaut
    @Prof

    Merci pour ces explications. Ma réponse était précipitée.
    Mon site personnel consacré à MSEide+MSEgui : msegui.net

Discussions similaires

  1. [AC-2007] Fonction Produit pour les zones de texte
    Par qltmi dans le forum IHM
    Réponses: 5
    Dernier message: 18/03/2010, 09h43
  2. fonction multi récursive
    Par Darkyl dans le forum Langage
    Réponses: 14
    Dernier message: 03/01/2010, 12h52
  3. [Turbo Pascal] Pile d'exécution pour la fonction factorielle récursive
    Par HASALGO dans le forum Turbo Pascal
    Réponses: 7
    Dernier message: 27/12/2009, 13h57
  4. Fonction produit avec group by
    Par nicoaix dans le forum Requêtes
    Réponses: 5
    Dernier message: 25/09/2008, 18h31
  5. fonction Produit Matriciel non booleen
    Par roman.nedellec dans le forum Macros et VBA Excel
    Réponses: 1
    Dernier message: 09/11/2007, 11h35

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo