gudii9
asked on
recursion example
public class TestRecurse {
private static void recurse(int count) {
// TODO Auto-generated method stub
System.out.println("recs");
if(count<=0){
System.out.println("finsiheds");
}else {
//count--;
recurse(count--);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int count=1;
recurse(count);
}
}
i am running above example and got stackoutofbound exception. please advise why i got below error and what it means by stack and why it became out of bound?
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
...
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
...
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
...
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
...
recs
recs
recs
recs
recs
recs
recs
recs
...
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
...
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
recs
Exception in thread "main" java.lang.StackOverflowError
at java.io.FileOutputStream.write(Unknown Source)
at java.io.BufferedOutputStream.flushBuffer(Unknown Source)
at java.io.BufferedOutputStream.flush(Unknown Source)
at java.io.PrintStream.write(Unknown Source)
at sun.nio.cs.StreamEncoder.writeBytes(Unknown Source)
at sun.nio.cs.StreamEncoder.implFlushBuffer(Unknown Source)
at sun.nio.cs.StreamEncoder.flushBuffer(Unknown Source)
at java.io.OutputStreamWriter.flushBuffer(Unknown Source)
at java.io.PrintStream.write(Unknown Source)
at java.io.PrintStream.print(Unknown Source)
at java.io.PrintStream.println(Unknown Source)
at TestRecurse.recurse(TestRecurse.java:8)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
...
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
...
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
...
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
...
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
at TestRecurse.recurse(TestRecurse.java:13)
Iterative is usually the best approach to use to solve a problem, so if you're not sure start with that approach.
Usually the time to use a recursive approach is when the data structure you are exploring is itself recursive - meaning each part is a small copy of the whole. E.g. trees. Each node of a tree has some branches to other nodes and each of those nodes looks like a tree.
So because the data structure is recursive it can be simpler to explore something like that using recursion.
But it's definitely the exception.
Doug
Usually the time to use a recursive approach is when the data structure you are exploring is itself recursive - meaning each part is a small copy of the whole. E.g. trees. Each node of a tree has some branches to other nodes and each of those nodes looks like a tree.
So because the data structure is recursive it can be simpler to explore something like that using recursion.
But it's definitely the exception.
Doug
ASKER
http://codingbat.com/prob/p145416
for above recursive
how calling recursive in if loop is best approach as below
we have 3 if loops
1st if loop as below is base case right
if (start >= nums.length) { // first deal with the corner case
return (target == 0);
}
second if calls again top recursive containing method
if (groupSum(start + 1, nums, target - nums[start]))
third second if calls again top recursive containing method with different set of arguments??
if (groupSum(start + 1, nums, target - nums[start]))
for above recursive
how calling recursive in if loop is best approach as below
public class Sum2 {
public static int targetSum = 15;
public static int[] nums = new int[]{6, 7, 8, 9};
public static void main(String args[]) {
System.out.println(" ======>Found group sum to " + targetSum + "? " + groupSum(0, nums, targetSum));
}
//public static boolean groupSum(int start, int[] nums, int target) {}
public static boolean groupSum(int start, int[] nums, int target) {
if (start >= nums.length) { // first deal with the corner case
return (target == 0);
}
if (groupSum(start + 1, nums, target - nums[start])) {
return true;
}
if (groupSum(start + 1, nums, target)) {
return true;
}
return false;
}
}
not clear on above code on what is going on inside? please advisewe have 3 if loops
1st if loop as below is base case right
if (start >= nums.length) { // first deal with the corner case
return (target == 0);
}
second if calls again top recursive containing method
if (groupSum(start + 1, nums, target - nums[start]))
third second if calls again top recursive containing method with different set of arguments??
if (groupSum(start + 1, nums, target - nums[start]))
ASKER
Usually the time to use a recursive approach is when the data structure you are exploring is itself recursive - meaning each part is a small copy of the whole. E.g. trees. Each node of a tree has some branches to other nodes and each of those nodes looks like a tree.
So because the data structure is recursive it can be simpler to explore something like that using recursion.
how to visualize tree and branch and where first branch ends and second branch begins??
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
when we use recursion approach and when we use backtracking recursion ?? please advise
In you OP you ask about why you are getting the stackoutofbound exception.
Your output had a lot more lines than you expected?
And each line was due to a call to the recursive function.
So, you know that you are calling that function a lot of times.
Each time you call a function you take up space on the stack for the functions stack frame.
After a lot of calls, your stack gets filled up to the allotted amount and when you try to go beyond that amount, you are now out of bounds. That is why you get the stackoutofbound exception.
Your output had a lot more lines than you expected?
And each line was due to a call to the recursive function.
So, you know that you are calling that function a lot of times.
Each time you call a function you take up space on the stack for the functions stack frame.
After a lot of calls, your stack gets filled up to the allotted amount and when you try to go beyond that amount, you are now out of bounds. That is why you get the stackoutofbound exception.
Recursive functions always backtrack. E.g. Method MyFunction calls itself. Eventually that function returns - which is the backtracking.
In your OP, you do a print in the if condition, but not in the else part. Either add a print of the count in the else condition, or go into your debugger, and break on the else condition 2 or 3 times and examine the count value. Following these steps should be enough to surprise you.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
i see
when i change
recurse(count--);
to
recurse(--count);
i am getting meaningful output
when i change
recurse(count--);
to
recurse(--count);
i am getting meaningful output
ASKER
public class TestRecurse {
private static void recurse(int count) {
// TODO Auto-generated method stub
System.out.println(count+"recursive way");
if(count<=0){//base case
System.out.println("finsiheds");
}else {
//count--;
recurse(--count);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
//int count=5;
recurse(5);
for(int i=5;i>=0;i--){//iterative way
System.out.println(i+"iterative way");
}
}
}
above gave below output
5recursive way
4recursive way
3recursive way
2recursive way
1recursive way
0recursive way
finsiheds
5iterative way
4iterative way
3iterative way
2iterative way
1iterative way
0iterative way
Recursive functions always backtrack. E.g. Method MyFunction calls itself. Eventually that function returns - which is the backtracking.
in above program line 22 recurse(5); within main method calles above recursive method in line 1 i.e private static void recurse(int count) {
then inside the else line 13 recurse(--count); it calls again same function i.e line 6 right. i wonder where the function returns eventually? i do not see return statement either?
count keep on reducing which falls into base case of if condition and finally says "finished" right?
Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution.https://en.wikipedia.org/wiki/Backtracking
In backtracking algorithms you make a guess, and when it does not solve the problem, sometimes you keep track of the results of that guess as a partial solution (i.e., memoization) in order to optimize the performance.
https://en.wikipedia.org/wiki/Memoization
I never thought of recursion as always being backtracking; but backtracking problems are usually initially designed with recursion to make to optimal design solution simpler to understand. Often the recursive solution is converted to an iterative approach to improve performance.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
@friends,
In general, to avoid wasting our time, we should try to avoid discussing unrelated topics not asked in the OP which was simply about a program crashing. There were three separate topics in this question, and we all spent a bit of time handling them. Now, since one of the topics is a duplicate of another question, and because we have addressed this additional question, the mod is deleting the entire question, since duplicate questions are not allowed by the same author. (There probably are duplicate questions by different authors over the span of a decade; but that is a different category.)
I actually provided a solution to the OP that the author acknowledged as working, but he did not close the question at that point once the solution was found. As a result, the posts I did will be deleted along with other posts, and others looking for a similar solution in the future will not find this question in the PAQ. Seems like everyone in EE loses when we do not adhere to the EE policies.
In general, to avoid wasting our time, we should try to avoid discussing unrelated topics not asked in the OP which was simply about a program crashing. There were three separate topics in this question, and we all spent a bit of time handling them. Now, since one of the topics is a duplicate of another question, and because we have addressed this additional question, the mod is deleting the entire question, since duplicate questions are not allowed by the same author. (There probably are duplicate questions by different authors over the span of a decade; but that is a different category.)
I actually provided a solution to the OP that the author acknowledged as working, but he did not close the question at that point once the solution was found. As a result, the posts I did will be deleted along with other posts, and others looking for a similar solution in the future will not find this question in the PAQ. Seems like everyone in EE loses when we do not adhere to the EE policies.
ASKER
Open in new window
output is5recursive way
4recursive way
3recursive way
2recursive way
1recursive way
0recursive way
finsiheds
5iterative way
4iterative way
3iterative way
2iterative way
1iterative way
0iterative way
when is recursive way better and when iterative way better to use?
please advise