Solved

recursion example

Posted on 2016-11-04
16
66 Views
Last Modified: 2016-11-14
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
Comment
Question by:gudii9
  • 6
  • 5
  • 3
  • +1
16 Comments
 
LVL 7

Author Comment

by:gudii9
Comment Utility
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
 
LVL 26

Expert Comment

by:dpearson
Comment Utility
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
 
LVL 7

Author Comment

by:gudii9
Comment Utility
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
 
LVL 7

Author Comment

by:gudii9
Comment Utility
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
 
LVL 26

Assisted Solution

by:dpearson
dpearson earned 125 total points
Comment Utility
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
 
LVL 7

Author Comment

by:gudii9
Comment Utility
when we use recursion approach and when we use backtracking recursion ?? please advise
0
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
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
Highfive Gives IT Their Time Back

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 
LVL 26

Expert Comment

by:dpearson
Comment Utility
Recursive functions always backtrack.  E.g. Method MyFunction calls itself.  Eventually that function returns - which is the backtracking.
0
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
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
 
LVL 32

Accepted Solution

by:
phoffric earned 250 total points
Comment Utility
BTW, in general, be very careful when using pre or post-increment, as they often can produce undesired side-effects.
0
 
LVL 7

Author Comment

by:gudii9
Comment Utility
i see

when i change
      recurse(count--);

to
      recurse(--count);

i am getting meaningful output
0
 
LVL 7

Author Comment

by:gudii9
Comment Utility
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
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
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
 
LVL 27

Assisted Solution

by:tliotta
tliotta earned 125 total points
Comment Utility
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
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
@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

What Security Threats Are You Missing?

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

Java functions are among the best things for programmers to work with as Java sites can be very easy to read and prepare. Java especially simplifies many processes in the coding industry as it helps integrate many forms of technology and different d…
"Disruption" is the most feared word for C-level executives these days. They agonize over their industry being disturbed by another player - most likely by startups.
This theoretical tutorial explains exceptions, reasons for exceptions, different categories of exception and exception hierarchy.
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…

771 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now