How many recursive calls does a recursive function make?

ABSTRACT

The calculation of the Fibonacci sequence using recursion gives rise to an interesting question: How many times does a recursive function call itself? This paper presents one way to examine this question using difference equations with initial conditions, or discrete dynamical systems (DDS). We show that there is a linear relationship between the Fibonacci numbers themselves and the number of recursive calls. This relationship generalizes to any type of DDS of second-order, and DDS of higher-order.

REFERENCES

• 1: D. C. Arney, F. R. Giordano, J. S. Roberston, Discrete Dynamical Systems: Mathematics, Methods, and Models, McGraw-Hill, New York, 1998.