Recursion in Java with an example of solving a problem with LeetCode
Recursive methods in Java are methods that call themselves and require care in handling them.
To avoid seeing “StackOverflowError” on the screen, you need to remember two things: the basis and the recursion step.
The basis is the condition for exiting the recursion, and the step is a call by the method to itself with modified parameters.
The most common example you'll come across on the internet when trying to find information about recursion is finding the factorial of a number. Let's quickly go over it before looking at a more interesting problem with leetCode.
public int calculateFactorial(int x) {
int result = 1;
if (x == 1) {
return result;
}
return x * calculateFactorial(x - 1);
}The recursion basis in this case is determined by the “if” condition, and the step is specified here – calculateFactorial(x – 1);
What will happen in the method if we pass the value 3 as the parameter x? First, we will fail the condition calculateFactorial(3 – 1), then again into it, but with the meaning calculateFactorial(2 – 1), then we run into the basis:
if (x == 1) {
return result;
}And let's go up: result = 2 * 1 = 2. And again up (since we fell through twice): result = 3 * 2 = 6. 6 is the final result that the method will return.
Now let's look at a more interesting problem with leetCode. If you don't know about classes, variables, getters, setters and constructors, you should study them first.
The problem statement is here: https://leetcode.com/problems/merge-two-sorted-lists/description/
Briefly: we have two ordered linked lists that are represented by a set of numbers. For example:
List 1: [1,4,8]
List 2: [2,3,9,10]
The task is to combine these two lists into one.
Expected Result: [1,2,3,4,8,9,10]
The lists themselves are represented by the ListNode class with two variables, setters, getters, and constructors (leetCode doesn't have setters and getters, but in the real world it's better to remember about encapsulation):
public class ListNode {
private int val;
private ListNode next;
public int getVal() {
return val;
}
public void setVal(int val) {
this.val = val;
}
public ListNode getNext() {
return next;
}
public void setNext(ListNode next) {
this.next = next;
}
public ListNode() {
}
public ListNode(int val) {
this.val = val;
}
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}The method that will merge our two linked lists into one takes the following parameters as input:
public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {}So, first let's think about the basis – the condition for exiting the recursion. We will finish sorting when there are no elements left in any of the lists, i.e.
if (list1 == null) {
return list2;
} else if (list2 == null) {
return list1;
}Great, we've defined the basis. Now we need to think about the recursion step – here the recursion step is the transition to the next element, which is represented by the private ListNode next variable in the ListNode class.
If neither list is empty, then we start by comparing the first elements of each list, in our case 1 and 2.
1 < 2, so we need to add the number "1" to our combined list and move to the next element from list1 using recursion. In Java, this would look like this:
if (list1.getVal() < list2.getVal()) {
list1.getNext() = mergeTwoLists(list1.getNext(), list2);
return list1;
}Having fallen into recursion on the second line, we now receive the following lists as input:
List 1: [4,8]
List 2: [2,3,9,10]
And we go through our cycle again, comparing the first elements of each list, only now 2 < 4, that is, list1.val < list2.val. And therefore we must move on to the next element from "List 2", we will write in the code:
else {
list2.getNext() = mergeTwoLists(list1, list2.getNext());
return list2;
}So, our method should look like this:
public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null) {
return list2;
} else if (list2 == null) {
return list1;
}
if (list1.getVal() < list2.getVal()) {
list1.setNext(mergeTwoLists(list1.getNext(), list2));
return list1;
} else {
list2.setNext(mergeTwoLists(list1, list2.getNext()));
return list2;
}
}Let's quickly go through each step of the recursion, looking at the input data:
Step 3:
Step 4:
List 1: [4,8]
List 2: [9,10]
Step 5:
List 1: [8]
List 2: [9,10]
Step 6:
List 1: []
List 2: [9,10]
At step 6 we reach one of the bases (exit conditions) of the recursion and start moving upward.
Returning to step 5, we get list1.next = [9,10]and list1 itself = [8,9,10].
On the 4th step: list1.val = 4, list1.next = [8,9,10]return to step 3 – [4,8,9,10];
We entered step 3 via list2.next, so list2.next = [4,8,9,10]and list2.val = 3, we return to the 2nd step: [3,4,8,9,10].
In step 2, list2.next = [3,4,8,9,10]list2.val = 2, list2 = [2,3,4,8,9,10].
At the 1st step, that is, at the very top and the final exit from the recursion, we get list1.next = [2,3,4,8,9,10]list1.val = 1, and list1 = [1,2,3,4,8,9,10] – this is the result of the method's work.
I think for a full understanding it is worth debugging the code several times through the idea. By the way, there are two types of recursion: tail and head. If the last thing a method does is call itself, then it is tail recursion, otherwise it is head recursion. So, in the case of finding the factorial we used tail recursion, and in the case of solving the ListNode problem – head recursion.
This is what recursion is 🙂
