• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Recursion in java

 
Ranch Hand
Posts: 2234
Eclipse IDE Firefox Browser Redhat
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Greenhorn
Posts: 19
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
http://faq.javaranch.com/java/ShowSomeEffort
http://faq.javaranch.com/java/SearchFirst


 
Ravi Kiran Va
Ranch Hand
Posts: 2234
Eclipse IDE Firefox Browser Redhat
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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??
 
Ranch Hand
Posts: 492
Firefox Browser VI Editor Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Ranch Hand
Posts: 2908
1
Spring Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 2908
1
Spring Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Rancher
Posts: 3742
16
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 2908
1
Spring Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Ranch Hand
Posts: 686
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Author
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Bartender
Posts: 2911
150
Google Web Toolkit Eclipse IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Rancher
Posts: 43081
77
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 686
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 686
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 2911
150
Google Web Toolkit Eclipse IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
reply
    Bookmark Topic Watch Topic
  • New Topic