Copyright

Practical Application for Data Structures: Recursion in Java

Instructor: Martin Gibbs

Martin has 16 years experience in Human Resources Information Systems and has a PhD in Information Technology Management. He is an adunct professor of computer science and computer programming.

In this practical lesson, you will create an algorithm that uses recursion to calculate factorials. You will be able to build, compile, run, and test your program.

Lesson Overview & Knowledge Required

You will be creating a program that generates the factorial of a given number. A factorial is expressed in math as:

n! = n ∗ (n - 1) ∗ (n - 2) ∗ … ∗ (2) ∗ (1)

What this means is that the number is a product of all positive integers that are less than or equal to n. Five factorial is written as:

5! = 5 x 4 x 3 x 2 x 1

The final answer is 120.

For this exercise, you should be able to create a new program in Java, declare variables, methods, and display output to the screen. You should also have an understanding of logic testing (if/then/else statements), and modulo division. We will be taking user input in this lesson but will provide the code.

Program Code

The program code for this lesson was developed, compiled, and tested using NetBeans IDE 8.2. This code imports the Java utility so that it can collect user input.

First, create the Java application (in our example the name of the application is Recursion):

package recursion;
import java.util.*;
public class Recursion {
  public static void main(String[] args) {
  }
}

After the curly bracket that ends the main method, enter the method that calculates the factorial of a number. This is a recursive method because it calls itself. Notice that there is an important 'if' statement at the beginning. Without this check, the method would never exit.

The return statement is the actual recursive line of code because it calls itself when it calculates the value. Imagine that the value of the input integer is 5. The code runs the following check:

  • Is 5 equal to 1? No, continue:
  • Return 5 ∗ (5 - 1) = 5 x 4 = 20
  • Call the method again but now input is 4
  • Continue until the value is 1

Enter the following method after the ending curly bracket of the main function but before the ending curly bracket of the Recursion class.

public static long calcFactorial(int input) {
   if (input == 1) {
    return 1
   }
  return input * calcFactorial(input - 1);
}

Next, return to the main method and enter the following code to ask for input from the user:

  System.out.println("Enter Integer for Factorial: " );
  Scanner newInput = new Scanner(System.in);
  int tester = newInput.nextInt();

In order to calculate the factorial for the given number, we will need to call the doFactorial method we created and pass an integer value (the value entered by the user) to it. We can do this all within the output statement:

  System.out.println("The factorial of " + tester + " = " + calcFactorial(tester));

Compile and run the program. Enter 7 for the integer. The result will be 5040.

Code Application

Now that you have created the basic program to calculate a factorial, you should be able to use recursion to solve another mathematical problem: the greatest common divisor between two numbers.

Recall modulo division: In modulo division (x % y), the result is 0 if there is no remainder. For example, 8 % 4 = 0.

Create a new Java file called GCD. The majority of the main method and the calculate GCD method is below:

package gcd;
public class GCD {
  public static void main(String[] args) {
   int a = 108;
   int b = 48;
   System.out.println("GCD of a and b is" + calcGcd(a, b));
  }
  //method to calculate the GCD
  public static long calcGcd(int a, int b) {
   if(??) {
    return ????
   } else {
    return a;
   }
  }
}

Complete the code that is indicated by question marks.

To unlock this lesson you must be a Study.com Member.
Create your account

Register for a free trial

Are you a student or a teacher?
I am a teacher

Unlock Your Education

See for yourself why 30 million people use Study.com

Become a Study.com member and start learning now.
Become a Member  Back

Earning College Credit

Did you know… We have over 160 college courses that prepare you to earn credit by exam that is accepted by over 2,000 colleges and universities. You can test out of the first two years of college and save thousands off your degree. Anyone can earn credit-by-exam regardless of age or education level.

To learn more, visit our Earning Credit Page

Transferring credit to the school of your choice

Not sure what college you want to attend yet? Study.com has thousands of articles about every imaginable degree, area of study and career path that can help you find the school that's right for you.

Create an account to start this course today
Try it free for 5 days!
Create An Account
Support