Recursion:

In order to understand recursion, you must first understand recursion

With defs

If you define the signature of the function before the definition, the definition can be recursive, e.g.

def fib : data -> data                               // THIS LINE IS NEEDED!
def fib = (n -> if (n <= 2) 1 else n + fib(n-1))

If you need several functions that are mutually recursive, just write several signatures before starting with the first definition:

def countNumbers : data -> data
def countNumbersInArray : data -> data
def countNumbersInMap : data -> data
def countNumbers =
  (x ->
    let dc = datacase(x);
    if (dc == "number") 1
    else if (dc == "array") countNumbersInArray(x)
    else if (dc == "object") countNumbersInMap(x)
    else 0
  )
def countNumbersInArray =
  (x ->
    array.reduce((x_k,acc) -> acc + countNumbers(x_k), 0, x)
  )
def countNumbersInMap =
  (x ->
    map.reduce((x_k,acc) -> acc + countNumbers(x_k), 0, x)
  )

For example, countNumbers([1,2,false,"hi",[1,2,null,{a:56}]]) returns 5 (there are in total 5 numbers in this data structure).

But not with cells!

With cells, this does not work:

cell fib : data -> data
cell fib = (n -> if (n <= 2) 1 else n + fib(n-1))    // GIVES AN ERROR!

The interpretation is differently: It’s a cycle in the dependency graph, and the compiler will reject this.

Local recursion

Inside a def there is also a way to have local recursive functions with the help of the recursion combinator recurse. For example, a local Fibonacci function would look like:

def fibonacci =
  recurse((selfcall, n) -> if (n <= 2) 1 else n + selfcall(n-1))

Instead of using fibonacci(x-1) as the recursive call we have to write here selfcall instead.

There’s also a recursion combinator for two parameters: recurse2(selfcall, x1, x2).