No, your code is NOT tail-recursive.
Tail-recursive means that at the bottom of the recursion you get the answer that you ask for at the beginning directly.
If you trace your code, for exampleappend([1,2,3],[a,b,c],Out)
, your get:
Call:append([1, 2, 3], [a, b, c], _G4702)
Call:append([2, 3], [a, b, c], _G4756)
Call:append([3], [a, b, c], _G4759)
Call:append([], [a, b, c], _G4762)
Exit:append([], [a, b, c], [a, b, c])
Exit:append([3], [a, b, c], [3, a, b, c])
Exit:append([2, 3], [a, b, c], [2, 3, a, b, c])
Exit:append([1, 2, 3], [a, b, c], [1, 2, 3, a, b, c])
The values of the variables(_G4762,_G4759,_G4756
) are passed up to _G4702
, and _G4702
is the answer.
We may have a tail-recursive version of append:
ap_tail_r([H|T],B,Ac,Out):-
ap_tail_r(T,B,[H|Ac],Out).
ap_tail_r([],B,[H|Ac],Out):-
ap_tail_r([],[H|B],Ac,Out).
ap_tail_r([],Out,[],Out).
Let trace again ap_tail_r([1,2,3],[a,b,c],[],Out)
:
Call:ap_tail_r([1, 2, 3], [a, b, c], [], _G4786)
Call:ap_tail_r([2, 3], [a, b, c], [1], _G4786)
Call:ap_tail_r([3], [a, b, c], [2, 1], _G4786)
Call:ap_tail_r([], [a, b, c], [3, 2, 1], _G4786)
Call:ap_tail_r([], [3, a, b, c], [2, 1], _G4786)
Call:ap_tail_r([], [2, 3, a, b, c], [1], _G4786)
Call:ap_tail_r([], [1, 2, 3, a, b, c], [], _G4786)
Exit:ap_tail_r([], [1, 2, 3, a, b, c], [], [1, 2, 3, a, b, c])
Exit:ap_tail_r([], [2, 3, a, b, c], [1], [1, 2, 3, a, b, c])
Exit:ap_tail_r([], [3, a, b, c], [2, 1], [1, 2, 3, a, b, c])
Exit:ap_tail_r([], [a, b, c], [3, 2, 1], [1, 2, 3, a, b, c])
Exit:ap_tail_r([3], [a, b, c], [2, 1], [1, 2, 3, a, b, c])
Exit:ap_tail_r([2, 3], [a, b, c], [1], [1, 2, 3, a, b, c])
Exit:ap_tail_r([1, 2, 3], [a, b, c], [], [1, 2, 3, a, b, c])
The only variable that we are keeping tract of is _G4786
, which is the answer that we look for at the first place.
What exactly the tail-recursive code does is: a. reverse the first part, b. put the reversed first part to the second part head by head, c. when the reserved first part is empty, the updated second part is the appended result.