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

particularl care of the behavior of the function stack. In particular, we shall
focus on program/function termination by inspecting the terminal states that
correspond to the trivial cases that do not need to call functions.

3.5.1 Revisiting the factorial function: A recursive
function

We have seen in § 3.2.3 an iterative algorithm for computing the factorial n !=

n 1. Let us now write the factorial function the recursive

way. First, we need to find a recurrence equation for the factorial function. We
simply get this relationship as:

× ( n − 1) × ... ×

n != n × ( n − 1) × ... × 1= n × ( n − 1)!

with 0! = 1 by definition (terminal state).

Program 3.11 Recursive implementation of the factorial function
class RecursiveFactorial
{ public static int Factorial( int n)
{ if ( n==0) return 1; // Terminal stage
else return n

∗ −

Factorial(n 1) ; // Apply recurrence

equation

}

public static void main( String [ ] arg )

{ System . out . println ( "10!=" +Factorial (10)); }

}

Compiling and executing this code, we get 10!=3628800 . Does this recursive
function always terminate? For a given integer n 0, the function Factorial

calls itself until we reach at some stage the argument n = 0. Thus the function
stack has piled n + 1 calls with the last call being Factorial(0) . At this stage,
we enter the terminal stage and return 1. Factorial(1) can return its result
1

≥

1 = 1 and it is removed from the stack. Then Factorial(2) can return its
result 2

×

1, and so on, until we return the result of Factorial(n) . Figure 3.3
illustrates the pile on process of the function call stack until it reaches the
terminal state n =0.
Note that if we call Factorial(-1) , the program will pile-on the function
stack the function calls Factorial(-2) , Factorial(-3) , etc. and stop once
the function stack gets full, generating an overflow memory problem: A stack
overflow .

×