Récusivité terminale ?

Version imprimable

Voir 40 message(s) de cette discussion en une page

Bonjour ,je suis un étudiant en informatique , et j'ai un projet en Lisp que je dois rendre dés la rentré prochaine.

mon projet consiste a écrire un programme qui prend en argument une liste correspondant à une fonction et renvoie #t s'il s'agit d'une récursivité terminale et #f sinon.
Attention.

j'ai commencé à écrire des fonction récursivité et récursivité terminale (ou récursivité totale ) et j'ai pris ces fonction comme si c'était une liste , ensuite j'ai défini chaque parti de la liste c'est à dire : nom de la fonction , paramètre de la fonction et le corps de la fonction . A partir de sa j'ai sélectionner les différence qu'il y a entre les deux formes de récursivité :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 (define (corp df); vu en cours (if (unpair df)'() (caddr df))) (define (unpair l) (if (pair? l)#f #t)) (define (nom df); vu en cour (if (unpair df)'() (caadr df))) (define (par df); vu en cour (if (unpair df)'() (cdadr df))) ; sauf que comme les fonction fonction sans toute differentes je n'arrive pas a ecrire un programme adapté a toute les fonction récursivé : (define (fonction df); elle renvoie le nom de la fonction dans la fonction elle même . exemple la fonction somraux " (somraux (- n 1) (+ n acc))" elle renvoie :> somraux (if (unpair df)'() (car(car(cdr(cdr( cdr(car (cdr( cdr df)))))))))) (define (rterminale df); renvoie #t si c'est terminale et si non #f. (if (equal? (fonction df)(nom df)) #t #f)) ;( ce programme ne marche que sur certain fonction simple avec un seul IF) ; j'ai fai une fonction qui vérifié si la fonction appel une fonction chapeau : (define (chap df); nom de la fonction chapeau (if (unpair df)'() (caar(cddar df )))) (define (fchap df); fonction chapeau (if (unpair df)'() (car(cadadr df )))) (define (rterm df) (if (equal? (chap df)(fchap df)) #t #f))
mais quand je teste avec une fonction recursive normal , elle renvoie error pck elle retrouve pas l'élèment choisi du coup j'essaye de supprimé cette erreur en lui disnat de renvoyé liste vide s'il trouve pas l'élement mais j'ai pas pu .

si quelqu'un peu m'aider sur ce programme , Merci à l'avance[/SIZE][/SIZE][/SIZE]

Bonjour.
Citation:
Envoyé par kbprince
Code:

1 2 3 (define (corp df); vu en cours (if (unpair df)'() (caddr df)))
Vous n'avez pas vu le 'not' ???
Code:

1 2 3 (define (corps df); pas encore vu en cours ??? (if (not (pair? df)) '() (caddr df)))
Ce n'est peut-être pas la peine de définir une fonction 'unpair' juste pour inverser le sens de 'pair?' !!!
Code:

1 2 3 4 5 6 ; sauf que comme les fonction fonction sans toute differentes je n'arrive pas a ecrire un programme adapté a toute les fonction récursivé : (define (fonction df); elle renvoie le nom de la fonction dans la fonction elle même . exemple la fonction somraux " (somraux (- n 1) (+ n acc))" elle renvoie :> somraux (if (unpair df)'() (car(car(cdr(cdr( cdr(car (cdr( cdr df))))))))))
Comment peux-tu espérer que cette fonction marche pour toutes les fonctions???
Elle est beaucoup trop câblée sur la définition de 'somraux'!
Comme tu le dis plus loin, ça ne marchera que sur certaines fonctions qui auront la même forme que 'somraux'!

Je ne suis pas sûr que ton algorithme soit le bon:
1) rechercher LA fonction dans le corps
2) vérifier si cette fonction est la fonction

Il me semble qu'il vaudrait mieux explorer (parser) le corps de la fonction et chercher s'il contient (en position fonctionnelle) une ou plusieurs occurrences de la fonction.

En gros, écrire une fonction auxiliaire:

Code:

(define (nb-occurrences fct corps) ...)

qui retourne le nombre d'occurrences de 'fct' dans la liste 'corps'.

Il est clair que cette recherche est elle-même récursive!

occurence de quoi ?

Bonjour
Merci pour votre réponse.
j
J'ai essayer de refaire mon programme avec d'autres manières :

La 1er c'est de cherche si la fonction contient une fonction chapeau , et elle marche pour toutes les fonction en récusivité terminale mais pas sur toute les fonctions en récusivité normal.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 (define (chap df); nom de la fonction chapeau (if (unpair df)'() (caar(cddar df ) ))) (define (fchap df); fonction chapeau (if (unpair df)'() (car(cadadr df ) ))) (fchap '((define (somrt n); somme de n jusqu'a n en Récursivité terminale (somraux n 0)) (define (somraux n acc); Fonction Chapeau (if (= n 0) acc (somraux (- n 1)(+ n acc)))))) somraux > (chap '((define (somrt n); somme de n jusqu'a n en Récursivité terminale (somraux n 0)) (define (somraux n acc); Fonction Chapeau (if (= n 0) acc (somraux (- n 1)(+ n acc)))))) somraux >
j'ai testé plein de fonction en terminale sa marche mais quand il s'agit de la récusité normal sa renvoi un eerruer parceque l'endroit recehrché n'existe pas dans c'est certain fonction, le programme ne peut pas continué la vérification, j'ai essayé de faire quelque comme "si le nom de la fonction chapeau n'existe pas dans la liste renvoyé une liste vie " mais sa ne marche pas .

du coup je me suis retourné sur une autre hypothese : l'accumulateur : on sait que dans une fonction en récusivité terminale l'accumulateur est repté au moin trois fois : dans les parametres , la boucle et la fonction vu que le résultat se renvoi toujour dans l'accumulateur .
j'ai fai la fusionner la focntion aplatir2 avec compter le nombre de fois ou le mot accumulateur est repété dans la fonction, donc si il repeté plus de 2 fois ( 3 et plus ) #t (terminale ) si non #f . , je sais pas commen dire au programme ( if (< cla 3) #t #f) mais sa ne marche pas aussi .
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 (define (aplatir2 e) (define (aplatir-interne e r) (if (pair? e) (aplatir-interne (car e) (aplatir-interne (cdr e) r)) (if (null? e) r (cons e r)) ) ) (aplatir-interne e '()) ) define (compter mot phrase) (if (pair? phrase) (+ (if (equal? mot (car phrase)) 1 0) ; Notez l'alternative sous l'addition! (compter mot (cdr phrase)) ) 0 ) ) (define ( cla mot df) (if (unpair df)0 (compter mot (aplatir2 df))))
Merci !

02/01/2013, 14h55
jack-ft

:tagcode:

Afin de faciliter la lecture de ton message, peux-tu l'éditer en ajoutant la balise CODE (le '#' dans la barre d'outils) et en corrigeant les erreurs de frappe?

bonjour

Bonjour
Quand je teste si la fonction possede une fonction chapeau sa donne sa pour les fonction non terminale :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
(rterm '(define (pcr n); Fibonacci " vu en cours "
    (if (< n 2)
        1
        (+ (pcr (- n 1))
           (pcr (- n 2))))))
. . cddar: expects argument of type <cddarable value>; given (define (pcr n) (if (< n 2) 1 (+ (pcr (- n 1)) (pcr (- n 2)))))
 
>  (rterm '(define (add a b) ; addition
  (if (= a 0)
      b
      (add (- a 1)(+ b 1)))))
. . cddar: expects argument of type <cddarable value>; given (define (add a b) (if (= a 0) b (add (- a 1) (+ b 1))))

mais quand il s'agit d'une fonction en recusivité terminale il répond directement #t .
#t (vrais)
#f (faux).

Re Bonjour.

Comme je l'ai précisez dans mes messages précédents, j'ai fait une fonction qui aplatir une liste ( enleve les parenthèses) et une autre qui compte le nombre occurrence d'un mot dans une liste.

j'ai fusionner ces deux fonction pour faire un fonction qui aplatit la liste puis calcule le nombre occurrence d'un mot.
En ce qui me concerne je cherche a savoir combien il y'a le mot acc (accumulateur dans la fonction) , qui est un paramètre indispensable dans une fonction en récusivité terminale.

Si ce paramêtre est cité 3 fois ou plus dans la fonction dans c'est de la récusivité terminale si non faux, j'ai fais sa en fonction aparament sa marche sur toute type de fonction puisque les fonction sont aplati elle deviennent des liste simple (un probleme ou pas ? )
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 (terminacc 'acc '((define (multrt a b) (multraux a b 0)) (define (multraux a b acc) (if ( = a 0) acc (multraux (- a 1)b (+ b acc)))))) #t > > (terminacc 'acc '(define (rac2 n r) ; racine carré (if (> (carre r) n) (- r 1) (rac2 n ( + r 1)))) ) #f > (terminacc 'acc '(define (mult a b); multiplication avec des ( + et -) (if (= a 0) 0 (+ b (mult (- a 1) b))))) #f >(terminacc 'acc '((define (prt p n); puissance p du nombre n (praux p n 1)) (define (praux p n acc) (if (= p 0) acc (praux (- p 1) n (* n acc)))))) #t
Merci !

C'est pas gagné! :(

Pour améliorer la lisibilité des messages, pourrais-tu:
- utiliser la balise CODE en cliquant sur le '#' dans la barre d'outils du message
- mettre un point ou un return à la fin de chaque phrase

Ce n'est pas de ta faute si le français n'est pas ta langue maternelle, mais il m'est difficile de comprendre une phrase comme:

Citation:

Si ce paramêtre est cité 3 fois ou plus dans la fonction dans c'est de la récusivité terminale si non faux, j'ai fais sa en fonction aparament sa marche sur toute type de fonction puisque les fonction sont aplati elle deviennent des liste simple (un probleme ou pas ? )

Citation:

Envoyé par kbprince

Re Bonjour.

Comme je l'ai précisez dans mes messages précédents, j'ai fait une fonction qui aplatir une liste ( enleve les parenthèses) et une autre qui compte le nombre occurrence d'un mot dans une liste.

j'ai fusionner ces deux fonction pour faire un fonction qui aplatit la liste puis calcule le nombre occurrence d'un mot.

J'imagine que ton prof aurait préféré que tu comptes en parcourant récursivement l'arbre, sans créer explicitement la liste aplatie, mais c'est mieux que rien!

Citation:

En ce qui me concerne je cherche a savoir combien il y'a le mot acc (accumulateur dans la fonction) , qui est un paramètre indispensable dans une fonction en récusivité terminale.
Si ce paramêtre est cité 3 fois ou plus dans la fonction dans c'est de la récusivité terminale si non faux, j'ai fais sa en fonction aparament sa marche sur toute type de fonction puisque les fonction sont aplati elle deviennent des liste simple (un probleme ou pas ? )

C'est beaucoup trop réducteur!

Que se passe-t-il si quelqu'un écrit une fonction avec le mot 'accu' ou 'ac' plutôt que 'acc', ou écrit une fonction sans variable d'accumulation ou avec plusieurs variables d'accumulation?

~~Peux-tu donner une définition précise de ce que tu (ou ton prof) appelles récursivité terminale et récursivité non terminale?~~
EDIT: J'ai consulté Wikipedia (pour me rafraîchir la mémoire):
Une fonction à récursivité terminale est une fonction où l'appel récursif est la dernière instruction à être évaluée.

Pour moi, la fonction 'rac2' est bien récursive terminale:
Code:

1 2 3 4 (define (rac2 n r) ; racine carré (if (> (carre r) n) (- r 1) (rac2 n ( + r 1))))
Un bon compilateur peut la remplacer par une boucle qui ne consomme pas de ressource.

La fonction 'mult' n'est pas récursive terminale, car elle empile un paquet de 'b' et de '+':
Code:

1 2 3 4 (define (mult a b); multiplication avec des ( + et -) (if (= a 0) 0 (+ b (mult (- a 1) b))))
La fonction 'aplatir2' est clairement récursive non terminale:
Code:

1 2 3 4 5 6 (define (aplatir2 e) (define (aplatir-interne e r) (if (pair? e) (aplatir-interne (car e) (aplatir-interne (cdr e) r)) (if (null? e) r (cons e r)) ) ) (aplatir-interne e '()) )
car elle possède une fonction 'aplatir-interne' qui s'appelle 2 fois (parcours d'arbre binaire).
Il faut, à chaque appel, empiler tout un contexte à restaurer au retour de la fonction.

03/01/2013, 10h50
jack-ft

Citation:

Envoyé par jack-ft

C'est pas gagné! :(

Je confirme! Ce n'est pas un problème facile qu'il vous a donné!

Petite précision: il me semble que 'define' est spécifique de scheme et non de lisp.
Je n'ai jamais fait de scheme. En particulier, je ne connais pas bien les syntaxes spécifiques.
Par exemple, il semble que la syntaxe de la fonction 'if' n'autorise pas un 'progn' implicite (ou un 'begin', semble-t-il, en scheme?), contrairement aux autres lisps.

En repartant d'une définition précise de la récursivité terminale, comme celle de wikipedia, voilà ce que je ferais:

WP: Une fonction à récursivité terminale est une fonction où l'appel récursif est la dernière instruction à être évaluée.

Je commencerais par traiter le cas d'une fonction sans sous-fonction, ce qui n'est déjà pas si simple!

1) (pour s'entraîner) déterminer si une fonction 'fct' (sans sous-fonction) est récursive:
parcourir récursivement le corps de 'fct' à la recherche d'un appel à 'fct'
(sans aplatir le corps de la fonction)

2) déterminer si une fonction 'fct' (sans sous-fonction) est récursive terminale
parcourir récursivement le corps de 'fct'
en vérifiant si les appels à 'fct' sont à l'intérieur d'une fonction normale (comme 'cons' '+' etc.) ou d'une fonction ignorable (comme 'if' ou 'cond')
et faisant attention au cas particulier du 'begin' (explicite ou implicite).

Pour préciser ce dernier point:
si un appel à 'fct' est la dernière instruction d'un 'begin' (explicite ou implicite), il ne remet pas en cause la récursivité terminale.
si un appel à 'fct' est avant la dernière instruction d'un 'begin' (explicite ou implicite), la fonction n'est pas récursive terminale.
si un appel à 'fct' est imbriqué dans une fonction normale, la fonction n'est pas récursive terminale.

Rq: le parser (la fonction qui explore récursivement le corps de 'fct') doit être assez intelligent pour reconnaître le type et la structure de chaque noeud de l'arbre: il doit plonger avec un indicateur spécifique dépendant de la fonction (normale (comme '+') ou structure de contrôle (comme 'if')).
Pour la fonction 'cond', il doit traiter différemment chaque tête de clause (condition) du reste de la clause ('begin' implicite).
etc.

3) déterminer si une fonction 'fct' (avec sous-fonctions) est récursive terminale
déterminer si chacune des sous-fonctions est récursive terminale (cf. 2)
vérifier la récursivité croisée (fct1 appelle fct2 qui appelle fct1)

Voilà quelques pistes à développer!

Y a du boulot!

Bon courage!
03/01/2013, 16h35
kbprince

difficle !
Bonjour
D'après ce que je viens de lire il y'a boucaup de travail sur sa sur tout qu'il me reste pas boucaup de temps pour développer tous sa mais je ne baisserai pas les bras ce projet ces 40% de ma note finale pour le module ( programmation fonctionnelle) .

Pour la fonction que j'ai faites (define (compter mot phrase)) qui compte le nombre d'occurrence ne fonction que sur des liste vraiment simple qui ne contiennent aucune parenthèse c'est pour sa que j'ai rajouter la fonction (define (aplatir2 e)).

il y a plein d'expression que je ne comprend pas dans votre vocabulaire, comme le ( begin )et le (implicite et explicite), pour le cond , j'aime pas l'utiliser parce que je sais pas comment classer les événements du traiment de la fonction, car d'aprés le mon prof , le cond remplace plusieur (if).

Apparemment, je me retrouve au point de départ du projet , et le travail qui me reste à faire n'est pas du gâteau.
c'est ce que j'essaye de reprendre depuis le début, ce programme contient beaucoup pièges, les fonction récursive sont toutes différentes.

en vérifiant si les appels à 'fct' sont à l'intérieur d'une fonction normale (comme 'cons' '+' etc.) ou d'une fonction ignorable (comme 'if' ou 'cond') (j'ai pas compris ou vous voullez en venir ).

3) déterminer si une fonction 'fct' (avec sous-fonctions) est récursive terminale
déterminer si chacune des sous-fonctions est récursive terminale (cf. 2)
vérifier la récursivité croisée (fct1 appelle fct2 qui appelle fct1)

vérifier tout simplement si il y a une fonction chapeau .

jJe connais une fonction qui marche sur les liste simplement , cette fonction detail toute les etape de construction d'un liste :
Code:

1 2 3 4 5 (define (reconstruire exp) (if (pair? exp) (list 'cons (reconstruire (car exp)) (reconstruire (cdr exp)) ) (list 'quote exp) ) )
donner lui n'importe quelle liste et elle vous détaillera sa construction. Je veux savoir si y il as une fonction qui detail les appels récursives d'un fonctionn par exemple :
la fonction qui calcule la somme de 4 donne le résultat 10 = 1 + 2 + 3 + 4
en récursivité sa fait :
Code:

1 2 3 4 (+ 4 (som ( - 4 1)) (+ 3 (som (- 3 1)) (+ 2 (som (- 2 1)) (+ 1 (som (- 1 1)) somme de 0 = 0
ensuite elle fai un calcule pour remonter les résultat :
+ 1
+ 2 sa donne 3
+ 3 sa donne 6
+ 4 sa donne 10

en récursivité terminale sa fait :
Code:

1 2 3 4 5 (somrt (- 4 1) (+ 4 0)) " 0 zéro est un accumulateur " (somrt (- 3 1) (+ 3 4)) (somrt (- 2 1) (+ 2 7)) (somrt (- 1 1) (+ 1 9)) (somrt (- 0 1) (+ 0 10)) n = 0 en renvoi l'acumulateur .
Si j'arrive a trouve une fonction qui ses appels, et comme vous l'avez précisez , si l'appel récusive et la dernier chose a faire donc c'est terminale si non faux. Le probleme c'est comme dire à la fonction qui prend l'argument liste .

En gros : determiner si la fonction est récursive implique deux chose : avoir une boucle , et vérifié qu'on se dérige vers la boucle.
deerminer si elle es terminale : appel récursive dernier chose a faire.
puis determiner si la terminale a une sous fonction.
Je suis Perdu pour l'instant je vais essayé de travailler tous sa , si j'ai d'autre question je vous les transmettrez demain,.

Merci

bonjour

j'ai trouvé sa dans un site internet je sais même pas si sava m'aider , je vous le transmet comeme.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
#lang racket
 
(require parser-tools/lex
 
(prefix-in re- parser-tools/lex-sre)
 
parser-tools/yacc)
 
(provide (all-defined-out))
 
 
 
(define-tokens a (NUM VAR))
 
(define-empty-tokens b (+ - EOF LET IN))
 
(define-lex-trans number
 
(syntax-rules ()
 
((_ digit)
 
(re-: (re-? (re-or "-" "+")) (uinteger digit)
 
(re-? (re-: "." (re-? (uinteger digit))))))))
 
(define-lex-trans uinteger
 
(syntax-rules ()
 
((_ digit) (re-+ digit))))
 
(define-lex-abbrevs
 
(digit10 (char-range "0" "9"))
 
(number10 (number digit10))
 
(identifier-characters (re-or (char-range "A" "z")
 
"?" "!" ":" "$" "%" "^" "&"))
 
(identifier (re-+ identifier-characters)))
 
 
 
(define simple-math-lexer
 
(lexer
 
("-" (token--))
 
("+" (token-+))
 
("let" (token-LET))
 
("in" (token-IN))
 
((re-+ number10) (token-NUM (string->number lexeme)))
 
(identifier (token-VAR lexeme))
 
;; recursively calls the lexer which effectively skips whitespace
 
(whitespace (simple-math-lexer input-port))
 
((eof) (token-EOF))))
 
 
 
(define-struct let-exp (var num exp))
 
(define-struct arith-exp (op e1 e2))
 
(define-struct num-exp (n))
 
(define-struct var-exp (i))
 
 
 
(define simple-math-parser
 
(parser
 
(start exp)
 
(end EOF)
 
(error void)
 
(tokens a b)
 
(precs (left - +))
 
(grammar
 
(exp ((LET VAR NUM IN exp)
 
(make-let-exp $2 (num-exp $3) $5))
 
((NUM) (num-exp $1))
 
((VAR) (var-exp $1))
 
((exp + exp) (make-arith-exp + $1 $3))
 
((exp - exp) (make-arith-exp - $1 $3))))))
 
 
 
 
 
(define (eval parsed-exp)
 
(match parsed-exp
 
((let-exp var num exp)
 
(eval (subst var num exp)))
 
((arith-exp op e1 e2)
 
(op (eval e1)
 
(eval e2)))
 
((num-exp n) n)
 
((var-exp i) (error 'eval "undefined identifier ~a" i))))
 
 
 
(define (subst var num exp)
 
(match exp
 
((let-exp var2 num2 exp2)
 
(if (eq? var var2)
 
exp
 
(let-exp var2 num2
 
(subst var num exp2))))
 
((arith-exp op e1 e2)
 
(arith-exp op
 
(subst var num e1)
 
(subst var num e2)))
 
((var-exp id)
 
(if (equal? id var)
 
num
 
exp))
 
((num-exp n) exp)))
 
 
 
(define (lex-this lexer input) (lambda () (lexer input)))
 
 
 
(let ((input (open-input-string "3 - 3.3 + 6")))
 
(eval (simple-math-parser (lex-this simple-math-lexer input))))
 
 
 
(let ((input (open-input-string "let foo 6 in 3 - 3.3 + foo")))
 
(eval (simple-math-parser (lex-this simple-math-lexer input))))

03/01/2013, 17h52
jack-ft

Désolé, comme tes messages n'utilisent pas les balises QUOTE et CODE, j'ai beaucoup de mal à les lire et je préfère faire un meilleur usage de mon temps et de mon énergie.
Merci d'éditer tes messages et de mettre les balises pour les rendre plus faciles à lire.

fonction compter

Bonjour
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 (define (corp df) (if (unpair df)'() (caddr df))) (define (unpair l) (if (pair? l)#f #t)) (define (nom df) (if (unpair df)'() (caadr df))) (define (par df) (if (unpair df)'() (cdadr df)))
Je cherche à améliorer ma fonction qui compte le nombre d'occurence dans une liste , pour l'instant je suis obligé d'aplatir ma liste pour que la fonction arrive a compter les elements.
Je cherche à compter le nombre d'occurence du nom de la fonction , si il es repeté au moin une fois c'est qu'il y a appel récursive normalement .

Code:

(Cadr fonction)

Pour l'accumulateur c'est un peu dificile , parceque le nom de la fonction es bien définit , mais le parametre pour etre n'importe tous , sauf si on suppose par exemple qu'il sois le dernier élement des paramêtres.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 (define (multraux a b acc) (if ( = a 0) acc (multraux (- a 1)b (+ b acc)))) le 'acc ( accumulateur c'est le dernier elemeent des parametre. (define (der df) (if (unpair df)'() (car (reverse (cdr df))))) (define (ac df); (if (unpair df)'() (der(cdadr df))))
la je pourrai faire une une fonction qui compte l'accumulateur.

ensuite il reste toujour le probleme de comment parcourir les diférentes fonctions pour savoir si c'est vraiment la récursivité est la dernier chose à faire.

une fois toute ces etape franchi la 3eme et derniere etape qui vérifie si fct 1 appel fct 2 et fct 2 appel fct1.

Merci

Bonjour

Voici la fonction qui comptes le nombre d'occurence d'un element dans une liste aplati

Code:

1
2
3
4
5
(define (compter mot phrase)
  (if (pair? phrase)
      (+ (if (equal? mot (car phrase)) 1 0) ; Notez l'alternative sous l'addition!
         (compter mot (cdr phrase)) )
      0 ))

Merci beaucoup d'avoir fait l'effort d'utiliser la balise CODE!
Du coup, ça me donne presque envie de répondre...

Citation:

Envoyé par kbprince

Voici la fonction qui comptes le nombre d'occurence d'un element dans une liste aplati

Code:

1
2
3
4
5
(define (compter mot phrase)
  (if (pair? phrase)
      (+ (if (equal? mot (car phrase)) 1 0) ; Notez l'alternative sous l'addition!
         (compter mot (cdr phrase)) )
      0 ))

Exercice (transformer le pseudo-code en code):

Code:

1
2
3
4
5
6
Pour compter le nombre d'occurrences de 'x' dans un arbre 'A' (sans l'aplatir):
  si 'A' = 'x' c'est 1
  sinon si 'A' n'est pas un 'cons', c'est 0 (on ne traite pas les vecteurs ni les chaines de caractères)
  sinon c'est la somme
    entre le nombre d'occurrences de 'x' dans le sous-arbre (car 'A')
    et le nombre d'occurrences de 'x' dans le sous-arbre (cdr 'A')

Bonjour

J'ai suivi vos instruction sa me donne toujour le résultat 3 , voici ma fonction plus les exemple

Code:

1
2
3
4
5
(define (conte mot df)
 
  (if(equal? mot df)1
     (if (unpair df) 0
  (+ 1 (conte mot (cdr df))))))

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Welcome to DrScheme, version 4.2.4 [3m].
Language: Module; memory limit: 4096 megabytes.
> (conte 'v '(define (cherarb v a)
  (if (unpair a) #f
	(if (= v (car a)) #t
	  (if (< v (car a))
		  (cherarb v (cadr a))
		  (cherarb v (caddr a)))))))
3
> (conte 'chararb '(define (cherarb v a)
  (if (unpair a) #f
	(if (= v (car a)) #t
	  (if (< v (car a))
		  (cherarb v (cadr a))
		  (cherarb v (caddr a)))))))
3
> (conte 'a '(define (cherarb v a)
  (if (unpair a) #f
	(if (= v (car a)) #t
	  (if (< v (car a))
		  (cherarb v (cadr a))
		  (cherarb v (caddr a)))))))
3
>

Merci

04/01/2013, 14h43
jack-ft
Citation:

Envoyé par kbprince

il y a plein d'expression que je ne comprend pas dans votre vocabulaire, comme le ( begin )et le (implicite et explicite),

:google: est votre ami:

http://www.cs.bham.ac.uk/research/pr...ex_scheme.html
http://www.cs.bham.ac.uk/research/pr...re4.html#begin

Citation:

Actually, the begin statement is not necessary in the test function above, since Scheme allows one to have a sequence of expressions as the body of a function, although the begin may make the code clearer.

Lorsque le code contient explicitement un appel à la fonction 'begin', on dit que c'est un 'begin' explicite.
Lorsque le code contient une forme (comme 'define' ou le 'cdr' d'une clause de 'cond') qui autorise une séquence d'instructions et retourne le résultat de la dernière, on dit que c'est un 'begin' implicite.

Citation:

pour le cond , j'aime pas l'utiliser parce que je sais pas comment classer les événements du traiment de la fonction,

Je ne comprends pas 'classer les événements du traiment de la fonction'

Citation:

car d'aprés le mon prof , le cond remplace plusieur (if).

Oui. C'est une manière de voir les choses.
Il y a plusieurs "écoles":
- ceux qui considèrent que la "vraie" primitive est le 'cond' est que le 'if' n'est qu'un cas particulier dégénéré et programmable à partir du 'cond'
- ceux qui considèrent que la "vraie" primitive est le 'if' est que le 'cond' n'est qu'un cas particulier dégénéré et programmable à partir du 'if'.
- ceux qui considèrent que les 2 existent et que chacun a ses avantages et inconvénients.

Dans tous les cas, si on te demande d'écrire un programme qui vérifie si la définition d'une fonction quelconque est récursive terminale, il faut bien traiter le cas où le corps de la fonction contient des trucs comme des 'cond', des 'let', etc.

Citation:

Apparemment, je me retrouve au point de départ du projet , et le travail qui me reste à faire n'est pas du gâteau.

Je confirme!

Citation:

c'est ce que j'essaye de reprendre depuis le début, ce programme contient beaucoup pièges, les fonction récursive sont toutes différentes.

Je confirme!

Citation:

en vérifiant si les appels à 'fct' sont à l'intérieur d'une fonction normale (comme 'cons' '+' etc.) ou d'une fonction ignorable (comme 'if' ou 'cond') (j'ai pas compris ou vous voullez en venir ).

C'est le point crucial!!!

Dans l'arbre du corps d'une fonction comme:
Code:

1 2 3 4 (define (fact1 a) (if (= a 0) 1 (* a (fact1 (- a 1)))))
l'appel (récursif) de 'fact1' est encapsulé dans un appel à '*' (qui n'est pas ignorable) lequel est encapsulé dans un appel à 'if' (qui est ignorable).
conclusion: à cause de la fonction non-ignorable '*', l'appel n'est pas récursif terminal.

Dans l'arbre du corps d'une fonction comme:
Code:

1 2 3 4 5 6 (define (membre a l) (if (not (pair? l)) #f (if (eq a (car l)) #t (membre a (cdr l)))))
l'appel (récursif) de 'membre ' est encapsulé dans un appel à 'if' (qui est ignorable) lequel est encapsulé dans un appel à un autre 'if' (qui est aussi ignorable).
conclusion: l'appel n'est imbriqué sous aucune fonction non-ignorable, l'appel est donc récursif terminal.

Citation:

Citation:

3) déterminer si une fonction 'fct' (avec sous-fonctions) est récursive terminale
déterminer si chacune des sous-fonctions est récursive terminale (cf. 2)
vérifier la récursivité croisée (fct1 appelle fct2 qui appelle fct1)

vérifier tout simplement si il y a une fonction chapeau .

ce n'est malheureusement pas si simple!...

Citation:

Envoyé par kbprince

J'ai suivi vos instruction

Presque...

Dans:

Code:

1
2
3
4
5
6
Pour compter le nombre d'occurrences de 'x' dans un arbre 'A' (sans l'aplatir):
  si 'A' = 'x' c'est 1
  sinon si 'A' n'est pas un 'cons', c'est 0 (on ne traite pas les vecteurs ni les chaines de caractères)
  sinon c'est la somme
    entre le nombre d'occurrences de 'x' dans le sous-arbre (car 'A')
    et le nombre d'occurrences de 'x' dans le sous-arbre (cdr 'A')

Tu as oublié la partie le nombre d'occurrences de 'x' dans le sous-arbre (car 'A'), mais tu y es presque!

04/01/2013, 15h00
jack-ft

Citation:

Envoyé par kbprince

j'ai trouvé sa dans un site internet je sais même pas si sava m'aider , je vous le transmet comeme.

Totalement inutile: après reformatage, c'est juste un parser d'expressions arithmétiques.

Bonjour

Sa Marche enfin :
Code:

1 2 3 4 5 6 7 (define (decompter mot arbre) (if (pair? arbre) (+ (decompter mot (car arbre)) ; récursion à gauche (decompter mot (cdr arbre)) ) ; récursion à droite (if (equal? mot arbre) 1 0 ) ) )
Maintenant , je peut compter le nombre d'occurence du 'Nom' et de 'l'accumulateur' dans la fonction !
est que cela m'aiderai a prouver que c'est une fonction récursive , pour un début ?!
il me restera bien sure le probeleme de comment parcourir les differentes fonction récursives pour determiner si c'est terminale ou pas.

pour la derniere etape : vérifier si elle a une fonction chapeau , on a pas besoin de faire le teste sur les fonction qui ne sont pas on Rterminal , Non ?!

Merci!

04/01/2013, 17h36
jack-ft

Quelle version de scheme utilises-tu?

Concernant le 'begin' implicite, cette référence est bien meilleure: http://www.gnu.org/software/mit-sche...tml#Sequencing

Elle donne la liste des fonctions à parser spécialement!

Voir 40 message(s) de cette discussion en une page