# How can I best study a problem to determine whether recursion can/should be used?

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?

• 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/… Oct 28, 2011 at 10:27
• Anything with a loop can be done with recursion. The question is really if the recursive method is more straightforward. Oct 28, 2011 at 14:57
• @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). Oct 28, 2011 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 ). Nov 16, 2011 at 15:56

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.

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#

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.