efficiency
There are many ways for code to be inefficient. This article concentrates on the issue of avoiding unnecessary recursive calls. Consider the following exercise: write a Prolog predicate `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 an inefficient solution to the task posed above:

% even numbers
printOrAdd([First | Rest], [First | RestOfEvens], Sum) :-
0 is First mod 2.

% odd numbers
printOrAdd([First | Rest], RestOfEvens, Sum) :-
1 is First mod 2,
Sum is SumOfRest + First.

% avoids the unnecessary recursive calls.

printOrAdd1([First | Rest], [First | RestOfEvens], Sum) :-
0 is First mod 2,

printOrAdd1([First | Rest], RestOfEvens, Sum) :-
1 is First mod 2,
```?- printOrAdd([1,2,3,4,5,6], Evens, SumOfOdds).
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 2100 recursive calls. If Prolog could manage a billion recursive calls per second, 2100 recursive calls would take about 270 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.