| | |
Knowing that a method can invoke other methods within its body, a natural question arises: "Can one invoke a method from within the body of that same method?" The answer is a firm yes -- such methods are called recursive.
As a simple example, recall that in mathematics, the factorial function is defined by
$$n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1$$
Writing a method to compute $n!$ is fairly easy with a for loop, as the below example shows:
public static long factorial(int n) {
long product = 1;
for (int i = 2; i <= n; i++) {
product *= i;
}
return product;
}
However, we can even more elegantly write a method to calculate the factorial of a value recursively:
public static long factorial(int n) {
return (n == 0 ? 1 : n * factorial(n-1));
}
Note, when factorial() is invoked inside of its own definition, that invocation is applied to a smaller case than the one initially called (i.e., factorial(n-1) as compared to factorial(n)). This is in general true of all recursive methods. Consequently, a sequence of method calls result, each one in some sense "smaller" than the previous one. For example, if some bit of code invoked factorial(5), then in the process of calculating that value, factorial(4) would be called, and factorial(3) to accomplish that, and so on.
However, so that this doesn't result in an infinite chain of method calls, we need to ensure this process terminates at some point. As such, we must check to see if we are in the "smallest" case (called the base case) before calling the method with a "smaller" case. For the factorial function, we note that $n! = n \times (n-1)!$ for all $n > 0$, but this identity does not hold for smaller $n$. Thus the "smallest" case for the factorial functions occurs when we seek factorial(0). There is no additional calculation that needs to be done -- we simply return 1.
Noting that the greatest common divisor of any two numbers must also divide their difference (and ultimately the remainder of one upon division by the other), we can write a recursive method to calculate it:
public static int gcd(int a, int b) {
return (a % b == 0 ? b : gcd(b, a%b));
}
To reverse a string, we can use a recursive method as well:
public static String reverse(String s) {
return (s.length() <= 1 ? s : reverse(s.substring(1)) + s.charAt(0));
}
public static void countDown(int n) {
if (n == 0) {
System.out.println("Lift Off!");
}
else {
System.out.println(n);
countDown(n-1);
}
}
Recursive methods can be compact and elegant, but under certain circumstances, the time needed to complete a recursive method can grow exponentially with the size of the problem the method hopes to solve due to excessive recomputation. For example, the Fibonacci sequence $0,1,1,2,3,5,8,13,21,34,55,89,\ldots$ can be defined by $F_n = F_{n-1} + F_{n-2}$ for $n \ge 2$ and $F_0 = F_1 = 1$. This might lead one to try to write a recursive method to calculate the $n^{th}$ Fibonacci number in the following way:
public static long fibonacci(int n) {
return (n < 2 ? 1 : fibonacci(n-1) + fibonacci(n-2);
}
Unfortunately, the above code is terribly inefficient. Consider the computation of fibonacci(8) = 21. We first compute fibonacci(7) = 13 and fibonacci(6) = 8. But to do that, we recursively compute fibonacci(6) = 8 again and fibonacci(5) = 5. From here, things start to get rapidly worse. Indeed, to compute fibonacci(8), calls are made to compute fibonacci(1) or fibonacci(0) a grand total of $34$ times!