Should I avoid tail recursion in Prolog and in general?

by

Short answer: Tail recursion is desirable, but don’t over-emphasize it.

Your original program is as tail recursive as you can get in Prolog. But there are more important issues: Correctness and termination.

In fact, many implementations are more than willing to sacrifice tail-recursiveness for other properties they consider more important. For example steadfastness.

But your attempted optimization has some point. At least from a historical perspective.

Back in the 1970s, the major AI language was LISP. And the corresponding definition would have been

(defun addone (xs)
  (cond ((null xs) nil)
    (t (cons (+ 1 (car xs))
         (addone (cdr xs))))))

which is not directly tail-recursive: The reason is the cons: In implementations of that time, its arguments were evaluated first, only then, the cons could be executed. So rewriting this as you have indicated (and reversing the resulting list) was a possible optimization technique.

In Prolog, however, you can create the cons prior to knowing the actual values, thanks to logic variables. So many programs that were not tail-recursive in LISP, translated to tail-recursive programs in Prolog.

The repercussions of this can still be found in many Prolog textbooks.

More Related Contents:

  1. Explanation of a Prolog algorithm to append two lists together
  2. Prolog Accumulators. Are they really a “different” concept?
  3. Prolog map procedure that applies predicate to list elements
  4. What is the difference between ‘ and ” in Prolog?
  5. Definition of Reflexive Transitive Closure
  6. Most general higher-order constraint describing a sequence of integers ordered with respect to a relation
  7. Delete vowels in a list
  8. Reification of term equality/inequality
  9. Prolog successor notation yields incomplete result and infinite loop
  10. Finding Unique Items in a List
  11. Prolog: a person is a sibling of himself?
  12. What is the logical ‘not’ in Prolog?
  13. Using a constrained variable with `length/2`
  14. Einsteins Riddle Prolog
  15. Safer type tests in Prolog
  16. Complexity of ISO Prolog predicates
  17. Meaning of instantiation mode indicators in arguments of Prolog predicates
  18. Shuffle in prolog
  19. Collect all “minimum” solutions from a predicate
  20. Using \==/2 or dif/2
  21. Converting Terms to Atoms preserving variable names in YAP prolog
  22. Knowing when to use cut in prolog
  23. Good beginners material on Prolog [closed]
  24. ‘if’ in prolog?
  25. Understanding Difference Lists
  26. Define graph in Prolog: edge and path, finding if there is a path between two vertices
  27. Can you write between/3 in pure prolog?
  28. PROLOG: Determining if elements in list are equal if order does not matter
  29. Features of good Prolog code? [closed]
  30. GNU Prolog assert error

Leave a Comment