Geek asks and answers

Why does my predicate in Prolog Fib / 2 always say "from the local stack"?

I wrote the fib / 2 predicate to calculate Fibonacci numbers in Prolog. Although it works, it always says “from the local stack,” and the error looks like this:

?- fib(10, F).
F = 55 ;
ERROR: Out of local stack

my predicate is below:

fib(0, 0).
fib(1, 1).
fib(N, NF) :-
    A is N - 1, 
    B is N - 2,
    fib(A, AF), 
    fib(B, BF),
    NF is AF + BF.

Does anyone know why this is and how to fix it to get the following material:

% or the search might stop immediately, without pressing space.
?- fib2(10, F).
F = 55 ;
false.

Thanks in advance!

+5
source share
5 answers

The error out of local stackmeans that the program used too much memory and exceeded the allocated space; this happens often when a program enters an endless loop. In your case, this is a trace:

[trace] 2 ?- fib(2,M).
   Call: (6) fib(2, _G671) ? creep
^  Call: (7) _G746 is 2+ -1 ? creep
^  Exit: (7) 1 is 2+ -1 ? creep
^  Call: (7) _G749 is 2+ -2 ? creep
^  Exit: (7) 0 is 2+ -2 ? creep
   Call: (7) fib(1, _G747) ? creep
   Exit: (7) fib(1, 1) ? creep
   Call: (7) fib(0, _G747) ? creep
   Exit: (7) fib(0, 0) ? creep
^  Call: (7) _G671 is 1+0 ? creep
^  Exit: (7) 1 is 1+0 ? creep
   Exit: (6) fib(2, 1) ? creep
M = 1 ;
   Redo: (7) fib(0, _G747) ? creep
^  Call: (8) _G752 is 0+ -1 ? creep
^  Exit: (8) -1 is 0+ -1 ? creep
^  Call: (8) _G755 is 0+ -2 ? creep
^  Exit: (8) -2 is 0+ -2 ? creep
   Call: (8) fib(-1, _G753) ? creep
^  Call: (9) _G758 is -1+ -1 ? creep
^  Exit: (9) -2 is -1+ -1 ? creep
^  Call: (9) _G761 is -1+ -2 ? creep
^  Exit: (9) -3 is -1+ -2 ? creep
   Call: (9) fib(-2, _G759) ? creep
^  Call: (10) _G764 is -2+ -1 ? creep
^  Exit: (10) -3 is -2+ -1 ? creep
...

, , 1 ( ), ; , , N > 1 , fib (-1), fib (-2), fib (-3) ..

, N>1

+9

, , . :

:- dynamic db_fib/2.

init_fib :-
    assertz( db_fib(0, 0) ),
    assertz( db_fib(1, 1) ).

fib(N, NF) :-
    A is N - 1,
    B is N - 2,
    get_fib(A, AF),
    get_fib(B, BF),
    NF is AF + BF.

get_fib(A, F) :-
    db_fib(A, F),
    !.

get_fib(A, F) :-
    fib(A, F),
    assertz( db_fib(A, F) ).

, SWI Prolog

?- init_fib, fib(1000,F).

.

?- init_fib.
true.

?- fib(10,A).
A = 55.

?- fib(100,A).
A = 354224848179261915075.

?- fib(1000,A).
A = 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875.
+4

tail-recursive. - , TRO ( ) . , . TRO . ( , , ):

% ------------------------------------------------------
% the public interface predicate
% ------------------------------------------------------
fib(1,1).          % first  element in the sequence is 1
fib(2,1).          % second element in the sequence is 1
fib(N,X) :-        % subsequent elements
  N > 2 ,          %   where N > 2
  fib(1,1,3,N,X)   %   are computed
  .

% --------------------------------------
% the private worker predicate for N > 2
% this predicate maintains a sliding 'window' on the fibonacci sequence
% as it computes it
% --------------------------------------
fib( V1 , V2 , N , N , X ) :- % compute the element at position N
  N > 2 ,                     % ensure N > 2
  X is V1 + V2                % value is the sum of the 2 prior elements
  .
fib( V1 , V2 , T , N , X ) :- % on backtracking, slide the window to the right:
  T > 2         ,             %  ensure N > 2
  T1 is T  + 1  ,             %  increment N
  V3 is V1 + V2 ,             %  compute the next value (V1+V2)
  fib(V2,V3,T1,N,X)           %  recurse
  .
+3

, , , , failure-slice, , false.

fib(0, 0) :- false.
fib(1, 1) :- false.
fib(N, NF) :-
    A is N - 1, 
    B is N - 2,
    fib(A, AF), false,
    fib(B, BF),
    NF is AF + BF.

. , , , .

, - . , .

, . , , ( @RicardoMojica). false , . :

() .


. .

+2

, ( ), , :

fib(N, NF) :- 
  A is N - 1, 
  B is N - 2,
  fib(A, AF), 
  fib(B, BF),
  NF is AF + BF.
fib(1, 1).
fib(0, 0).

.

0

More articles:


All Articles