In programming, recursion refers to the process in which a function calls itself directly or indirectly. Recursion is used to solve a number of problems in computer science.
The Java programming language supports creating recursive methods, which are methods that call themselves.
In this tutorial, we are going to discuss, with reference to examples, how recursion works, and how you can create a recursive function in Java. After reading this guide, you’ll be an expert at writing recursive methods in Java.
Java Methods
Methods, sometimes called functions, are blocks of code that perform a specific task. For instance, a method could be used to calculate the sum of an array of values or print out the contents of an array to the console.
Here’s the syntax for a method in Java:
modifier static returnType methodName (Parameters) { // Method body }
For instance, suppose you wanted to create a method that printed out the sentence “It’s Wednesday! We’re half-way through the week!” to the console. You could do so using this code:
class Main { public static void printItsWednesday() { System.out.println("It's Wednesday! We're half-way through the week!"); } public static void main(String[] args) { printItsWednesday(); } }
When we call this method using printItsWednesday()
, the following is returned:
It’s Wednesday! We’re half-way through the week!
If you’re interested in learning more about Java methods, you can read our complete guide to methods in Java here.
In our above example, we call the prinItsWednesday()
method in the main program. But if we were to call our method in the method itself, we would have created a recursive method.
Java Recursion
Recursive methods are methods that are called within the main method at first and then are called within the method itself. Here’s the syntax for a recursive method:
static void executeMethod() { // Code here executeMethod(); // This is our recursive call // Code here } public static void main(String[] args) { executeMethod(); // This is the normal method call }
When we run our program, the executeMethod()
method is called in our main program. This causes the code in the executeMethod()
method to be run, which in this case includes the executeMethod()
method. So, when our program runs, it will enter a loop.
The program will continue executing the executeMethod()
method until a condition is met that prevents it from continuing. If no conditions are specified that could stop the recursion, the program will run on forever. This is referred to as infinite recursion.
Why should you use recursion? First, recursion can reduce the time complexity of a program in certain cases. Second, recursion can make it easier for you to implement some algorithms in a more readable and maintainable way.
Here are a few examples of programs which are often written using recursion:
- Calculating the fibonacci sequence
- Reversing a string
- Calculating a factorial of a number
- Calculating the height of a binary tree
That said, recursion can be slower than writing a standard method to perform a task. This is because recursion creates a new storage location for variables every time a recursive method is executed.
Java Recursion Examples
Let’s walk through two examples to demonstrate how recursion works in Java.
Reversing a String Using Recursion
Suppose we are building a program for a middle school teacher that reverses a string with each student’s grades throughout the year. The string starts with the first grade the student received and ends with the most recent grade the student has earned. We want to reverse the string so the last, or most recent, grade earned by the student is first in the string.
We could use the following code to reverse the string:
public class ReverseGrades { public static String reverse(String grades) { if (grades.isEmpty()) return grades; return reverse(grades.substring(1)) + grades.charAt(0); } public static void main(String[] args) { String grades = "CBCBAABACAABA"; String reverse_grades = reverse(grades); System.out.println("This student's grades for the year are: " + reverse_grades); } }
Our code returns:
This student’s grades for the year are: ABAACABAABCBC
As you can see, our program has reversed the contents of our string. In our program, we have created a recursive function called reverse()
.
When the reverse()
function is executed, first check if the grades string is empty. If it is, we return the list of grades to the main program. This stops the recursion because the reverse()
call at the end of the function is not given the chance to run.
If the grades string is not empty, our program will execute the reverse()
method again and concatenate the result of the function to the first character of the sentence. We use the charAt()
method in our example to retrieve the first character in the sentence, and add it to the left side of the reverse()
method.
After our string has been reversed, a message stating This student’s grades for the year are:
“, followed by the reversed string of student grades, is returned to the program.
Calculating a Factorial Using Recursion
Another instance where recursion can be useful is in calculating the factorial of a number.
In math, factorials are the product of all positive integers less than or equal to a number multiplied together. For instance, the factorial of 5 is equal to 5*4*3*2*1, which is 120. Because factorial methods involve a repetitive calculation, they are a good real-life example of where recursion can be useful in solving a problem.
"Career Karma entered my life when I needed it most and quickly helped me match with a bootcamp. Two months after graduating, I found my dream job that aligned with my values and goals in life!"
Venus, Software Engineer at Rockbot
The following Java program allows us to calculate a factorial of the number 7 in Java:
class Main { static int calculateFactorial(int number) { if (number != 0) return number * calculateFactorial(number-1); else return 1; } public static void main(String[] args) { int num = 7; int answer = calculateFactorial(num); System.out.println("The factorial of 7 is: " + answer); } }
Our code returns:
The factorial of 7 is: 5040
In this example, we create a method called calculateFactorial()
that multiplies the number stored in the number parameter by the result of the next calculateFactorial()
method. This process executes until the number parameter is equal to 0.
When the number parameter is equal to 0, the if statement in our code returns 1 and the result of the calculateFactorial()
method is passed back to the main program.
So, the calculateFactorial()
method performs 7*6*5*4*3*2*1, then returns the answer to the main program. Once the answer has been calculated, the message The factorial of 7 is:
, followed by the answer calculated by our program, is printed to the console.
Conclusion
Recursion is a concept in programming used to describe a method that calls itself. Recursive methods can be useful in cases where you need to repeat a task multiple times over and use the result of the previous iteration of that task in the current iteration.
This tutorial walked through the basics of recursion in Java and how to create recursive methods. In addition, this tutorial walked through two examples of recursion in action, with reference to reversing a string and calculating a factorial.
You’re now ready to start working with recursive methods in Java like a professional!
About us: Career Karma is a platform designed to help job seekers find, research, and connect with job training programs to advance their careers. Learn about the CK publication.