How to save the value of a recursive function in a list in the prolog?

Question

My purpose:

Given the following definition of f, create a Prolog program to calculate f (i) for all 0 <i <32.

• f (0) = 0
• f (1) = 1
• f (n) = f (n-2) + 2 * f (n-1) for n> 1

My code so far:

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

It works, but it always shows values ​​for N> 20.

Please let me know how to save the values ​​in a list to speed up the program.

Answer 1

This uses the DCG approach, which generates the sequence as a list:

prob3(1, F0, F1) --> [F0, F1].
prob3(N, F0, F1) --> {N > 1, F2 is 2*F1 + F0, N1 is N-1}, [F0], prob3(N1, F1, F2).

prob3(0, [0]).
prob3(N, FS) :-
    phrase(prob3(N, 0, 1), FS).

?- prob3(10, L).
L = [0, 1, 2, 5, 12, 29, 70, 169, 408, 985] ;
false.

?- prob3(169, L).
L = [1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, 13860, 33461, 80782, 195025,
..., 17280083176824678419775054525017769508908307965108250063833395641] ;
false

?- time((prob3(1000, L),false)).
% 3,011 inferences, 0.005 CPU in 0.005 seconds (100% CPU, 628956 Lips)
false.

<h / "> Note that for long-list answers, SWI Prolog will reduce the output, for example:

?- prob3(20, L).
L = [0, 1, 2, 5, 12, 29, 70, 169, 408|...]

SWI Prolog . w, :

?- prob3(20, L).
L = [0, 1, 2, 5, 12, 29, 70, 169, 408|...] [write]   % PRESSED 'w' here
L = [0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, 13860, 33461, 80782, 195025, 470832, 1136689, 2744210, 6625109, 15994428] ;
false

?-

. : .

Answer 2

, !

:

p3(N,F) :- 
   (  N =:= 0 -> F = 0
   ;  N =:= 1 -> F = 1
   ;  N  >  1 -> N0 is N-2, p3_(N0,0,1,F)
   ).

p3_(N,F0,F1,F) :- 
   F2 is F0 + 2*F1,
   (  N =:= 0
   -> F2 = F
   ;  N0 is N-1,
      p3_(N0,F1,F2,F)
   ).

:

?- between(25,35,N), p3(N,F).
  N = 25, F = 1311738121
; N = 26, F = 3166815962
; N = 27, F = 7645370045
; N = 28, F = 18457556052
; N = 29, F = 44560482149
; N = 30, F = 107578520350
; N = 31, F = 259717522849
; N = 32, F = 627013566048
; N = 33, F = 1513744654945
; N = 34, F = 3654502875938
; N = 35, F = 8822750406821.

- :

?- p3(111,F).
F = 1087817594842494380941469835430214208491185.

?- p3(123,F).
F = 42644625325266431622582204734101084193553730205.

?- p3(169,F).
F = 17280083176824678419775054525017769508908307965108250063833395641.

?

?- time((between(0,1000,N), p3(N,_), false)).
% 2,006,005 inferences, 0.265 CPU in 0.265 seconds (100% CPU, 7570157 Lips)
false.

Answer 3

, , :

:- use_module(library(lambda)).

f(N, FN) :-
    cont_f(N, _, FN, \_^Y^_^U^(U = Y)).

cont_f(N, FN1, FN, Pred) :-
    (   N < 2 ->
        call(Pred, 0, 1, FN1, FN)
    ;
        N1 is N - 1,
        P = \X^Y^Y^U^(U is X + 2*Y),
        cont_f(N1, FNA, FNB, P),
        call(Pred, FNA, FNB, FN1, FN)
    ).

Answer 4

memoizing is useful, I used it to speed up simple calculations using the Erathostenes sieve

?- time((between(0,1000,N), prob3(N,_), false)).
% 10,939 inferences, 0.011 CPU in 0.012 seconds (99% CPU, 951780 Lips)

:- dynamic memo/2.
prob3(0, 0).
prob3(1, 1).
prob3(N, R) :- memo(N, R), !.
prob3(N, R) :-
    N > 1, N2 is N-2, N1 is N-1, prob3(N2,R2), prob3(N1,R1), R is R2+2*R1, assertz(memo(N, R)).