# Java Recursion

Welcome to my Java Recursion tutorial. In the video below, I’m going to cover java recursion in 5 different ways. I figured if I show it using many different diagrams that it will make complete sense.

A recursive method is just a method that calls itself. As these calls are made the problem gets simpler until you reach a condition that leads to the method no longer making calls upon itself. This is known as the base case. The video and code below will make recursion easy to understand. I also cover the Merge Sort.

If you like videos like this, it helps to tell Google+ [googleplusone]

Code From the Video

Recursion.java

```public class Recursion {

public static void main(String[] args) {

Recursion recursionTool = new Recursion();

// Demonstrate what a triangular number is
// Triangular numbers can be visualized as triangles
// Equals itself plus every number before it to 1
// TN of 5 = 5+4+3+2+1

recursionTool.calculateSquaresToPrint(10);

System.out.println("\nTriangular Number: " + recursionTool.getTriangularNum(3) + "\n");

System.out.println("GET TRIANGULAR NUMBER");

System.out.println("Recursion Triangular Number: " + recursionTool.getTriangularNumR(6));

System.out.println("\nGET FACTORIAL");

System.out.println("Factorial: " + recursionTool.getFactorial(3));

}

// Calculate triangular number not using recursion

public int getTriangularNum(int number){

int triangularNumber = 0;

while(number > 0){

triangularNumber = triangularNumber + number;
number--;

}

// If number equals 3, you find TN by adding 3+2+1 = 6

return triangularNumber;

}

// Calculate triangular number using recursion

public int getTriangularNumR(int number){

// Every recursive method must have a condition that
// leads to the method no longer making another method
// call on itself. This is known as the base case

System.out.println("Method " + number);

if(number == 1){

System.out.println("Returned 1");

return 1;

} else {

int result = number + getTriangularNumR(number - 1);

System.out.print("Return " + result);

System.out.println(" : " + number + " + getFactorial(" + number + " - 1)");

return result;

}

}

// Returns the factorial of a number
// factorial(3) = 3 * 2 * 1

public int getFactorial(int number){

System.out.println("Method " + number);

if(number == 1){

System.out.println("Returned 1");

return 1;

} else {

int result = number * getFactorial(number - 1);

System.out.print("Return " + result);

System.out.println(" : " + number + " * getFactorial(" + number + " - 1)");

return result;

}

}

// USED TO DEMONSTRATE TRIANGULAR NUMBERS --------------------

// Draws the number of squares that are passed in horizontally

public void drawSquares(int howManySquares){

for(int i = 0; i < howManySquares; i++) System.out.print(" --  ");

System.out.println();

for(int i = 0; i < howManySquares; i++) System.out.print("|" + howManySquares + " | ");

System.out.println();

for(int i = 0; i < howManySquares; i++) System.out.print(" --  ");

System.out.println("\n");

}

// Outputs the number of squares to print to represent a triangle

public void calculateSquaresToPrint(int number){

for(int i = 1; i <= number; i++){

for(int j = 1; j < i; j++){

drawSquares(j);

}

System.out.println("Triangular Number: " + calcTriangularNum(i));

}

}

public double calcTriangularNum(int number){

return .5 * number * (1 + number);

}

}```

MergeSort.java

