Recursion and Tail recursion in Java
Filed in: Recursion | Tail recursion
This is a quick article about recursion and how it can be used to solve various problems. We will start with some simple examples and work our way up.
Let us look at what recursion is. What we do in recursion is to call the same method or function many times in order to solve a problem because the actual algorithm does not change from call to call just the arguments.
A recursive algorithm always has at least two elements to it
Firstly the Algorithm or logic that does not change call to call
Secondly the stop condition, so the Algorithm knows it has reached its conclusion.
Since we heavily use the stack when making recursive calls it is very important that we make sure that the Condition is hit before we run out of stack space.
As an example if we sum up the numbers from 1 to 10 we can do this recursively
if( n > 1){ //CONDITION
return sum(n-1) + n; //Recurse
}
return n;
}
This code simply defines a condition if( n >=1 ) and if it is it calls itself again adding the n so we have a simple algorithm Something + n and a simple condition.
This code works fine and recursion like this is useful but does have some downsides.
Think about what is happening under the covers we create a stack frame and push the n+sum(…) onto it and then create another stack frame and push n+sum(…) onto it and we do this as many as n times. If n was a huge number this would be a lot of work and waste on the stack. If the algorithm was nontrivial it also may cause you to run out of stack space.
A more efficient way to do this would be to not put so much on the stack or to use tail recursion. Tail recursion is a recursion where the only thing that we return when recursing is the method itself. Not n+sum(…) but just sum(…) so how can we get rid of the n in this algorithm if we don’t want it in the return.
What we can do is use an accumulator. This means adding a variable in the method call to account for that n+ variable, look at this code.
if(n < 1){ //Condition
return accumulator;
}
//Update Accumulator
//Update Conditional
return tailSum(accumulator + n, n -1); //TAIL as recurse is last item in Method
}
The reason this is so much better is that almost all JVMs and interpreters will actually convert this into an inline call with a condition which is far more performant than creating stacks for every recursive call. The accumulator allows for tail recursion as everything is wrapped in the method call.
Recursion can be used to solve lot of different problems here are a few recursive examples to review before we move on.
public int fibonacci(int n){
if(n <=1 ) { //Condition
return n;
}
//Recurse n-1 + n-2
return fibonacci(n-1) + fibonacci(n-2);
}
//factorial of n
public long factorial ( int n ) {
if(n==1) return 1;
return n * factorial(n-1);
}
/*
* Greatest Common Denominator
* Good test 1440, 408 we would expect 24
* Good test 102, 68 we would expect 34
*
* Largest divisor that divides evenly to both numbers
*
*
*/
public int euclidAlgoGCD(int a, int b){
if(b==0) return a; //if modulo is 0 we have found largest divisor
else return euclidAlgoGCD(b, a % b);
}
Now we have seen some simple examples of recursion let us look at a real life practical example of this in action. Imagine you had a sorted array of 100 or even a 1000 elements and you wanted to find in that array 1 specific element ? Given the array is sorted can you take advantage of this fact and search quickly for the specific element.
One neat trick with sorted arrays is to use a binary search. A binary search algorithm is straightforward and is as follows.
Find the middle of the list in an array of 100 it would be 50 have we found the element ?
if the element < 50
Then search between start and 50
If the element is > 50
Then search between 50 and end of the list
You can see how this algorithm keeps searching a smaller and smaller subset of the array. The condition to stop is either we have 1 element left and its not what we want or we have found the element so we can stop the search.
Now lets put this into some code
private Optional splitList( int start, int end, int e){
//Calc Midpoint
int mid=Math.abs(end-start)/2 + start;
System.out.println(start+" -> "+ end + " e=" + e + " Middle="+mid);
//Found Element - sortedArray is a field variable of teh class which is an array which is sorted.
if(sortedArray[mid]==e){
return Optional.of(mid);
}
//We have only 1 element and its not the one so Empty or Not Found
if(end-start == 1){
return Optional.empty();
}
//Left or Right
if(e < sortedArray[mid]){
return splitList(start, mid, e);
}else{
//right
return splitList(mid, end, e );
}
}
//Using a binary search algorithm find the element e in the sortedArray[]
public Optional binSearch( int e){
//First iter
int start=0;
int end=sortedArray.length;
//sortedArray is Array at Class Level
return splitList(start, end, e);
}
The splitList method is recursed many times and each time we check our conditions to see if we are done.
If I have a sorted list of 1 to 100 and I look for 62 in that list my search would look something like
0 -> 100 split Middle and search right array from middle
50 -> 100 split Middle and search left array
50 -> 75 split Middle and we have found the element.
62
binSearch(62).ifPresent(c -> System.out.println(c.intValue()));
So we recursed 3 times and then finally found the element we were looking for so it returns the array position where it found the element. This is a practical implementation of binary search and it also tends to show up as Interview questions.
Java Interview Code Examples
Naive Bayes classification AI algorithm
K-Means Clustering AI algorithm
Equity Derivatives tutorial
Fixed Income tutorial
Java
python
Scala
Investment Banking tutorials
HOME
Let us look at what recursion is. What we do in recursion is to call the same method or function many times in order to solve a problem because the actual algorithm does not change from call to call just the arguments.
A recursive algorithm always has at least two elements to it
Firstly the Algorithm or logic that does not change call to call
Secondly the stop condition, so the Algorithm knows it has reached its conclusion.
Since we heavily use the stack when making recursive calls it is very important that we make sure that the Condition is hit before we run out of stack space.
As an example if we sum up the numbers from 1 to 10 we can do this recursively
public int sum(int n){
if( n > 1){ //CONDITION
return sum(n-1) + n; //Recurse
}
return n;
}
This code simply defines a condition if( n >=1 ) and if it is it calls itself again adding the n so we have a simple algorithm Something + n and a simple condition.
This code works fine and recursion like this is useful but does have some downsides.
Think about what is happening under the covers we create a stack frame and push the n+sum(…) onto it and then create another stack frame and push n+sum(…) onto it and we do this as many as n times. If n was a huge number this would be a lot of work and waste on the stack. If the algorithm was nontrivial it also may cause you to run out of stack space.
A more efficient way to do this would be to not put so much on the stack or to use tail recursion. Tail recursion is a recursion where the only thing that we return when recursing is the method itself. Not n+sum(…) but just sum(…) so how can we get rid of the n in this algorithm if we don’t want it in the return.
What we can do is use an accumulator. This means adding a variable in the method call to account for that n+ variable, look at this code.
public int tailSum(int accumulator, int n){
if(n < 1){ //Condition
return accumulator;
}
//Update Accumulator
//Update Conditional
return tailSum(accumulator + n, n -1); //TAIL as recurse is last item in Method
}
The reason this is so much better is that almost all JVMs and interpreters will actually convert this into an inline call with a condition which is far more performant than creating stacks for every recursive call. The accumulator allows for tail recursion as everything is wrapped in the method call.
Recursion can be used to solve lot of different problems here are a few recursive examples to review before we move on.
//Calc n'th fibonacci
public int fibonacci(int n){
if(n <=1 ) { //Condition
return n;
}
//Recurse n-1 + n-2
return fibonacci(n-1) + fibonacci(n-2);
}
//factorial of n
public long factorial ( int n ) {
if(n==1) return 1;
return n * factorial(n-1);
}
/*
* Greatest Common Denominator
* Good test 1440, 408 we would expect 24
* Good test 102, 68 we would expect 34
*
* Largest divisor that divides evenly to both numbers
*
*
*/
public int euclidAlgoGCD(int a, int b){
if(b==0) return a; //if modulo is 0 we have found largest divisor
else return euclidAlgoGCD(b, a % b);
}
Now we have seen some simple examples of recursion let us look at a real life practical example of this in action. Imagine you had a sorted array of 100 or even a 1000 elements and you wanted to find in that array 1 specific element ? Given the array is sorted can you take advantage of this fact and search quickly for the specific element.
One neat trick with sorted arrays is to use a binary search. A binary search algorithm is straightforward and is as follows.
Find the middle of the list in an array of 100 it would be 50 have we found the element ?
if the element < 50
Then search between start and 50
If the element is > 50
Then search between 50 and end of the list
You can see how this algorithm keeps searching a smaller and smaller subset of the array. The condition to stop is either we have 1 element left and its not what we want or we have found the element so we can stop the search.
Now lets put this into some code
private Optional
//Calc Midpoint
int mid=Math.abs(end-start)/2 + start;
System.out.println(start+" -> "+ end + " e=" + e + " Middle="+mid);
//Found Element - sortedArray is a field variable of teh class which is an array which is sorted.
if(sortedArray[mid]==e){
return Optional.of(mid);
}
//We have only 1 element and its not the one so Empty or Not Found
if(end-start == 1){
return Optional.empty();
}
//Left or Right
if(e < sortedArray[mid]){
return splitList(start, mid, e);
}else{
//right
return splitList(mid, end, e );
}
}
//Using a binary search algorithm find the element e in the sortedArray[]
public Optional
//First iter
int start=0;
int end=sortedArray.length;
//sortedArray is Array at Class Level
return splitList(start, end, e);
}
The splitList method is recursed many times and each time we check our conditions to see if we are done.
If I have a sorted list of 1 to 100 and I look for 62 in that list my search would look something like
0 -> 100 split Middle and search right array from middle
50 -> 100 split Middle and search left array
50 -> 75 split Middle and we have found the element.
62
binSearch(62).ifPresent(c -> System.out.println(c.intValue()));
So we recursed 3 times and then finally found the element we were looking for so it returns the array position where it found the element. This is a practical implementation of binary search and it also tends to show up as Interview questions.
People who enjoyed this article also enjoyed the following:
Java Interview Code Examples
Naive Bayes classification AI algorithm
K-Means Clustering AI algorithm
Equity Derivatives tutorial
Fixed Income tutorial
And the following Trails:
C++Java
python
Scala
Investment Banking tutorials
HOME