Search code examples
listprologfactorial

List of factorials in Prolog


I'm having trouble solving the following exercise...

A factorial can be described in Prolog as:

factorial(0, 1).
factorial(N, F) :-
   N1 is N - 1,
   factorial(N1, F1),
   F is N * F1.

I need to expand this code in order to return a list of all previous factorials until N. But it returns only the first factorial (1), and then the error: ERROR: Out of local stack. Here is my code:

insertList(H, L, [H|L]) :-
   !.

factorial(0, 1, [1]).
factorial(N, F, L) :-
   N1 is N - 1,
   factorial(N1, F1, L),
   F is N * F1,
   insertList(F, L, [F|L]). 

list_factorial(X, L) :-
   factorial(X, F, L).

What am I doing wrong?


Solution

  • the minimal correction, indicating the main problem

    insertList(H, L, [H|L]):- !.
    
    factorial(0, 1, [1]).
    factorial(N, F, Fs):- N1 is N-1, factorial(N1, F1, L), F is N * F1, insertList(F, L, Fs). 
    
    list_factorial(X, L):- factorial(X, F, L).
    

    but it will loop if you request backtracking after the first solution is returned. You could add the test @false suggested... otherwise, another definition could be

    factorials(N, L) :-
        N > 0 -> L = [F,G|Fs], M is N-1, factorials(M, [G|Fs]), F is G*N ; L = [1].