Rewriting tail recursion prolog code into simple recursion

Question

I'm quite new in prolog and I want to practice rewriting a tail-recursion code into a simple recursion to understand better the process, but I did not succeed in it. If anybody can help with it I would really appreciate it.

Note: Converting tail-recursive (tail-call) code to non tail-recursive code is not a wise thing to normally do in Prolog. This question is only for academic purposes of learning.

The code:

some_predicate(T,1,3,0,D),
%the tail has elements with ID and Numbers like [(1,3),(2,5),(4,3)])
%in the D I count steps if different conditions are fulfilled
%I would like to write something like: some_predicate(T,1,3,D) without the Acc

some_predicate(_, _, 1, D, D):-!.
some_predicate([], _, _, D, D):-!.
some_predicate([(UP,_)|_], ID, H, D, D):-
    UP >= ID + H,
    !.
some_predicate([(UP,UH)|T], _, H, D, RetD):-
    H > UH,
    TH is H - 1,
    TD is D + 1,
    some_predicate(T, UP, TH, TD, RetD),
    !.
some_predicate([(UP,UH)|T], _, _,D, RetD):-
    TD is D + 1,
    some_predicate(T, UP, UH, TD, RetD),
    !.

My attempt

some_predicate(_, _, 1,0):-!.
some_predicate([], _, _,0):-!.
some_predicate([(UP,_)|_], ID, H, 0):-
    UP >= ID + H,
    !.
some_predicate([(UP,UH)|Er], _, H, D):-
    H > UH,
    some_predicate(Er, UP, TH, TD),
    H is TH - 1,
    D is TD + 1,
    !.
some_predicate([(UP,UH)|Er], _, _,D):-
    some_predicate(Er, UP, UH, TD),
     D is TD + 1,
     !.

But why would you want to sacrifice the possibility of having the compiler optimize the recursion into a loop? — David Tonhofer
My university task is to write a code snippet in two different ways, a tail-rec and a simple recursion and mark the differences. I prefer the tail-recursion too and as you can see I managed to solve the problem in that way, but I have to do it with non-tailrec too. — MrNobody
Does this answer your question? How to find out if Prolog performs Tail Call Optimization — Guy Coder
I am sorry to give this a down-vote but I really consider the title damaging. For someone new to Prolog they might get the impression from the title that tail recursion is a bad thing. It is the opposite, it is a very good thing. I do understand what you are trying to accomplish which is why the link in the previous comment should be of use to you. — Guy Coder
I understand, thank you for the note section editing. To be honest the linked question didn't really helped me, but I'm still trying to rewrite it. If I can solve it, I will answer my question later, but thank you for the suggestion. — MrNobody

Isabelle Newbie Isabelle Newbie · Accepted Answer · 2020-12-01T20:10:20

A comment in the question says that you would like to rewrite the code without an accumulator, but it doesn't use an accumulator. The general schema for predicates using a list accumulator would be something like this:

foo(X, Ys) :-
    foo(X, [], Ys).

foo(X, Acc, Acc) :-
    bar(X).
foo(X, Acc, Ys) :-
    baz(X, Y, Z),
    foo(Z, [Y | Acc], Ys).

The recursive call involving the list accumulator gets a bigger list than the accumulator was before. You add something to the accumulator before you pass it to the recursive call.

Your program instead uses the common pattern of "list iteration" (comments with a better name are welcome) in Prolog which does the opposite of recursion using an accumulator:

foo([], Y) :-
    bar(Y).
foo([X | Xs], Y) :-
    baz(X),
    foo(Xs, Y).

(This uses similar names to the predicate before, but I'm not saying that they are equivalent.)

The list constructor [_ | _] is in the head of the clause, not in a recursive call. The list in the recursive call is smaller than the list in the head. You remove something from the list before you pass the tail to the recursive call.

This is therefore not an answer your question, just a hint that you need to start from the right place: Some predicate definition that really does use an accumulator list. The simplest interesting case is probably reversing a list.

Rewriting tail recursion prolog code into simple recursion

1 Answers