A function can be recursive; that is, the name of a function may be used in its own body.

def sumto(n) = if n < 1 then 0 else n + sumto(n-1)

The call sumto(5) publishes 15.

A recursive function may run forever, publishing an infinite number of times. The function metronome is a classic example; a call to metronome publishes a signal once per second, forever:

def metronome() = signal | Rwait(1000) >> metronome()

Mutual recursion is also supported.

def even(n) = 
  if (n :> 0) then odd(n-1)
  else if (n <: 0) then odd(n+1)
  else true
def odd(n) = 
  if (n :> 0) then even(n-1)
  else if (n <: 0) then even(n+1)
  else false

There is no special keyword for mutual recursion; any contiguous sequence of function declarations is assumed to be mutually recursive. Also, note that :> and <: are the Orc symbols for 'greater than' and 'less than' respectively.

The combination of functions and pattern matching offers a powerful capability: clausal definition of functions. We can define expressions which execute different code depending on the structure of their arguments.

Here's an example.

def sum([]) = 0
def sum(h:t) = h + sum(t)

sum(l) publishes the sum of the numbers in the list l. It has two clauses: one which matches the empty list, and one which matches any nonempty list. If its argument is an empty list, it returns 0, the appropriate sum for an empty list. If the argument is a nonempty list, it adds the first element of that list to the sum of all of the other elements. In this way, it recursively finds the sum of the list.

A function may have multiple clauses, each of which has a sequence of patterns to match each argument, and a body expression. Naturally, all clauses of a function must have the same number of arguments. Any contiguous sequence of definitions with the same name and different arguments is interpreted as a clausal definition, where each individual declaration is a clause of the larger function.

When the function is called, the clauses are tried in the order in which they appear until a match is found. If no clause matches, the call remains silent.

We can use a literal pattern to define the base case of a recursive function in a straightforward way.

{- Fibonacci numbers -}
def fib(0) = 1
def fib(1) = 1
def fib(n) = fib(n-1) + fib(n-2)

This definition of the Fibonacci function is straightforward, but slow, due to the repeated work in recursive calls to fib. We can define a linear-time version, again with the help of pattern matching:

{- Alternate definition of the Fibonacci function -}

{- A helper function: find the pair (Fibonacci(n), Fibonacci(n+1)) -}
def H(0) = (1,1)
def H(n) = H(n-1) >(x,y)> (y, x+y)

def fib(n) = H(n) >(x,_)> x

As a more complex example of matching, consider the following function which takes a list argument and returns a new list containing only the first n elements of the argument list.

def take(0,_) = []
def take(n,h:t) = h:take(n-1, t)

Each clause of a function definition may also have a guard: a Boolean expression which determines whether or not the clause applies. If the guard publishes false, then the next clause is tried, just as if some pattern had failed to match.

We can add guards to a previous example to protect against the degenerate case of a negative argument:

{- Fibonacci numbers -}
def fib(0) = 1
def fib(1) = 1
def fib(n) if (n :> 1) = fib(n-1) + fib(n-2)

We can also improve the readability of a previous example:

def even(n) if (n :> 0) = odd(n-1)
def even(n) if (n <: 0) = odd(n+1)
def even(0) = true 
def odd(n) if (n :> 0) = even(n-1)
def odd(n) if (n <: 0) = even(n+1)
def odd(0) = false