09 - Recursion with an Accumulator

In this video we learn about the common pattern of recursion with an accumulator. We introduce the idea trying to implement a property that relates a list and its reverse. At first attempt we fail, and use tracing to help us see what needs to be fixed - including using an accumulator.

00:00 Reversing A List Puzzle
08:00 Recursive Method
15:03 Growing A List from its Head
17:01 Debugging First Attempt
27:12 Accumulator
28:51 Walk Through
32:58 Wrapping to Hide the Accumulator

Blog:

Code on GitHub:

––––––––––––––––––––––––––––––

The following pieces of music are freely licensed for use in this video.

[xemorr]

The music makes it feel like you're singing me a lullaby

[ЧингизНабиев-эг]

I was able to implement a reversed predicate without an accumulator:

% Checking if the lists are of the same length
same_len([], []).
same_len([_Head1|Tail1], [_Head2|Tail2]) :- same_len(Tail1, Tail2).

% Getting the last element of the list
last_of([X], X).
last_of([_|Tail], X) :- last_of(Tail, X).

% Getting the list without the last element
no_last([], []).
no_last([_], []).
no_last([Head|Tail], [Head|Tail2]) :- no_last(Tail, Tail2).

% Checking if the lists are reverses of each other
reversed([], []).
reversed([X], [X]).
reversed([Head1|Tail1], [Head2|Tail2]) :-
same_len(Tail1, Tail2),
last_of(Tail1, Head2),
last_of(Tail2, Head1),
no_last(Tail1, X),
no_last(Tail2, Y),
reversed(X, Y).