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!):
