Version imprimable
Bonjour !
Soit une fonction récursive définie comme suit :
Quelle est la solution itérative pour cette fonction?Citation:
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
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. :roll:
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.
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
@Prof
Merci pour ces explications. Ma réponse était précipitée. :oops: