[plt-scheme] structural recursion question

From: Arthur Nunes-Harwit (anh at cs.rit.edu)
Date: Mon Jul 7 11:37:40 EDT 2008

Hi,

   I'm not sure if this is the right list for this question, but here 
goes...

   Structural recursion on natural numbers seems to have the following 
template.

   (define (f n)
     (if (zero? n)
         ... ; answer for zero case
         ... (f (sub1 n)) ...)) ; answer for positive case

   Is naive Fibonacci structurally recursive?  It seems to not quite fit, 
since there are two base cases.  However, it isn't generative recursive or 
accumulative recursive.  But accumulative and generative recursive 
formulations provide the same kind of speed ups.  It seems as though 
Fibonacci could be a nice example, but where does it fit in?

(It looks to me as though structural recursion is a generalization of the 
rules for constructing the primitive recursive functions.  But showing 
that Fibonacci is primitive recursive involves sequencing.)

   Thanks.

-Arthur




Posted on the users mailing list.