Link to home
Start Free TrialLog in
Avatar of gudii9
gudii9Flag for United States of America

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);
	}

}

Open in new window


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)

Open in new window

Avatar of gudii9
gudii9
Flag of United States of America image

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");
		}
	}

}

Open in new window

output is


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



when is recursive way better and when iterative way better to use?
please advise
Avatar of dpearson
dpearson

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
Avatar of gudii9

ASKER

http://codingbat.com/prob/p145416

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;
		}
}

Open in new window

not clear on above code on what is going on inside? please advise

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]))
Avatar of gudii9

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
Avatar of dpearson
dpearson

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of gudii9

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.
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
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of gudii9

ASKER

i see

when i change
      recurse(count--);

to
      recurse(--count);

i am getting meaningful output
Avatar of gudii9

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");
		}
	}

}

Open in new window


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
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
@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.