- Ko
- 2. Language
**2.3. Varieties and recursion**

**2.3. Varieties and recursion**Ko has lambdas (functional values) and closures (creating functional values by fixing some or all arguments) as in other languages. In Ko, functional values are called varieties , whereas the operation of fixing arguments of a variety (to produce a new, restricted variety) is called augmentation .

The exact syntax of augmentation is described in the syntax chapter . In brief, augmentation uses the same syntax as invocation, replacing the round brackets,

`()`

, with square ones,`[]`

. In the following example we assume that a function`Max3(a, b, c)`

which returns the maximum of its three arguments is given.`ReturnTheMax(x, y, z) { max2: Max3[a: x] // fix the a-argument of Max3 to x max1: max2[b: y] // fix the b-argument of max2 to y max0: max1[c: z] // fix the c-argument of max1 to z return: max0() }`

Calling

`ReturnTheMax(x: p, y: q, z: r)`

(for some arguments`p`

,`q`

and`r`

) is equivalent to calling`Max3(a: p, b: q, c: r)`

.## Recursion

Varieties are particularly important when implementing recursive functions. Consider the following implementation of a function computing the n-th Fibonacci number.

`import "integer" Fib(n?) { branch: Yield( if: Or( // If n is a base case (0 or 1), integer.Equal(n, 0) integer.Equal(n, 1) ) then: [1] // then Yield returns a variety that will return 1 when invoked, else: fibSum[n] // otherwise Yield returns a variety for the recursive step. ) return: branch() // Whichever variety was returned, invoke it. } fibSum(m?) { return: integer.Sum( Fib(integer.Sum(m, -1)) Fib(integer.Sum(m, -2)) ) }`

The key point in this example is that the

`Yield`

step does not invoke the recursive function`fibSum`

, rather it returns a variety to it. If the function were to be invoked (by writing`fibSum(n)`

instead of`fibSum[n]`

), then`Fib`

would hang in an infinite recursive loop. This follows from the rule that once a function starts executing (in this case`Fib`

) all of its elements will be executed and waited on to complete before the function completes itself.