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 recursionis recursion a form of divide & conquer strategy or a form of code reuse -- or, is a design pattern in its own rightcan 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?
Recursion -- is it divide and conquer or code reuse
recursion
what are the problem patterns that call for the solution of  recursionI wouldn't say there's such a thing like a problem pattern for the use of recursion. Every function that can be implemented with recursion can also be implemented iteratively, often by pushing and popping a stack.It's a matter of expression and also of performance. Iterative algorithms often times have a better performance and are easier to optimize. However, recursive algorithms benefit from a clearer expression and thus are often easier to read, understand and implement.Some things even cannot be expressed without recursion, infinite lists for example. The so called functional languages heavily rely on recursion, as it's their natural way of expression. The saying is: Recursive programming is functional programming done right.is recursion a form of divide & conquer strategy or a form of  code reuse -- or, is a design pattern in its own rightI would not call it a design pattern. It's a matter of expression. Sometimes a recursive expression is simply more powerful and more expressive and thus leads to better and cleaner code.can you give us an example of a real world problem where  recursion comes to mind as an immediate solutionAnything that needs to traverse trees will be properly expressed by a recursive algorithm.