## More Induction

Induction is fundamental to programming in Prolog, so it’s worth going over it a little more. Before we do, let’s take a look at the principle data structure in Prolog: the list.

Lists in Prolog are defined inductively according to the following two rules:

`[]`, the empty list, is a list.`[X|List]`is a list for any`X`if`List`is a list.

We use lists a lot in Prolog. To start with, we’ll define a predicate for adding all of the numbers in a list, using induction. The base case here is obvious; the sum of all the numbers in a list with one element is that element. We can write this as follows:

sum([X],X).

This example makes use of Prolog’s pattern-matching abilities. Since
we’ve used the variable `X` twice, this predicate will evaluate to
`true` only if the same value is used in both places; `sum([1],1)`
will succeed, `sum([1],2)` will not. If we leave `X` undefined in
some places, Prolog will assign the value to `X` that’s used in
other places. We can see this in the Prolog interpreter:

?- sum([1],S). S = 1 Yes ?- sum([S],1). S = 1 Yes

Next, we must define the inductive case. Induction on lists typically uses
the `[Head|Tail]` construction. This sets `Head` to the first
element of a list and `Tail` to the remainder of the list; in the case of
a single element list, `Tail` will be the empty list. To sum the elements
in a list inductively, we add the first element to the sum of the remaining
ones. In Prolog we say this:

sum([H|T], S) :- sum(T,X), S is H + X.

The left side of this statement will match any list, and split it so that
`H` is the first element and `T` is a list of the others. We then
use the same predicate to make `X` the sum of all the elements of
`T`, and then set `S` to this plus the first element. We can test
this principle by loading the file `sum.pro` from the source file for
this article:

?- sum([1,2,3],X). X = 6 Yes

Another common pattern in Prolog is *tail-recursion*, which is popular
because it’s easy for the compiler to optimize. A tail-recursive predicate
is one in which the recursive call in the inductive step is the last part of the
clause. Confused? Here’s how we would write the `sum` predicate in
a tail-recursive manner:

sum([],X,X). sum([H|T], A, S) :- A2 is A + H, sum(T,A2,S).

Note that in the tail-recursive version we need to add an accumulator,
`A`, to store intermediate results. In this example, the accumulator
keeps a running total. When we get to the base case, we simply return the
accumulator. This is faster because Prolog has to keep track of far fewer
intermediate steps. In the previous version, every recursive step required
Prolog to keep track of the fact that it would need to perform the addition
later, while in the tail-recursive version the base case will return
immediately.

The tail-recursive version isn’t as friendly to use, though, since you
have to initialize the accumulator when you use it. To get around this
restriction, we can define a `sum/2` predicate that uses our
`sum/3` predicate:

sum(L,S) :- sum(L,0,S).