# Recursion, Reduction, and Iteration ## Recursion It is often very useful to be able to refer to a sequence currently under construction, for example to define the sequence recursively. For this purpose the `Self` operator is available. ### `Self(n): RngIntElt -> Elt` ### `Self() -> SeqEnum` This operator enables the user to refer to an already defined previous entry $s[n]$ of the enumerated sequence $s$ inside the sequence constructor, or the sequence $s$ itself. ### `Example: Self (ex-5ee4f8)` The example below shows how the sequence of the first 100 Fibonacci numbers can be created recursively, using `Self`. Next it is shown how to use reduction on these 100 integers. ```magma > s := [ i gt 2 select Self(i-2)+Self(i-1) else 1 : i in [1..100] ]; > &+s; 927372692193078999175 ``` ## Reduction Instead of using a loop to apply the same binary associative operator to all elements of a complete enumerated sequence, it is possible to use the *reduction operator* `&`. ### `& ∘ S: Op, SeqEnum -> Elt` Given a complete enumerated sequence $S = [ a_1, a_2, \ldots, a_n ]$ of elements belonging to an algebraic structure $U$, and an (associative) operator $\circ : U \times U \rightarrow U$, form the element $a_1 \circ a_2 \circ a_3 \circ \ldots \circ a_n$. Currently, the following operators may be used to reduce sequences: `+, *, and, or, join, meet, cat`. An error will occur if the operator is not defined on $U$. If $S$ contains a single element $a$, then the value returned is $a$. If $S$ is the null sequence (empty and no universe specified), then reduction over $S$ leads to an error; if $S$ is empty with universe $U$ in which the operation is defined, then the result (or error) depends on the operation and upon $U$. The following table defines the return value: ``` EMPTY NULL &+ U!0 error &* U!1 error &and true true &or false false &join empty null &meet error error &cat empty null ``` ## Iteration The iteration operator `in` can be used in loops or in the set and sequence constructors to enumerate the defined elements of a sequence. When multiple range sequences are used, it is important to know in which order the range are iterated over; the rule is that the repeated iteration takes place as nested loops where the first range forms the innermost loop, etc. See the examples below. ### `x in S` ### `i -> x in S` Enumerate the defined elements of the sequence $S$. $x$ takes on the successive defined values in the sequence; if the dual iteration form is used then $i$ is the corresponding numeric index of $x$. ### `Example: Nested Iteration (ex-c6e3f6)` The first example shows how repeated iteration inside a sequence constructor corresponds to nesting of loops. ```magma > [ : number in [1..5], letter in ["a", "b", "c"]]; [ <1, a>, <2, a>, <3, a>, <4, a>, <5, a>, <1, b>, <2, b>, <3, b>, <4, b>, <5, b>, <1, c>, <2, c>, <3, c>, <4, c>, <5, c> ] > r := []; > for letter in ["a", "b", "c"] do > for number in [1..5] do > Append(~r, ); > end for; > end for; > r; [ <1, a>, <2, a>, <3, a>, <4, a>, <5, a>, <1, b>, <2, b>, <3, b>, <4, b>, <5, b>, <1, c>, <2, c>, <3, c>, <4, c>, <5, c> ] ``` This explains why the first construction below leads to an error, whereas the second leads to the desired sequence. ```magma > // The following produces an error: > [ : x in [0..5], y in [0..x] | x^2+y^2 lt 16 ]; ^ User error: Identifier 'x' has not been declared > [ : x in [0..y], y in [0..5] | x^2+y^2 lt 16 ]; [ <0, 0>, <0, 1>, <1, 1>, <0, 2>, <1, 2>, <2, 2>, <0, 3>, <1, 3>, <2, 3> ] ``` Note the following! In the last line below there are two different things with the name $x$. One is the (inner) loop variable, the other just an identifier with value $1000$ that is used in the bound for the other (outer) loop variable $y$: the limited scope of the inner loop variable $x$ makes it invisible to $y$, whence the error in the first case. ```magma > // The following produces an error: > #[ : x in [0..5], y in [0..x] | x^2+y^2 lt 100 ]; ^ User error: Identifier 'x' has not been declared > x := 1000; > #[ : x in [0..5], y in [0..x] | x^2+y^2 lt 100 ]; 59 ``` ### `Example: Dual Iteration (ex-13375d)` This example shows how dual iteration allows us to get both the index and the value simultaneously. ```magma > letters := Eltseq("abc"); > [ : i -> x in letters ]; [ <1, "a">, <2, "b">, <3, "c"> ] > for i -> x in letters do > printf "letters[%o] is %o\n", i, x; > end for; letters[1] is a letters[2] is b letters[3] is c ``` Dual iteration allows us to easily get the indices of defined elements; note the use of an underscore in the dual iteration below to ignore the values, since we do not use them. ```magma > S := [ 7, 3 ]; > S[5] := 2; > S; [ 7, 3, undef, undef, 2 ] > [ i : i -> _ in S ]; [ 1, 2, 5 ] ```