Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

In some cases, I fail to see that a problem could be solved by the divide and conquer method. To give a specific example, when studying the find max sub-array problem, my first approach is to brute force it by using a double loop to find the max subarray. When I saw the solution using the divide and conquer approach which is recursion-based, I understood it but ok. From my side, though, when I first read the problem statement, I did not think that recursion is applicable.

When studying a problem, is there any technique or trick to see that a recursion based (i.e. divide and conquer) approach can be used or not?

share|improve this question
    
I've read a great book by Jeff Edmonds on "How to think about algorithms" which shows where the distinction betweent iterative an d recursive approches on problem solving have their bennefits. amazon.com/Think-About-Algorithms-Jeff-Edmonds/dp/0521614104/… –  Carlo Kuip Oct 28 '11 at 10:27
1  
Anything with a loop can be done with recursion. The question is really if the recursive method is more straightforward. –  Karl Bielefeldt Oct 28 '11 at 14:57
1  
@Karl Bielefeldt: I had a LISP course in university where we were prohibited from using for- and while-loops. EVERYTHING had to be done recursively. Very hard for the first little bit, but once I got used to it it was quite easy. I think that was still one of the best aspects of that class, and most useful too (I don't use LISP much anymore, but recursive methods are still very easy for me). –  FrustratedWithFormsDesigner Oct 28 '11 at 16:30
    
Recursion is often a good way to blow up your stack if used in the real world (as opposed to academic problems). If you're going to use recursion you need to read up on tail call optimization ( en.wikipedia.org/wiki/Tail-call_optimization ). –  Jim In Texas Nov 16 '11 at 15:56

3 Answers 3

When studying a problem, is there any technique or trick to see that a recursion based approach can be used or not?

Yes, sure, though I would not call it a trick. It should be basic knowledge that in imperative languages there is really only one kind of loop, the while loop (every other loop is merely syntactic sugar). But a while loop corresponds directly to a recursive pattern I give her in a haskell like notation:

loop False action = return ()
loop True  action = action >> loop nextCondition nextAction
   where
       nextCondition = .....
       nextAction    = .....

So, the conclusion is: a recursion based approach can be used for every problem. Like it or not.

share|improve this answer

For me, I believe that a problem is a good candidate for recursion if a smaller subset of this problem could be solved easier or obviously.

An easy example: word count all files that end with ".txt" in a folder including it's subfolders.

  1. what if I had one file? (easy: word count that),
  2. what if I had one folder? (easy: word count each and use (1) for each file then sum),
  3. So now that I have folders and subfolders, I can recurse using (2) (which uses (1))

Another approach would be "pattern matching": Some times similar problems, with well known problems that have been solved with recursion, pop up. Example again: Is there a structure as a tree involved ?(as above). If yes you can probably traverse it.

share|improve this answer

The best way of knowing when recursion is apropriate is from experiance. Use it and you will get more of a feel for when its apropriate. Also try learning a functional langage, I didnt understand how usefull recursion can be till I started learning F#

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.