CUE does not permit general recursion. It intends to be Turing Incomplete.
That being said, there are some forms of recursion that can be represented.

Structural Recursion

CUE also disallows cyclic references.
However, this does not prevent us from defining infinite structures
such as linked lists or binary trees.
We call this structural recursion,
where the process works on a finite piece of data.

linked-list.cue

// Definition of an infinite linked list#List: { data: _ next: #List |*null// note, the default to null is required// otherwise it looks like a cyclic reference}// manually construct a linked listl: #List & {data: 1, next: #List & {data: 2}}ds: [1, 2, 4, 8]// comprehend a linked list from some datall: [ for i, d in ds { data: dif i <len(ds)-1 { next: ll[i+1] // note how we reference "future" list elements! }}]L: ll[0] // we really only want the first element

Bounded recursion is a limited form of general or generative recursion.
The problem CUE has with general recursion is that it becomes difficult or impossible
to run the evaluator and verify your CUE code.
Bounded recursion puts a limit on recursion depth,
thus making the problem not infinite and permissible under CUE’s philosophy.
There were some comments made about permitting bounded general recursion
in: https://github.com/cue-lang/cue/issues/990

In the meantime, and as a thought experiment,
you can simulate bounded recursion with a comprehension
and a function generator.
You can find the following code and examples,
as well as many more “recursive” structural helpers,
in the Cuetils project on GitHub.
There you will also find Go versions of these functions.
For any serious usage, it is highly recommended using
a language with proper general recursion support.
Cuetils provides these same helpers as a Go package
that supports CUE values as arguments.
Expect performance issues when using the CUE version
of RecurseN and the “recursive” functions built with it.

recurse.cue

packagerimport"list"#RecurseN: {// this is the bound on our recursion #maxiter: uint|*4// This is the function list element// we generate this to simulate recursion #funcFactory: { #next: _ #func: _ }// this is our "recursion unrolling"for k, v inlist.Range(0, #maxiter, 1) {// this is where we build up our indexed functions and the references between them #funcs: "\(k)": (#funcFactory & {#next: #funcs["\(k+1)"]}).#func }// our final value needs to be null #funcs: "\(#maxiter)": null// we embed the head of the list so that the values// we write this into can be used like other CUE "functions" #funcs["0"]}

depth.cue

packagerimport"list"#DepthF: { #next: _ #func: { #in: _ #basic: int|number|string|bytes|null out: {// if we have a basic type, we are at a leaf, depth is 1if (#in & #basic) !=_|_ {1}// if we are not a basic type, then we are 1 + the max of childrenif (#in & #basic) ==_|_ {// this is our "recursion" for each childlet depths = [ for k, v in #in {(#next & {#in: v}).out}]list.Max(depths) +1 } } }}#Depth: #RecurseN & {#maxiter: 11, #funcFactory: #DepthF}tree: { a: { foo: "bar" a: b: c: "d" } cow: "moo"}d: #Depth & {#in: tree}

Note the {(#next & {#in: v}).out} in the let depths = ... line.
This is “recursion” or really the reference from one of the generated “functions” to the next.

todo, show what an unrolled #Depth value looks like, this should help with understanding

We should be clear, there are no functions or calls or recursion happening here.
What we are really doing is taking an incomplete definition and creating a sequence of them,
which refer to their neighbors (the for comp in #RecurseN).
It’s a way to reduce the writing, but each “function” has its own label and is a separate value.
So we are essentially unrolling a “bounded recursion” into struct fields with a field (for) comprehension,
and using an index suffix to name them so they are independent values.

Some more examples:

pick.cue

packager#pickF: { #next: _ #func: { #X: _ #P: _ pick: {// if P is not a complex typeif (#P & ({...} | [...])) ==_|_ {// then take the leaf value if it unifies (note to dev, should there be an if here?) #P & #X }// if P is a complex typeif (#P & ({...} | [...])) !=_|_ {// for each field in Pfor i, p in #P {let x = #X[i]// if they unify (samish type)if (x & p) !=_|_ {// if not a struct, pick the valueif (x & {...}) ==_|_ {"\(i)": x }// if it is a struct, then "recurse"if (x & {...}) !=_|_ {"\(i)": (#next & {#X: x, #P: p}).pick } }// if they do not unifyif (x & p) ==_|_ {// and if struct, then recurseif (x & {...}) !=_|_ {"\(i)": (#next & {#X: x, #P: p}).pick } } } } } }}#Pick: #RecurseN & {#funcFactory: #pickF}tree: { a: { foo: "bar" a: b: c: "d" } cow: "moo"}P: { a: foo: string cow: "moo"}p: #pick & {#X: tree, #P: P}

diff.cue

packager#DiffF: { #next: _ #func: { #X: _ #Y: _ diff: { {for i, x in #X {let y = #Y[i]if y ==_|_ {"-": "\(i)": x }if y !=_|_ {if (x & {...}) !=_|_ {"\(i)": (#next & {#X: x, #Y: y}).diff }if (x & {...}) ==_|_ {if (x & y) ==_|_ {"-": "\(i)": x"+": "\(i)": y } } } } }"+": {for i, y in #Y {if #X[i] ==_|_ {"\(i)": y } } } } }}#diff: #RecurseN & {#funcFactory: #DiffF}ex: { x: { a: "a" b: "b" d: "d" e: { a: "a" b: "b" d: "d" } } y: { b: "b" c: "c" d: "D" e: { b: "b" c: "c" d: 1 } } diff: (#diff & {#X: x, #Y: y}).diff}