Win a copy of The Java Performance Companion this week in the Performance forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Recursion in java

 
Ravi Kiran Va
Ranch Hand
Posts: 2234
Eclipse IDE Firefox Browser Redhat
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Hi ,
I have read that

Stack overflow Error occurs , The docs says usually indicates when you're using recursion . Please tell me what does actually Recursion mean ?

Thanks in advance.
 
Prabz Bhatia
Greenhorn
Posts: 19
 
Ravi Kiran Va
Ranch Hand
Posts: 2234
Eclipse IDE Firefox Browser Redhat
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
recursion is when a function calls itself.

Bhatia, can you please tell me how this is related to Stack overflow error??
 
Hunter McMillen
Ranch Hand
Posts: 492
Firefox Browser Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The only way for recursion to cause a stack overflow error that i know of is if it has infinite calls. meaning there is no base case for your recursive method calls.


Hunter.
 
Sagar Rohankar
Ranch Hand
Posts: 2907
1
Java Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ravi Pavan wrote:recursion is when a function calls itself.
Bhatia, can you please tell me how this is related to Stack overflow error??

A function call has a stack assigned to it, which is used to store local variable and references. This stack also gets an address of function which gets call within it. When you call the same function recursively, the stack gets exhausted some where down (or up) in the stacks and JVM complains about Stack Over Flow error indicating it can't add more function call into a same stack.
 
fred rosenberger
lowercase baba
Bartender
Posts: 12147
31
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
the JVM only get so much memory from the operating system. each time you call a method, an additional chunk of memory needs to be used from that allocated amount to save the info on the new method.

so, there are two ways to get a stack overflow. If you're function isn't written correctly, you don't actually reduce the problem to a simpler case. For example:



note that since x never changes, this function will keep calling itself forever, each call using a little more memory from the heap. Eventually, you run out of memory, causing the stack overflow.

The method should be written as something like




Note that each time through the method, x will get reduced a little bit. Eventually, x will reduce to 1, so the method will stop calling itself.

The other time you can get a stack overflow is simply when you run out of memory... you're method may be correct, but if each call takes 5k (you create a bunch of objects in each iteration), and you have to do 10 million iterations, you might run out of what you were allocated.

There are ways to tweak how much memory the JVM gets, but it is possible you may just NEVER have enough.
 
Sagar Rohankar
Ranch Hand
Posts: 2907
1
Java Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
fred rosenberger wrote:The other time you can get a stack overflow is simply when you run out of memory... you're method may be correct, but if each call takes 5k (you create a bunch of objects in each iteration), and you have to do 10 million iterations, you might run out of what you were allocated.

i.e if we call an different function many time within a same function (stack), we get stack overflow.



I mentioned different function because many felts, : recursion = calling same function recursively
 
Joanne Neal
Rancher
Posts: 3742
16
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sagar Rohankar wrote:
fred rosenberger wrote:The other time you can get a stack overflow is simply when you run out of memory... you're method may be correct, but if each call takes 5k (you create a bunch of objects in each iteration), and you have to do 10 million iterations, you might run out of what you were allocated.

i.e if we call an different function many time within a same function (stack), we get stack overflow.



I mentioned different function because many felts, : recursion = calling same function recursively



The code in this example will not produce a stack overflow error (assuming there's no recursion going on in myMethod). Every time thru the loop, the myMethod method will be called causing stuff to be pushed on to the stack, but as soon as the method returns all that stuff will be popped off the stack. This will happen 10000000 times
 
Sagar Rohankar
Ranch Hand
Posts: 2907
1
Java Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Joanne Neal wrote:....but as soon as the method returns all that stuff will be popped off the stack

ohh, Thanks Joanne, how could I forget such a simple thing.
 
Fred Hamilton
Ranch Hand
Posts: 684
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi this is maybe a little off topic, but I am learning about recursion, and doing all my exercises using java. The following question has been posed...

3. Write a function using Recursion to enter and display a string in reverse. Don't use arrays/strings.

What do you suppose he means by that. I do not understand "Don't use arrays/strings." It's all about strings, no?

Thanks

here is my reference http://erwnerve.tripod.com/prog/recursion/recintro.htm
 
David Newton
Author
Rancher
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In general you'll want to start new threads for new topics.

I'd assume the point of the exercise is to not create new strings or arrays but to figure out how to use recursion to print a string in reverse.
 
salvin francis
Bartender
Posts: 1280
10
Eclipse IDE Google Web Toolkit Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
on a funny side:

Meanings:
Recursion is: [see Recursion]

Recursion is an art of writing code that calls itself again and again till some condition is met
You obviously need to have a "terminating" condition for the call.

Recursion is sometimes preferred over looping since many a times its simpler to look at problems in a recursive manner
infact many AI programs are written using recursion.

The simplest Example is the Fibnacci series, try to first make it using loops and then see how its done recursively, you will
understand the difference.
the examples given by other posts are not bad too.

Just like a loop can be infinite, a recursive call can be too and hence throw a Stack overflow error.
 
Campbell Ritchie
Sheriff
Pie
Posts: 49447
62
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
salvin francis wrote:The simplest Example is the Fibnacci series
No, factorials are much simpler. Fibonacci numbers are by no means simple.
 
Ulf Dittmer
Rancher
Posts: 42968
73
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Fibonacci numbers are a good example of how recursion can get you into trouble, though, since it's tree recursion. It slows down dramatically faster than the linear recursion Factorials have (which will run into the numerical limits of "int" or "long" way before the difference between an iterative algorithm and a recursive algorithm can make itself felt).

We've actually had a fair number of discussions on the various aspects of using recursion before.
 
Fred Hamilton
Ranch Hand
Posts: 684
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
duly noted on starting new threads. Thanks to all for the pointers, some useful information here. Someone told me something the other day about recursion, with tongue only partially in cheek. "You need to have faith that it works. If you try to figure out exactly how or why it works, you will go crazy."
 
Campbell Ritchie
Sheriff
Pie
Posts: 49447
62
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It always works if you have designed it properly. It is quite scary when you first try a nice tree recursion, knowing full well it will never work, and it does work.
 
Fred Hamilton
Ranch Hand
Posts: 684
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
heh heh I can imagine.

After a few examples, I have formulated Fred's 1st rule of recursive programming. It seems to work quite nicely, at least for simple examples like the one I mentioned.

#1 If what you are trying to do seems impossible, then try writing a program to do it backwards, then switch the order of the function call and the code block that does the work.
 
salvin francis
Bartender
Posts: 1280
10
Eclipse IDE Google Web Toolkit Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:
salvin francis wrote:The simplest Example is the Fibnacci series
No, factorials are much simpler. Fibonacci numbers are by no means simple.


hmm

Factorials are indeed much simpler.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic