CODEWITHSUNDEEP
prolog
user1313410
user1313410

Reputation: 27

Prolog Ending a Recursion

 countdown(0, Y).
 countdown(X, Y):-
    append(Y, X, Y),
    Y is Y-1,
    countdown(X, Y).

So for this program i am trying to make a countdown program which will take Y a number and count down from say 3 to 0 while adding each number to a list so countdown(3, Y). should produce the result Y=[3,2,1]. I can't seem the end the recursion when i run this and i was wondering if anyone could help me?

I cant seem to get this code to work any help? I seem to be getting out of global stack so I dont understand how to end the recursion.

Upvotes: 1

Views: 2181

Answers (2)

Nicholas Carey
Nicholas Carey

Reputation: 74375

Your original code

countdown( 0 , Y ) .
countdown( X , Y ) :-
  append(Y, X, Y),
  Y is Y-1,
  countdown(X, Y).

has some problems:

  1. countdown(0,Y). doesn't unify Y with anything.
  2. Y is Y-1 is trying to unify Y with the value of Y-1. In Prolog, variables, once bound to a value, cease to be variable: they become that with which they were unified. So if Y was a numeric value, Y is Y-1 would fail. If Y were a variable, depending on your Prolog implementation, it would either fail or throw an error.
  3. You're never working with lists. You are expecting append(Y,X,Y) to magically produce a list.

A common Prolog idiom is to build lists as you recurse along. The tail of the list is passed along on each recursion and the list itself is incomplete. A complete list is one in which the last item is the atom [], denoting the empty list. While building a list this way, the last item is always a variable and the list won't be complete until the recursion succeeds. So, the simple solution is just to build the list as you recurse down:

countdown( 0 , []    ) .    % The special case.
countdown( N , [N|Ns] ) :-  % The general case: to count down from N...
  N > 0 ,                   % - N must be greater than 0.
  N1 is N-1 ,               % - decrement N 
  countdown(N1,Ns)          % - recurse down, with the original N prepended to the [incomplete] result list.
  .                         % Easy!

You might note that this will succeed for countdown(0,L), producing L = []. You could fix it by changing up the rules a we bit. The special (terminating) case is a little different and the general case enforces a lower bound of N > 1 instead of N > 0.

countdown( 1 , [1]    ) .
countdown( N , [N|Ns] ) :-
  N > 1 ,
  N1 is N-1 ,
  countdown(N1,Ns)
  .

If you really wanted to use append/3, you could. It introduces another common Prolog idiom: the concept of a helper predicate that carries state and does all the work. It is common for the helper predicate to have the same name as the "public" predicate, with a higher arity. Something like this:

countdown(N,L) :-   % to count down from N to 1...
  N > 0 ,           % - N must first be greater than 0,
  countdown(N,[],L) % - then, we just invoke the helper with its accumulator seeded as the empty list
  .                 % Easy!

Here, countdown/2 is our "public predicate. It calls countdown/3 to do the work. The additional argument carries the required state. That helper will look like something like this:

countdown( 0 , L , L ) . % once the countdown is complete, unify the accumulator with the result list
countdown( N , T , L ) . % otherwise...
  N > 0 ,                % - if N is greater than 0
  N1 is N-1 ,            % - decrement N
  append(T,[N],T1) ,     % - append N to the accumulator (note that append/3 requires lists)
  countdown(N1,T1,L)     % - and recurse down.   
  .                      %

You might notice that using append/3 like this means that it iterates over the accumulator on each invocation, thus giving you O(N2) performance rather than the desired O(N) performance.

One way to avoid this is to just build the list in reverse order and reverse that at the very end. This requires just a single extra pass over the list, meaning you get O(2N) performance rather than O(N2) performance. That gives you this helper:

countdown( 0 , T , L ) :- % once the countdown is complete,
  reverse(T,L)            % reverse the accumulator and unify it with the result list         
  .                       %
countdown( N , T , L ) :- % otherwise...
  N > 0 ,                 % - if N is greater than 0
  N1 is N-1 ,             % - decrement N
  append(T,[N],T1) ,      % - append N to the accumulator (note that append/3 requires lists)
  countdown(N1,T1,L)      % - and recurse down.   
  .                       %

Upvotes: 1

gusbro
gusbro

Reputation: 22585

There are several errors in your code:

  • first clause does not unify Y.
  • second clause uses append with first and third argument Y, which would only succeed if X=[].
  • in that clause you are trying to unify Y with another value which will always fail.
  • Y should be a list (according to your comment) in the head but you are using it to unify an integer.

You might do it this way:

countdown(X, L):-
  findall(Y, between(1, X, Y), R), 
  reverse(R, L).

between/3 will give you every number from 1 to X (backtracking). Therefore findall/3 can collect all the numbers. This will give you ascending order so we reverse/2 it to get the descending order.

If you want to code yourself recursively:

countdown(X, [X|Z]):-
  X > 1,
  Y is X-1,
  countdown(Y, Z).
countdown(1, [1]).

Base case (clause 2) states that number 1 yields a list with item 1.

Recursive clause (first clause) states that if X is greater than 1 then the output list should contain X appended with the result from the recursive call.

Upvotes: 0

Related Questions