Recursion
simply means calling the same function inside its own body repeatedly to
complete some task. This is one of the
standard approaches to achieve some task. While programming using recursion,
there is one basic thing one must fix is the base condition to stop the
recursion, otherwise we’ll run into an infinite recursion.
package blog.techcypher.recursion;
/**
* Returns the sum of 'n' natural numbers.
*
* @author abhishek
*
*/
public class Sum {
/**
* @param n
* @return
*/
public static int sum(int n) {
int sum = 0;
if (n==1) {
sum = 1;
} else {
sum = n + sum(n-1);
}
return sum;
}
/**
* main method to invoke recursion
* @param args
*/
public static void main(String[] args) {
int n = 1000;
System.out.print("Sum of [" + n + "] naural numbers: ");
System.out.println(sum(n));
}
}
Result:
Sum of [1000] naural numbers: 500500
In this example, the base condition is n == 1 i.e. call to sum will be stop when n=1. So, we start summing up numbers starting from n till 1 using recursion.
It works perfectly… J
But, what will be the depth of recursion for various values
of n in the above “sum” function.
Obviously, it will depend on the input. For large values of n like 10000 or more, the program will throw StackOverflowError and JVM may crash.
Obviously, it will depend on the input. For large values of n like 10000 or more, the program will throw StackOverflowError and JVM may crash.
For n = 10000,
Sum of [10000] naural numbers: Exception in thread "main" java.lang.StackOverflowError
at blog.techcypher.recursion.Sum.sum(Sum.java:15)
An obvious question comes into mind is - “Why we are getting StackOverflowError
for deep recursion…?”
The reason is “The recursive function may run out of the default thread stack size, and such scenario it throws an Error which is StackOverflowError ”.
In Java, the default thread stack size is 512k in the 32-bit VM, and 1024k in the 64-bit VM on Windows. You may refer link to check the default thread stack size for other OS.
Solutions:
1. Increase the default thread stack size:
Java
provides run-time argument to tune the default thread stack size using –Xss
option.
java –Xss2048k
This statement means that the stack size will be 2048KB.
But notice that it may be curable, but a better solution would be to
work out how to avoid
recursing so much.2. Change the implementation to an iterative solution:
Most of the recursive solutions can easily be converted to iterative solutions, which will
make the code scale to larger inputs much more cleanly. Otherwise we'll really be guessing
at how much stack to provide, which may not even be obvious from the input.
make the code scale to larger inputs much more cleanly. Otherwise we'll really be guessing
at how much stack to provide, which may not even be obvious from the input.
This should the most preferred solution.
3. Using Tail Recursion:
Using tail-call optimization we are able to
avoid allocating a new stack frame for a
function because the calling function will simply return the value that it gets from
the called function. The most common use is tail-recursion, where a recursive function
written to take advantage of tail-call optimization can use constant stack space.
function because the calling function will simply return the value that it gets from
the called function. The most common use is tail-recursion, where a recursive function
written to take advantage of tail-call optimization can use constant stack space.
It is
supported by many functional languages but it is not supported by Java.
Coming to the best practices, we should prefer iterative solution over recursion wherever
possible. This will be relatively faster and scalable.
Hope this article helped. Happy learning… J
- 01:57
- 0 Comments
