Search code examples
prologprolog-cut

What is the role of cut at the base case?

gcd(X,X,X):-
    !.
gcd(X,Y,Z):-
    X>Y,
    !,
    Inter is X - Y,
    gcd(Inter, Y, Z).
gcd(X,Y,Z):-
    Inter is Y - X,
    gcd(X,Inter,Z).

I get the if else nature of the second cut but I don't understand why program just aborts with the first cut.

Solution

  • It just means you've reached a state where you can get rid of all possible other solutions. Otherwise when asking for more solutions Prolog would run the third rule resulting in unwanted answers. You could alternatively rewrite it like this (assuming X and Y are unified):

    gcd(X,X,X).
gcd(X,Y,Z):-
    X>Y,
    Inter is X - Y,
    gcd(Inter, Y, Z).
gcd(X,Y,Z):-
    X<Y,
    Inter is Y - X,
    gcd(X,Inter,Z).

    The version with the cuts runs probably faster because it does not require as much RAM as the version without cuts. But the version without cuts does not require the strict order of the rules.