Avoid recursive call Prolog

Question

I have this problem and I need to give a solution to avoid the recursive call f(T,S) in both clauses:

f([],0).
f([H|T],S):-
    f(T,S1),
    S1>=2,
    !,
    S=S1+H.
f([_|T],S):-
    f(T,S1),
    S=S1+1.

I don't understand what this does... And I really have no idea how I could avoid that recursive call. Please help me with a solution

Wasn't the task to avoid non-tail recursive call? Above code is calculating sum of the elements in the list, there is no easy way (I don't know any) to do it without recursion. — Świstak35
That predicate doesn't compute a sum. It will actually, for a list like [1,2,3,4], result in S = 0+1+1+2+1. So it needs some work as-is. One issue is that, in prolog, =/2 is not an arithmetic assignment statement. To assign an arithmetic expression, use is/2. — lurker
You're right, I forgot about is/2. Still, I don't think it's possible to do that without recursion. — Świstak35
@Świstak35 actually, I think the OP's use of = is OK in this case. I didn't notice the Turbo Prolog tag. Turbo Prolog allows = to be used as is (not sure why, but it does). I agree: recursion is the only simple way to do it, but there is a choice between tail recursive and non-tail recursive as you indicated. — lurker
@Świstak35 after puzzling through the predicate, I realized that it doesn't computer the sum of a list (as it first appears), but adds the value of a list's head to the length of its body. Strange, that. — Shon

Shon Shon · Accepted Answer · 2014-01-16T22:19:58

Note: I replaced propositions of the form L = M + N with L is M + N, since I'm not using Turbo Prolog, but I'd guess everything else will be the same.

Your f/2 predicate is a strange one. The third clause just counts the length of a list but the second relates S1 to the tail of the list, and adds the value determined for S1 to the value of the head if S1 > 1. In other words, f/2 adds the head to the length of the tail if the tail is > 1, or else it just returns the length of the list (i.e., 1 or 2); e.g.,

?- f([1], X).
X = 1.

?- f([2], X).
X = 1.

?- f([2,1], X).
X = 2.

?- f([3,1], X).
X = 2.

?- f([3,1,1], X).
X = 5.

?- f([2,1,1], X).
X = 4.

The second and third clauses of f/2 describe quite different relations. The second predicate relates the integer value of a list's head to the length of the list's body, provided a certain condition holds. The third predicate simply relates an integer to a list, such that the value of the integer is the same as the number of elements in a list. I.e., it describes the length of a list. Prolog excels at declarative programming and at helping us understand problems by forcing/enabling us to write clear and concise descriptions of relationships. The second and third clauses of f/2 describe different relations, so we can (and should) use two different predicates. As you'll see, this will allow us to remove the recursive call from the the predicate f/2, since the recursion is only necessary for determining the length relationship (but we still have recursion in operation, it's just not a recursive call to f/2). Here's one possible solution (it simply uses the built-in length/2, but you can replace this with your own predicate if you're not allowed to use built-ins):

f([], 0).
f([H|T],S):-
    length(T, Len),    % Len is the length of T
    ( Len > 1          % if Len is greater than 1
    ->
        S is Len + H   % then the value of S is Len plus the value of H
    ;
        S is Len + 1   % otherwise, S is Len + 1 ( the addition is to make up for the missing H)
    ).

You could actually refractor this further to eliminate the conditional:

head_plus_length_of_tail([E1, E2 | Es], N) :-
    length([E2|Es], Len),
    N is E1 + Len.

g(List, N) :-
    head_plus_length_of_tail(List, N), !.
g(List, N) :-
    length(List, N).

head_plus_length_of_tail/2 only succeeds if there are three or more elements in a list (which takes care of the conditional that checks if the length of the list's body is > 1. If that succeeds, we cut, so it won't backtrack to give us the length of the list as well. Otherwise we just get the length of the list.

Avoid recursive call Prolog

1 Answers