Recursion -- as we all know -- is one of those problems -- that wrapping your head around feels like achieving a "milestone" in your programming voyage.
But when it comes to actually using it in real world problems -- knowing the mechanics of recursion is NOT enough -- one must also understand the nature of the problems where recursion is the most suitable solution.
So my question is this...
- what are the "problem patterns" that call for the solution of recursion
- is recursion a form of "divide & conquer" strategy or a form of "code reuse" -- or, is a design pattern in its own right
- can you give us an example of a real world problem where recursion comes to mind as an immediate solution
-- UPDATE --
a lot of answers are referring to "real problems" as tree traversing, of factorial, etc. I would prefer "the REAL real problems" -- let me give you an example...
We had a LARGE chuck of text (about 30 MB of text as a linked list of
structs), and we needed to make an index of it for full text searching. We needed keep the entire index in the memory and re-index the text every 10 minutes.
Every 10 minutes we'd compare the entire text (two linked lists, line by line) with a newly generated chunk of text -- to see what line was changed -- and then we would re-index only that line -- that way we could avoid having to re-index the ENTIRE text. Remember -- we needed to find the diff points between two 30 MB linked lists.
One of my colleagues came up with a fantastic program which used HEAVY recursion to compare the lines -- and then collect the positions where the chucks differed in an array -- yes i know it sounds puzzling -- how could recursion help here -- but it did.
The point is -- how could he see that this problem could be solved smartly with heavy use of recursion?