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

	
	

    
	

	
 
    Next: Main Menu