You may remember the factorial from class. It means you take an integer, and multiple it by all of the integers below it, stopping at 1. It has the definition of $n!=n(n-1)\times(n-2)\times(n-3)...\times(1)$. As an example, $5!$ is $5\times 4\times 3\times 2\times 1=120$.
Let's code up a factorial calculator in Prolog. It's quite interesting to do in Prolog, because it forces you to think carefully about how the factorial is calculated. What's special about doing this in Prolog is that as a language, functions (or clauses) do not return results. They instead work to make variables in their headers become defined (or "instantiated" in the lingo of Prolog). Thus, the approach as in this lesson will not work.
Here's what we'll do. Look at $5!$, which is
$$5!=5\times 4\times 3\times 2\times 1.$$
From this you can see that $5!$ is really $5\times 4!$, so $5!=5\times 4!$. And, what is $4!$? Well, it's $4\times 3!$.
In general terms, $n!=n\times (n-1)!$. There's also the rule that $0!=1$.
So if you wanted to take the factorial of $N$, you'd say something like fact(N) = N * fact(N-1). But in Prolog, the clause would have to be fact(N,Result), with Result being the variable that we'll assign to the final answer. We also have to work in some logic to use $0!=1$.
Now you try. Run the default goal, and try a few of your own!
Type your code here:
See your results here:
Code summary:
fact(0,1) :- !. is the "rule" of factorials and tells the calculation when to stop; $0!=1$. The ! is Prolog is called the "cut" and tells Prolog to stop looking back to the left of the ! when it goees looking for solutions. (Think of the ! like a "wall" one cannot pass back over.)
fact(N,Result) :- N1 is N -1, fact(N1,R), Result is N * R. This clause is read "to put the factorial of N into Result, use the idea above that $N!=N(N-1)!$. So, first find N-1, then the factorial of it. The answer to put into variable Result is then N times the factorial of N-1."
*Why can't we do fact(N-1,R)? It's because the Prolog is clause forces the numerical evaluation of what is to the right of the is.
Share your code
Show a friend, family member, or teacher what you've done!