Java Reference

In-Depth Information

Recursive Functions

A
recursive function
is one that invokes itself until a certain condition is met. It is a useful

tool to use when iterative processes are involved. A common example is a function that cal-

culates the
factorial
of a number:

function factorial(n) {

if (n === 0) {

return 1

} else {

return n * factorial(n - 1);

}

}

This function will return
1
if
0
is provided as an argument (0 factorial is 1), otherwise it

will multiply the argument by the result of invoking itself with an argument of one less. The

function will continue to invoke itself until finally the argument is
0
and
1
is returned. This

will result in a multiplication of 1, 2, 3 and all the numbers up to the original argument.

Another example from the world of mathematics is the
Collatz conjecture.
This is a problem

that is simple to state, but, so far, has not been solved. It involves taking any positive integer

and following these rules:

• if the number is even, divide it by two

• if the number is odd, multiply it by three and add one

For example, if we start with the number 18, we would have the following sequence:

18, 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, ...

As you can see, the sequence becomes stuck in a loop at the end, cycling through “4,2,1”.

The Collatz conjecture states that every positive integer will create a sequence that finishes

in this loop. This has been verified for all numbers up to 5 × 2
⁶⁰
, but there is no proof that

it will continue to be true for all the integers higher than this. To test the conjecture, we can

write a function that uses recursion to keep invoking the function until it reaches a value of

1
(because we want our function to avoid being stuck in a recursive loop at the end!):