# Recursive Sequences

In mathematics, many sequences are conveniently expressed in a recursive manner. Here are some examples:

• Arithmetic sequences: a(n) = a(n-1) + d, where d is the common difference (e.g. 1,4,7,10,13,...)
• Geometric sequences: a(n) = a(n-1) * r where r is the ratio (e.g. 1,3,9,27,81,...)
• Factorial: f(n) = f(n-1) * n (i.e. 1,2,6,24,120,...)
• Fibonacci numbers: f(1) = 0, f(2) = 1, f(3) = 0 + 1, f(n) = f(n-2) + f(n-1) where n > 2 (i.e. 0,1,1,2,3,5,8,13,...)
• These are called recursive sequences, because the Nth term of the sequence can be expressed using the previous terms. In Smojo, a recursive sequences are defined using 2 words:

Word Action
`{: ( -- rseq )`
This word is called RSEQ, and it puts an empty recursive sequence on the stack.
`;} ( rseq seq -- seq )`
This word is called END-RSEQ, and its purpose is to complete the recursive sequence. It takes the original recursive sequence as its first argument, and the recursively defined body (explained below) as its second argument. The result is a completed recursive sequence on the stack.

## Examples

Example 1

Consider the sequence ( 1, 0, 1, 0, ... )

Clearly, this sequence is of the form αnew = ( 1, 0, αold ). This is a simple recursive definition for this sequence, and we can create it this way:

```
{:			/ this puts α (which is currently empty) on the stack
dup 0 cons 1 cons	/ this duplicates α and uses it to create the sequence body, ( 1, 0, α )
;}  			/ this completes the recursive sequence α=( 1, 0, α )

10 take .list
1 0 1 0 1 0 1 0 1 0 ok
```
Example 2: Generating the Fibonacci series

The fibonacci series starts with 0, 1 ... Subsequent terms are the sum of the previous two terms. So, this sequence can be expressed as αnew = ( 0, 1, αold ) + ( 1, αold ) where "+" is element-wise addition:

```
{:			/ this puts α (which is currently empty) on the stack
dup 1 cons 0 cons	/ this duplicates α and uses this α to create the sequence ( 0, 1, α )
dup tail		/ this duplicates (0,1,α) and uses it to create the sequence ( 1, α )
' + zipwith		/ this does the element-wise summation on the two sequences
;}  			/ this sets α = ( 0, 1, α ) + ( 1, α )

10 take .list
1 2 3 5 8 13 21 34 55 89 ok
```

## Quiz

### Question 1

Given any finite sequence, write a word
`REPEAT ( seq -- seq )`
that creates a new sequence which is an unending repetition of the input.

### Question 2

Given a sequence s = (s0, s1, s2, ... ), write a word
`CUMULANT ( seq -- seq )`
which creates a new sequence cumulant(s) = (s0, s0 + s1, s0 + s1 + s2, ... )

### Question 3

Write the word
`...`
in terms of
`REPEAT`
and
`CUMULANT`
.

### Question 4*

Generalize
`CUMULANT`
to
`ACCUMULATE ( seq x0 xt -- seq )`
So that
`CUMULANT`
can be expressed this way:
```
: CUMULANT ( seq -- seq )
0 ['] + ACCUMULATE ;
```

### Question 5

Use
`ACCUMULATE`
to write
`PRODUCTS ( seq -- seq )`
which given a sequence sequence s = (s0, s1, s2, ... ) will return the sequence products(s) = (s0, s0*s1, s0*s1*s2, ... ).

### Question 6*

Given any sequence, s, write the word
`TAILS ( seq -- seq )`
that creates a new sequence tails(s) = (s, tail(s), tail(tail(s)), ...). Does your word work on finite sequences?

### Question 7

An algorithm is said to be iterative if both its running time and space requirements are at worst directly proportional to the number of terms it needs to process. For example, the algorithm:

```
: MAXES ( seq -- n )
dup head swap ['] max reduce ;
```
is iterative because it uses just 1 slot on the stack and its run time is directly proportional to the length of the sequence being examined. Seen this way, is the Fibonacci recursive sequence an iterative algorithm? Carefully defend your answer. How about your answer for
`CUMULANT`