How does this compute ? I am trying to understand how the values of H get assigned in the list

This predicate should print a list of size N containing possible permutations of 0 and 1.

My question is : does the value of H get carried over with each recursion or does the creation of the list with values of bit(H) take place in the backtracking phase?

bit(0).
bit(1).
gen(0,[]).
gen(N,[H|T]) :-
   N > 0,
   bit(H),
   N1 is N - 1,
   gen(N1,T).

Solution

Prolog execution is all about choice points. Here a choice point is left at each recursion step by the bit/1 predicate. When you ask Prolog to give you another solution, it will just go back to the youngest choice point. Here, instead of going through the first clause of bit/1 and bind H to 0, it will go through the second clause and bind H to 1. Once both clauses have been picked, Prolog'll go back to an older choice point, etc... until ultimately all choice points are exhausted and the program returns false..

you can try this yourself with the trace/0 predicate:

?- trace, gen(3, Result).