La fonction récursive de Prolog ne se comporte pas comme prévu

Question

J'essaye d'implémenter la version récursive de la séquence de Fibonacci dans Prolog. Voici le code:

fib(0,F) :- F is 0. 
fib(1,F) :- F is 1. 
fib(N,F) :- N > 1, 
AA is (N - 1), 
BB is (N - 2), 
fib(AA,CC), 
fib(BB,DD), 
RR is (CC + DD), 
F == RR, 
F is RR. 

Le problème est qu'il ne se comporte pas comme je m'y attendais logiquement. Lorsque j'utilise trace appeler fib (3,2), je reçois les lignes suivantes:

Call: (7) fib(3, 2) ? creep 
    Call: (8) 3>1 ? creep 
    Exit: (8) 3>1 ? creep 
    Call: (8) _G2569 is 3+ -1 ? creep 
    Exit: (8) 2 is 3+ -1 ? creep 
    Call: (8) _G2572 is 3+ -2 ? creep 
    Exit: (8) 1 is 3+ -2 ? creep 
    Call: (8) fib(2, _G2573) ? creep 
    Call: (9) 2>1 ? creep 
    Exit: (9) 2>1 ? creep 
    Call: (9) _G2575 is 2+ -1 ? creep 
    Exit: (9) 1 is 2+ -1 ? creep 
    Call: (9) _G2578 is 2+ -2 ? creep 
    Exit: (9) 0 is 2+ -2 ? creep 
    Call: (9) fib(1, _G2579) ? creep 
    Call: (10) _G2578 is 1 ? creep 
    Exit: (10) 1 is 1 ? creep 

Ce qui retient mon attention est le dernier appel, composez le: (10), qui dit "? _G2578 est 1", même si j'appelle fib (1, _G2579). Mon attente est que c'est _G2579 qui va être changé, mais cela ne semble pas être le cas. J'ai besoin de savoir pourquoi parce que je soupçonne fortement que c'est pourquoi fib (3,2) retourne faux au lieu de vrai.

Answer 1

Le problème, si je ne me trompe pas, est dans

F == R 

que vérifier si F (un nouveau terme sans valeur) est égale à R.

Si vous changez dans

F = R 

si unifing F avec R (un en suivant F is R redondant), votre fib/2 devrait fonctionner.

Mais je vous propose une certaine semplification.

(1) le cas de Terminale fib(0,F) :- F is 0. est bonne, mais vous pouvez l'écrire comme

fib(0,0). 

(2) même est la simplification pour l'autre cas terminal: vous pouvez l'écrire comme

fib(1,1). 

(3) dans la clause générale, vous n'avez pas besoin de deux variables différentes F et RR avec la même valeur (unifiée); vous pouvez utiliser seulement F de la façon suivante

fib(N,F) :- 
    N > 1, 
    AA is (N - 1), 
    BB is (N - 2), 
    fib(AA,CC), 
    fib(BB,DD), 
    F is (CC + DD).