wood burning stoves 2.0*
The moose likes Beginning Java and the fly likes Recursion in java Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Soft Skills this week in the Jobs Discussion forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Recursion in java" Watch "Recursion in java" New topic
Author

Recursion in java

Ravi Kiran Va
Ranch Hand

Joined: Apr 18, 2009
Posts: 2234


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.


Save India From Corruption - Anna Hazare.
Prabz Bhatia
Greenhorn

Joined: Apr 14, 2009
Posts: 19
http://faq.javaranch.com/java/ShowSomeEffort
http://faq.javaranch.com/java/SearchFirst


Ravi Kiran Va
Ranch Hand

Joined: Apr 18, 2009
Posts: 2234

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

Joined: Mar 13, 2009
Posts: 492

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.


"If the facts don't fit the theory, get new facts" --Albert Einstein
Sagar Rohankar
Ranch Hand

Joined: Feb 19, 2008
Posts: 2902
    
    1

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.


[LEARNING bLOG] | [Freelance Web Designer] | [and "Rohan" is part of my surname]
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11494
    
  16

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.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Sagar Rohankar
Ranch Hand

Joined: Feb 19, 2008
Posts: 2902
    
    1

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

Joined: Aug 05, 2005
Posts: 3742
    
  16
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


Joanne
Sagar Rohankar
Ranch Hand

Joined: Feb 19, 2008
Posts: 2902
    
    1

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

Joined: May 13, 2009
Posts: 679
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

Joined: Sep 29, 2008
Posts: 12617

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
Ranch Hand

Joined: Jan 12, 2009
Posts: 928

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.

My Website: [Salvin.in] Cool your mind:[Salvin.in/painting] My Sally:[Salvin.in/sally]
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 40027
    
  28
salvin francis wrote:The simplest Example is the Fibnacci series
No, factorials are much simpler. Fibonacci numbers are by no means simple.
Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 42906
    
  69
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

Joined: May 13, 2009
Posts: 679
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

Joined: Oct 13, 2005
Posts: 40027
    
  28
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

Joined: May 13, 2009
Posts: 679
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
Ranch Hand

Joined: Jan 12, 2009
Posts: 928

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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Recursion in java