wood burning stoves 2.0*
The moose likes Programming Diversions and the fly likes Why recursion? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Java 8 in Action this week in the Java 8 forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Why recursion?" Watch "Why recursion?" New topic
Author

Why recursion?

minal silimkar
Ranch Hand

Joined: Nov 25, 2007
Posts: 133
As I read about this community is for "Programming puzzles, challenges, interview questions, and similar fun".

One question is generally asked in interview is "What is the use of recursion functions, if we can write the other logic?"

As far as I know, for critical programming using recursion we can write more simplified logic than that of general functions.

Is there any reason to write recursive code?


Minal Silimkar
Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 39577
    
  27
There's nothing wrong with recursion per se. Recursive algorithms are easier to program (and the code is easier to read) than if I were to translate it into an iterative algorithm. There are benefits in having code that's easy to read and write.

There certainly is an overhead in allocating stack frames for each recursive call, but whether that's worthwhile working around is a different question. Writing something like QuickSort iteratively would involve setting up additional data structures (a stack) as well, so that too has a certain amount of overhead.

The overhead becomes sizeable when the problem is tree-recursive (i.e., involves more than one recursive call per step) and goes to great depths. Fibonacci numbers are a good example of when using recursion is the wrong thing to do - the iterative approach has linear complexity, while the recursive approach has exponential complexity, in addition to the stack frame allocation overhead.

But generally, recursion is nothing to be feared.


Ping & DNS - updated with new look and Ping home screen widget
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10925
    
  12

Answer their question with another question: "Why would you use other logic when you can write recursive a function?"


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

Joined: Jan 01, 2007
Posts: 184
Initially posted by Fred
Why would you use other logic when you can write recursive a function?


That is the best reply to this question that I have come across till now. Although if you are a fresher I wont advice you say that to your
interviewer or he might react like this


The significant problems we face cannot be solved by the same level of thinking which created them – Einstein
SCJP 1.5, SCWCD, SCBCD in the making
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10925
    
  12

in all seriousness, the answer to this question is the same as the answer to ANY question about software development - you need more info. What is important on this system? What constraints do you have?

If memory is an issue (i.e. a phone or hand-held device application), recursion might not be very wise, especially (as Ulf says) you're going to get pretty deep.

However, the logic for recursion can be simpler, so maintenance and development might be easier. Maybe there are well known recursive algorithms that are well documented already, while you'd have to 'roll your own' non-recursive solution.
mani vannan
Ranch Hand

Joined: Apr 17, 2006
Posts: 47
"Why would you use other logic when you can write recursive a function?"


1. Recursion will be bad for code readability - not every programmer can understand it.
2. Recursion is a repeated method call stack - the more you use recursion the more memory stack created
3. Recursion can not be inlined by compilers - if i am not wrong.


Mani (SCEA 1.4)<br /><a href="http://excusemeworld.com/technical/is-scjp-useful-worth-helps-job/" target="_blank" rel="nofollow"> Is SCJP Useful? Worth? Helps job?</a>
Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 39577
    
  27
1. Recursion will be bad for code readability - not every programmer can understand it.

That depends on whether a straightforward non-recursive algorithm exists. Programming a recursive algorithm using recursion will certainly result in easier to read code than the same algorithm programmed in a non-recursive way.

As an example, compare recursive and non-recursive QuickSort implementations.
Andrew Monkhouse
author and jackaroo
Marshal Commander

Joined: Mar 28, 2003
Posts: 11285
    
  59

Originally posted by mani vannan:
3. Recursion can not be inlined by compilers - if i am not wrong.


Tail recursion can be easily inlined, however it is my understanding that the Java creators specifically chose not to implement this, as it makes resultant code hard to debug (if not impossible).

- Andrew


The Sun Certified Java Developer Exam with J2SE 5: paper version from Amazon, PDF from Apress, Online reference: Books 24x7 Personal blog
tapeshwar sharma
Ranch Hand

Joined: Mar 10, 2006
Posts: 245

Is there any reason to write recursive code?

Several.I am listing 2:
1) When we learn coding for mathematical functions like n! (factorial).The coding is much easier and in fact more readable.
2) XML processing : Well, these are in essence mathematical function only, but not that apparent from the surface.So, when you have to process repeating nodes in a XML document, recursion is a boon.Or so I find.
Maris Orbidans
Ranch Hand

Joined: Mar 08, 2004
Posts: 149
mani vannan wrote:
1. Recursion will be bad for code readability - not every programmer can understand it.


If some [ person ] can't understand recursion then he shouldn't work as programmer.

mani vannan wrote:
2. Recursion is a repeated method call stack - the more you use recursion the more memory stack created


Tail recursion optimization can replace recursion with a loop.

mani vannan wrote:
3. Recursion can not be inlined by compilers - if i am not wrong.


Depends on compiler I think. Recursion is a paramount of functional programming.

[ UD: Please adhere to the "Be Nice" rule. ]
Ashish Maharaja Singh
Greenhorn

Joined: Jun 06, 2011
Posts: 8
Ulf Dittmer wrote:
The overhead becomes sizeable when the problem is tree-recursive (i.e., involves more than one recursive call per step) and goes to great depths.


I think that is what i am trying to do here. Please tell me if recursion is good for this or not. Please suggest ways to make a simple MergeSort program.

 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Why recursion?
 
Similar Threads
Programming avenues other than web programming
Recursive Problems
Can we execute two sql statements with one Connection object?
pause and resume download
Recursive Functions