[plt-scheme] structural recursion question

Structural recursion means that the layout of the template follows  
the layout of the data definition. It's a crutch to help you design  
programs. Since fib is a mathematically defined function, you don't  
need help designing it. Just type it in.

-- Matthias



On Jul 7, 2008, at 11:37 AM, Arthur Nunes-Harwit wrote:

> 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
>
>
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme