# N Factorial

```elixir
Mix.install([
  {:guesswork, "~> 0.7"}  
])
```

## Recursive Queries

```elixir
import Guesswork.Ast

alias Guesswork.Ast.And
alias Guesswork.Ast.Fact
alias Guesswork.Ast.Is
```

Looking for a factorial is a little different from some of the other queries 
we have written.
Instead generating possible values with criteria, we'll use a recursive query 
to define what a valid factorial is.
If you look below you can see some of the normal things you would see in a recursive
definition: `deffact` is used to define a base case, and `defrule` is used to define
the recursive step (where `Fact` invoces the next step).

```elixir
defmodule FactorialKB do
  use Guesswork.KnowledgeBase.Collection

  deffact n_factorial(0, 1)
  defrule n_factorial(n, f) do
    Is.new(true, [n, 0], &Kernel.>/2, halt_on_error: true)
    Is.new(true, [f, f1], &Kernel.>=/2, halt_on_error: true)
    Is.new(n, [n1, 1], &Kernel.+/2)
    Is.new(n1, [n, 1], &Kernel.-/2)
    Is.new(f, [n, f1], &Kernel.*/2)
    Fact.new(:n_factorial, [n1, f1])
  end
end
```

This can be used simillarly to other queries, like the pythagorean triple query, where 
we can pull the first `n` valid answer sets.

```elixir
Guesswork.query(term(Fact.new(:n_factorial, [n, f])), 10, knowledge_base: FactorialKB)
```

But because the query is defined in terms of `n` and `f` we can query what `f` is 
when `n` is `5`.

```elixir
Guesswork.query(term(Fact.new(:n_factorial, [5, f])), 10, knowledge_base: FactorialKB)
```

And the system supports binding `f` and searching for `n`.

```elixir
Guesswork.query(term(Fact.new(:n_factorial, [n, 120])), 10, knowledge_base: FactorialKB)
```

Even when there are multiple valid values for `n`, the query will return them all 
(provided you ask for them).

```elixir
Guesswork.query(term(Fact.new(:n_factorial, [n, 1])), 10, knowledge_base: FactorialKB)
```

## Stop Conditions

If you look above, you'll notice that even though we ask for `10` results 
from `Guesswork.query/3`, we only get the valid values, and then the query 
terminates.
This is done using stop conditions, via the `:halt_on_error` option of `Is`.

Stop conditions can also allow us to use the query to search for potentially
invalid values.

```elixir
Guesswork.query(term(Fact.new(:n_factorial, [n, 121])), 10, knowledge_base: FactorialKB)
```

Or test if a relationship is valid between some `n` and `f`.

```elixir
Guesswork.query(term(Fact.new(:n_factorial, [4, 120])), 10, knowledge_base: FactorialKB)
```

Stop conditions will terminate the entire stream after they are triggered 
(unlike normal tests, which will just disqualify individual answer sets).
But when we didn't define anything for `n` or `f`, we never triggered the stop conditions,
the query just kept returning values.

This is because the stop condition needs to be defined in terms of some concrete value.
You you can think of the recursive definition as building possible answer sets, first 
with just the base fact, then with one recursive, then two, and so on.
This is why the query is resonably fast, despite the large numbers; it doesn't have to 
search all possible numbers, just instantiate and resolve the answer sets.

But when you define `n` or `f` you need to account for the possibility that there is no
possible valid answer set, and tell the query to stop looking.
In this case we just have the system stop once it fines a recursive step with values 
greater than the values we are looking for, since the following anwser sets (which will 
all have more recursive steps) will have increasingly larger values, and therefore 
cannot be valid either.

In the unbound query, because `n` and `f` are always products of the answer set (and 
not defined by us) the stop condition cannot possibly be true.