Lesson goal: The Factorial in Prolog

Previous: Divisibility rules | Home | Next: Taking derivatives

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: