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:

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 a corrected version 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 ;

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.