[plt-scheme] structural recursion question
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