5

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?

Improve this question
4
  • 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
    Commented Oct 28, 2011 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
    Commented Oct 28, 2011 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
    Commented Oct 28, 2011 at 16:30
  • 1
    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
    Commented Nov 16, 2011 at 15:56

3 Answers 3

Reset to default
10

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 with (1) available: generate a list of files, apply (1) then sum the results),
  3. what if folders have subfolders? (Recurse using (2) (which uses (1))

Another approach could 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 so, you can probably traverse it.

Improve this answer
2

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#

Improve this answer
0

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.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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