Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 271
  • Last Modified:

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

0
gudii9
Asked:
gudii9
  • 6
  • 5
  • 3
  • +1
3 Solutions
 
gudii9Author Commented:
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
0
 
dpearsonCommented:
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
0
 
gudii9Author Commented:
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]))
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
gudii9Author Commented:
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??
0
 
dpearsonCommented:
If you want to work through the explanation of groupSum() - I think that's a different question.

how to visualize tree and branch and where first branch ends and second branch begins??

You normally think of a Tree as something like this:

public class Tree {
   Integer m_value ;
   Tree m_left ;
   Tree m_right ;

   public Tree(int value, Tree left, Tree right) { m_value = value ; m_left = left ; m_right = right ; }
} ;

So now you can have:

Tree a = new Tree(6, null, null) ;
Tree b = new Tree(7, null, null) ;
Tree root = new Tree(10, a, b) ;

So this is a tree like this:

     10
    /    \
  6      7

Make sense?

Doug
0
 
gudii9Author Commented:
when we use recursion approach and when we use backtracking recursion ?? please advise
0
 
phoffricCommented:
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.
0
 
dpearsonCommented:
Recursive functions always backtrack.  E.g. Method MyFunction calls itself.  Eventually that function returns - which is the backtracking.
0
 
phoffricCommented:
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.
0
 
phoffricCommented:
BTW, in general, be very careful when using pre or post-increment, as they often can produce undesired side-effects.
0
 
gudii9Author Commented:
i see

when i change
      recurse(count--);

to
      recurse(--count);

i am getting meaningful output
0
 
gudii9Author Commented:
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?
0
 
phoffricCommented:
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.
0
 
tliottaCommented:
Think about a database table that looks something like this:
Item_ID		Description		Is_Part_Of
001		Mercedes Sedan		null
002		Mercedes Sedan Body	001
003		Mercedes Sedan Engine	001
004		Mercedes Door		002
005		Mercedes Hood		002
006		Mercedes Piston		003
007		Mercedes Engine Block	003
008		Mercedes Cam Shaft	003
009		Mercedes Valve Stem	003
010		Ford Sedan		null
011		Ford Sedan Body		010
012		Ford Sedan Engine	010

Open in new window

And now think about creating a report that looks like this:
Item_ID		Description		Is_Part_Of
001		Mercedes Sedan		null
 002		Mercedes Sedan Body	001
  004		Mercedes Door		002
  005		Mercedes Hood		002
 003		Mercedes Sedan Engine	001
  006		Mercedes Piston		003
  007		Mercedes Engine Block	003
  008		Mercedes Cam Shaft	003
  009		Mercedes Valve Stem	003
010		Ford Sedan		null
 011		Ford Sedan Body		010
 012		Ford Sedan Engine	010

Open in new window

You can see that Item_ID( 004 ) Is_Part_Of( 002 ) and that Item_ID( 002 ) Is_Part_Of( 001 ). You can also see that Item_ID( 001 ) isn't a part of anything because it has a "null" value.

Using 'recursion', you can fairly efficiently look through the table to figure out what all of the completed products are and how each part fits into a completed product. It's a reasonably well structured table that handles both completed products and component parts, and it tells how they relate to each other. If Part_ID is an integer, the number of possible parts and products gets into billions.

Products can have many sub-assemblies. With a little more complexity, sub-assemblies could be associated with multiple products. Further, you can go from a completed product down to each part, or you can look at a single part and work all the way up to find what product it goes into.

Once you have a procedure that can find a part of a product, you can then call that same procedure to find sub-parts of that part. It just depends on what Item_ID you pass to the procedure. The procedure might simply call itself again and again until it reaches the last link in any chain of Item_IDs.

One example chain is 001->002->004. And since there are no rows that have Is_Part_Of( 004 ), you know that Part_ID( 004 ) is the last link. A second example chain would be 001->003->009.

It's technically possible to follow such chains iteratively or recursively. If you do it iteratively, you need to create structures that keep track of all parts along each chain until you reach the end. When there might be hundreds of links in a single chain, it can be difficult to keep track of it all. With recursion, you often only need to keep track of the single Part_ID and any one sub-part that your procedure finds it any level. The programming language itself can do much of the work of keeping track for you.

Although I used a physical product table for this example, other examples can be similar. You might want to display a site map for some web site that shows the structure of how pages link to each other. Or you might need to see how all modules in an application call each other. Or you might want to display a map of a directory structure on a server. All of those and many others will usually be done using recursive procedures. Any of those can have very deep structures with hundreds or thousands of branches.

Recursion can simplify, but it might also be less efficient. There is overhead needed in managing the memory that gets used up as a procedure is called over and over. An issue for a developer is deciding if that overhead is small enough to make up for the difference in complexity of code. Often that question comes down to maintainability. A future developer looking at your code might simply be unable to make sense of the extra coding an iterative process can require.

It probably won't take long for any developer to learn that recursion is very often the best choice between the two and to recognize when it's appropriate.
0
 
phoffricCommented:
@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.
0

Featured Post

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

  • 6
  • 5
  • 3
  • +1
Tackle projects and never again get stuck behind a technical roadblock.
Join Now