Recursion is the core of programming and is used in many related concepts like sorting, tree traversal, and graphs. In addition, recursion has a wide variety of uses in data structures and algorithms, and even though it is a complex concept, it can be used to make the task easier.
Recursion, in simple words, is a function calling itself. Let’s witness our first code, which literally describes the definition.
Recursion in Java
/**
This class has a recursive method.
*/
public class EndlessRecursion
{
public static void message()
{
System.out.println("This is a recursive method.");
//recursive call
message();
}
}
The above code is pretty simple. We have a class call endless recursion with a function named message, and the function prints the line “This is a recursive method.”. However, there is a problem. There’s no way to stop the recursive calls. So, this method is like an infinite loop because there is no code to stop it from repeating. So, we concluded that a recursive function also requires a termination condition to stop, just like a loop.
A simple code is demonstrated below with a termination condition.
/**
This class has a recursive method, message,
which displays a message n times.
*/
public class Recursive
{
public static void message(int n)
{
if (n > 0)
{
System.out.println("This is a recursive method.");
message(n - 1);
//After the condition is false the control returns to the end of the if
//expression and since no statement is written below the recursive
//call, the method returns.
}
}
}
Now the method message() contains an if condition that controls the repetition of the function. As long as the n parameter is greater than zero, the method displays the message and calls itself again. Let’s consider that n=5 in this case. Thus, the function message() will call itself 5 times and display the contents of the print statement. The number of times a method is called is the depth of recursion. In this case, the depth of recursion is 5. When the method reaches the sixth call, n=0. At that point, the if statement’s conditional expression is false, so the method returns.
Solving Problems with Recursion
Recursion can be a powerful tool for solving repetitive problems and is an important topic in upper-level computer science courses. What might not be clear to you yet is how to use recursion to solve a problem. Any problem that can be solved recursively can also be solved using a loop. In fact, recursive solutions are less efficient as compared to iterative solutions. However, recursion is still widely used because it makes the job of a programmer simpler.
In general, a recursive method works like this:
• If the problem can be solved without recursion, then the method solves it
and returns.
• If the problem cannot be solved, then the method reduces it to a smaller but
similar problem and calls itself to solve the smaller problem.
To apply this, we must identify at least one case in which the problem can be solved without recursion, and this is known as the base case. Then, we determine a way to solve the problem in all other circumstances using recursion. Finally, let’s consider a code that describes this recursive method.
/**
The factorial method uses recursion to calculate
the factorial of its argument, which is assumed
to be a nonnegative number.
@param n The number to use in the calculation.
@return The factorial of n.
*/
private static int factorial(int n)
{
if (n == 0)
return 1; // Base case
else
//Although this is a return statement, it does not immediately return. Before the return value
//can be determined, the value of factorial(n − 1) must be determined. The factorial
//method is called recursively until the n parameter will be set to zero.
return n * factorial(n - 1);
}Famous Recursive Problems
Some well-known recursive problems include Fibonacci series, factorial, Greatest common divisor, binary search, and many more.
Let’s start with the simplest, i.e., the Fibonacci series. The Fibonacci series is a sequence that looks something like this.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, . . .
Notice that each number in the series is the sum of the two previous numbers after the second number. Thus, the Fibonacci series can be defined as follows.
public static int fib(int n)
{
//base case 1
if (n == 0)
return 0;
//base case 2
else if (n == 1)
return 1;
else
return fib(n - 1) + fib(n - 2);
}Let’s write the whole code to test this function
/**
This program demonstrates the recursive fib method.
*/
public class FibNumbers
{
public static void main(String[] args)
{
System.out.println("The first 10 numbers in " +
"the Fibonacci series are:");
for (int i = 0; i < 10; i++)
System.out.print(fib(i) + " ");
System.out.println();
}
/**
The fib method calculates the nth
number in the Fibonacci series.
@param n The nth number to calculate.
@return The nth number.
*/
public static int fib(int n)
{
if (n == 0)
return 0;
else if (n == 1)
return 1;
else
return fib(n − 1) + fib(n − 2);
}
}
Next comes the greatest common divisor, i.e., the GCD.
The GCD of two positive integers, x, and y, is as follows:
if y divides x evenly, then gcd(x, y) = y
Otherwise, gcd(x, y) = gcd(y, remainder of x/y)
This definition states that the GCD of x and y is y if x/y has no remainder. This is the base case. Otherwise, the answer is the GCD of y and the remainder of x/y.
import java.util.Scanner;
/**
This program demonstrates the recursive gcd method.
*/
public class GCDdemo
{
public static void main(String[] args)
{
int num1, num2; // Two numbers for GCD calculation
// Create a Scanner object for keyboard input.
Scanner keyboard = new Scanner(System.in);
// Get the first number from the user.
System.out.print("Enter an integer: ");
num1 = keyboard.nextInt();
// Get the second number from the user.
System.out.print("Enter another integer: ");
num2 = keyboard.nextInt();
// Display the GCD.
System.out.println("The greatest common divisor " +
"of these two numbers is " +
gcd(num1, num2));
}
/**
The gcd method calculates the greatest common
divisor of the arguments passed into x and y.
@param x A number.
@param y Another number.
@returns The greatest common divisor of x and y.
*/
public static int gcd(int x, int y)
{
if (x %% y == 0)
return y;
else
return gcd(y, x %% y);
}
}
The output of the above program is
Enter an integer: 49 [Enter]
Enter another integer: 28 [Enter]
The greatest common divisor of these two numbers is 7Conclusion
All the methods described above have an iterative solution, but the recursive solution creates an elegant and easy write solution. In data structures like trees and graphs, recursive calls are widespread because they make the code concise and easy to understand.
