“Curiouser and curiouser” said alice. further reflections on an interesting recursive function

Abstract

In this paper the close relationship between a previously investigated recursive function and the familiar Fibonacci sequence is established. An efficient iterative program for the computation of the recursive function, which is based on this relationship, is given. The correctness of the program follows from an earlier proof of equivalence of the recursive function and a function based on the Fibonacci sequence. The structural dissimilarity of the functional specification and the implementation suggests that it is unlikely that the latter can be generated from the former using standard transformation techniques.

Keywords:

• Recursive function
• Fibonacci sequence
• program verification

C.R. Categories:

• F.3
• G.0