On the number of recursive calls of recursive functions

ABSTRACT

The advantages and disadvantages of recursion are early introduced to students. Simplicity in coding but time and space inefficiency during execution are the main characteristics. In many occasions, recursive formulae lead to recursive functions/procedures that are highly inefficient as calls with the same parameters are executed several times. Here, we elaborate on a previous report [2], where a generalized analysis is carried out to derive the number of recursive calls of a recursive formula, the calculation of the Fibonacci numbers in particular. Here we re-examine the problem using a different and simpler approach, which generalizes as well.

REFERENCES

• 1: Gilles Brassard , Paul Bratley, Fundamentals of algorithmics, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 2: John S. Robertson, How many recursive calls does a recursive function make?, ACM SIGCSE Bulletin, v.31 n.2, June 1999 [doi>10.1145/571535.571570]
• 3: Mark Allen Weiss, Data structures and algorithm analysis in C++, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1994

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Recursive function theory

General Terms:
Algorithms, Design, Theory

Keywords:
binomial coefficient, fibonacci numbers, mergesort, number of calls, recursion