`printOrAdd(IntegerList, Sum)`

which binds the even numbers from its input list `IntegerList`

to a list `EvensList`

,
and at the same time adds up the odd numbers in `IntegerList`

and
binds them to `Sum`

. Here are two versions of the code, `printOrAdd`

and `printOrAdd1`

:
% printOrAdd is aninefficientsolution to the task posed above: printOrAdd([], [], 0). % even numbers printOrAdd([First | Rest], [First | RestOfEvens], Sum) :- printOrAdd(Rest, RestOfEvens, Sum), 0 is First mod 2. % odd numbers printOrAdd([First | Rest], RestOfEvens, Sum) :- printOrAdd(Rest, RestOfEvens, SumOfRest), 1 is First mod 2, Sum is SumOfRest + First. % printOrAdd1 is acorrectedversion of printOrAdd which % avoids the unnecessary recursive calls. printOrAdd1([], [], 0). printOrAdd1([First | Rest], [First | RestOfEvens], Sum) :- 0 is First mod 2, printOrAdd1(Rest, RestOfEvens, Sum). printOrAdd1([First | Rest], RestOfEvens, Sum) :- 1 is First mod 2, printOrAdd1(Rest, RestOfEvens, SumOfRest), Sum is SumOfRest + First.

?- printOrAdd([1,2,3,4,5,6], Evens, SumOfOdds). Evens = [2, 4, 6], SumOfOdds = 9 ; false.

The first version makes the recursive call in the two recursive rules
before it tests to see if `First`

is even or odd.
If half the numbers are even and half odd, then clearly half of
the recursive calls will be wasted. However, the situation is actually
*much* worse than that, because of Prolog's automatic backtracking.
The backtracking means that Prolog will eventually try all three rules
for printOrAdd, and two of them will cause recursive calls, each of
which will in turn generate two recursive calls, each of which ...
Thus for a list of length 100, say, there will be more than 2^{100}
recursive calls. If Prolog could manage a billion recursive calls per
second, 2^{100} recursive calls would take about 2^{70} seconds,
or about 30 trillion years.

The solution, of course, is to test before you make a recursive call,
as is done in `printOrAdd1`

.
*Always test before you make a recursive call;
never call before you test*.