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

Figure 3.5 Sierpinski's triangle
fractal obtained by the program
Sierpinski.java

until the function call stack gets full. However even if all terminal states are
scrupusously taken care of, it is impossible to prove that such a function will
terminate. This crucial limitation is known by the name of the halting problem
in computer science .
Even for simple recurrence relations, it is very challenging to mathematically
prove termination. For example, consider the Syracuse sequence of numbers
defined in § 2.5.5 as follows:

u n +1 = u n / 2

if n is even,

,

3 u n + 1 otherwise.

initialized for any given u 0 ∈ N . It is conjectured but not yet proved that for any

u 0 ≥ 1 the sequence reaches in a finite step number 1. The following program

tests experimentally the termination of the recursive function:

Program 3.17 Recursive Syracuse: Testing for termination
class RecursiveSyracuse
{ public static double Syracuse( int n)
if ( n==1) return 1;
else
if ( n%2==0) return 1+Syracuse (n/2) ; // even
else return (1+Syracuse (3 ∗ n+1)/2) ;
} public static void main( String [ ]

args )

{ for ( int i=1; i < =10000; i++)
{ System . out . println ( "Test termination for " +i ) ;
Syracuse(i);

}