Рекурсивная функция пролога не работает должным образом

Question

Я пытаюсь реализовать рекурсивную версию последовательности Фибоначчи в Prolog. Ниже приведен код:

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. 

Проблема в том, что она не ведет себя так, как я ее логически ожидаю. Когда я использую trace назвать выдумку (3,2), я получаю следующие строки:

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 

Что привлекает мое внимание, это последний звонок, по телефону: (10), который говорит «? _G2578 является 1», хотя я называю fib (1, _G2579). Я ожидаю, что это будет _G2579, это будет изменено, но это, похоже, не так. Мне нужно выяснить, почему, потому что я очень подозреваю, что именно поэтому fib (3,2) возвращает false вместо true.

Answer 1

Проблема, если я не ошибаюсь, в

F == R 

что проверить, если F (вновь введен термин без значения) равно R.

Если вы измените его в

F = R 

так unifing F с R (ы в резервированной следующем F is R), ваш fib/2 должен работать.

Но я предлагаю вам несколько сэмплификаций.

(1) случай fib(0,F) :- F is 0. Terminale это хорошо, но вы можете написать его как

fib(0,0). 

(2) то же semplification для другого терминала случае вы можете написать его как

fib(1,1). 

(3) в общем предложении вам не нужны две разные переменные F и RR с одинаковым (унифицированным) значением; вы можете использовать только F следующим образом

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