# [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
*