Functions and Recursive Functions - A Concise and Practical Introduction to Programming Algorithms in Java - page 74

The recursive program below implements the logarithmic mean computation:

Program 3.13 Logarithmic mean
static double LogarithmicMean( double [ ] array , int i, int j)
// Terminal case: One element. The mean is always this
element
if (j − i ==0) return array [ i ];
else
int n=j − i+1;
return (n − 1) ∗ (LogarithmicMean( array , i +1, j ) − LogarithmicMean(
array , i , j − 1))/(Math. log (array [ j ]) − Math. log (array [ i ]) ) ;

}
}

static double LogarithmicMean( double [] array)
return LogarithmicMean( array ,0 , array . length

− 1) ;

}

3.6 Terminal recursion for program e ciency **

Although it is quite easy to write recursive functions once recurrence equations
and terminal states are clearly identified, the main drawback of using recursive
programs in practice is eciency. Indeed, every time we call a function, the
Java Virtual Machine (JVM) has to allocate some local memory for the local
variables declared inside the body of the function. Then it has to perform the
pass-by-value of arguments. Another major issue is that the function stack
is limited in its size, and it is quite easy in practice to reach stack overflow
problems. Terminal recursion is a principle that solves these time and memory
problems while keeping the essence of recursion. A recursive function is said to
be terminal if and only if wherever the function calls itself it is with the following
simple expression f(...); . In other words, a function is terminal recursive if all
its return paths are of the form return f(...); . Terminal recursion is effective
because it simply allows one to branch former arguments into new arguments by
performing various expression evaluations on parameters only. Therefore there
is no need to use the stack function calls, and no stack overflow problems are
occurring when using terminal recursion. In other words, arguments of terminal
recursive functions play the role of accumulators .
Let us reconsider the factorial recursive function:
if (n<=1) return 1; else
return n*f(n-1);