[plt-scheme] structural recursion question

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Mon Jul 7 11:50:29 EDT 2008

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

Posted on the users mailing list.