# Recursive Sequences

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

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 wordREPEAT ( seq -- seq )that creates a new sequence which is an unending repetition of the input.

: REPEAT ( seq -- seq ) {: tuck swap consa ;} ;

### Question 2

Given a sequence s = (s_{0}, s

_{1}, s

_{2}, ... ), write a word

CUMULANT ( seq -- seq )which creates a new sequence cumulant(s) = (s

_{0}, s

_{0}+ s

_{1}, s

_{0}+ s

_{1}+ s

_{2}, ... )

: CUMULANT ( seq -- seq ) {: tuck 0 cons ['] + zipwith ;} ;

### Question 3

Write the word...in terms of

REPEATand

CUMULANT.

: ... ( a b -- seq ) over - \ a d nil swap cons repeat \ a {d} swap cons cumulant ;

### Question 4*

GeneralizeCUMULANTto

ACCUMULATE ( seq x0 xt -- seq )So that

CUMULANTcan be expressed this way:

: CUMULANT ( seq -- seq ) 0 ['] + ACCUMULATE ;

: ACCUMULATE ( seq x0 xt -- seq ) >R >R {: swap over over head cons swap tail R> cons R> zipwith ;} ;

### Question 5

UseACCUMULATEto write

PRODUCTS ( seq -- seq )which given a sequence sequence s = (s

_{0}, s

_{1}, s

_{2}, ... ) will return the sequence products(s) = (s

_{0}, s

_{0}*s

_{1}, s

_{0}*s

_{1}*s

_{2}, ... ).

: PRODUCTS ( seq -- seq ) 1 ['] * accumulate ;

### Question 6*

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

: TAILS ( seq -- seq ) { b } {: dup ['] tail map b cons ;} b [‘] drop zipwith \ make sure seq stops at length of b. ;

### 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? Again, offer proof to support your answer.

Fibonacci sequence algorithm is iterative: fixed number of stack space, run time proportional to number of elements generated.
Cumulant algorithm is also iterative