```import java.util.Arrays;

public class MergeSort {
public static void main(String a[]) {

int array[] = { 10, 8, 4, 80, 13, 1, 3, 11 };

System.out.println("STARTING ARRAY\n");

printHorzArray(-1, -1, array, 49);

System.out.println();

// Send the array, 0 and the array size

mergeSort_srt(array, 0, array.length - 1);

System.out.print("FINAL SORTED ARRAY\n");

printHorzArray(-1, -1, array, 49);

}

// Receives the array, 0 and the array size

public static void mergeSort_srt(int array[], int lo, int n) {
int low = lo;
int high = n;

if (low >= high) {
return;
}

// Find the middle index of the array

int middle = (low + high) / 2;

// CREATE 2 ARRAYS FROM THE ONE

// Send the array, 0 and the middle index of the array

mergeSort_srt(array, low, middle);

// Send the array, the middle index + 1 and the highest
// index of the array

mergeSort_srt(array, middle + 1, high);

// Store the last index of the first array

int end_low = middle;

// Store the first index of the second array

int start_high = middle + 1;

// If the lowest index is less than or equal to the bottom arrays
// highest index & the lowest index of the 2nd array is less than
// or equal to its highest index

while ((lo <= end_low) && (start_high <= high)) {

System.out.println("\nBOTTOM ARRAY");

printSmallArray(array, lo, middle);

System.out.println("\nTOP ARRAY");

printSmallArray(array, start_high, high);

printHorzArray(-1, -1, array, 49);

// If the value in the 1st index of the 1st array is less
// than the value in the 1st index of the 2nd array

System.out.println("Is " + array[low] + " < " + array[start_high]
+ "? " + (array[low] < array[start_high]));

if (array[low] < array[start_high]) {

// Increment to the next index in the 1st array

low++;
} else {

// Store the value in the 1st index of the 2nd array

int Temp = array[start_high];

System.out.println("Temp: " + Temp);

// Decrement backwards through the first array starting
// at the last index in the first array

for (int k = start_high - 1; k >= low; k--) {

System.out.println("array[" + k + "] = " + array[k]
+ " Stored in array index " + (k + 1));

array[k + 1] = array[k];
}

System.out.println(Temp + " is stored in index " + low);

printHorzArray(-1, -1, array, 49);

array[low] = Temp;
low++;
end_low++;
start_high++;
}
}

printHorzArray(-1, -1, array, 49);

}

// Used to print out the smaller arrays

static void printSmallArray(int theArray[], int lo, int high) {

int[] tempArray = Arrays.copyOfRange(theArray, lo, high);

int tempArrayDashes = tempArray.length * 6;

System.out.println("Array Index Start " + lo + " and End " + high);

printHorzArray(-1, -1, tempArray, tempArrayDashes);

}

static void printHorzArray(int i, int j, int theArray[], int numDashes) {

for (int n = 0; n < numDashes; n++)
System.out.print("-");

System.out.println();

for (int n = 0; n < theArray.length; n++) {

System.out.format("| %2s " + " ", n);

}

System.out.println("|");

for (int n = 0; n < numDashes; n++)
System.out.print("-");

System.out.println();

for (int n = 0; n < theArray.length; n++) {

System.out.print(String.format("| %2s " + " ", theArray[n]));

}

System.out.println("|");

for (int n = 0; n < numDashes; n++)
System.out.print("-");

System.out.println();

}
}```

### 17 Responses to “Java Recursion”

1. Maggi says:

Hi Derek,
Can i get your personal email id..
I have tons of questions. but they all are different or not just related to one technology so dont want to ask here and deviate the topics.

It will be of great help if i can get your email so that i can mail you as and when i get a doubt. and i am sure the doubts will be of standard industry problems, and then you can elaborate to others.

Hope i get what i want, as i am getting from you without asking ðŸ™‚

Maggi

2. Ognian says:

Hi Derek,
I am interested in your view of ATD Tree
Regards,
Ognian Borisov

• Derek Banas says:

I’ll be covering that topic very soon. I’ll get the videos out as soon as possible

3. Ravi says:

Hi Derek,

I have seen your videos very recently and they are really good, you have explained the topics in such way that every one could easily follow them. Thank you very much for these wonderful tutorials ðŸ™‚
Just curious to know if you have any plans of making some tutorials on Web Services.

• Derek Banas says:

Thank you very much for the kind message ðŸ™‚ Yes I do plan on covering web services. I probably will need to cover them in the Android tutorial soon. Thank you for the request

• Ravi says:

Hi Derek,

Thanks for that. I will wait for them. Mean while I found so many video tutorials that I am looking for like python will start listening to them. Once again thanks for all your good work

4. Parul says:

Thanks Derek your tutorial is such a great help, I have started implementing these concepts in my Automation code .

5. Preston says:

Hi Derek,
I am experimenting with permutations and combinations using recursion and I was wondering if you could show an example on how you could display all the combinations according to the permutations. I seem to have quite some difficulty doing this.

I’ve done some extensive research, but all to no avail. Most of which simply explains the basic concepts of recursion.

Hope you could help, and that this would help anyone else searching up the same topic.

Preston

6. Swati says:

Hi Derek,

Very nice explanation. But I would like to see Merge Sort in detail just like you did for Quick sort. It took long time for me to understand how exactly it runs.

These 2 sorting algorithms are very important and complicated too. So please if possible prepare a separate video to explain Merge Sort. It would be really helpful for people like me.

Your videos are really amazing and helping me to prepare for interviews. Thank you so much for preparing these.

• Derek Banas says:

Hi Swati,

Thank you for the nice compliment ðŸ™‚ I cover the Merge Sort here.

• Swati says:

Yeah I saw this video, but I meant a separate video. Anyways, no problem.