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.

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?

share|improve this question
    
Is 30 MB really large these days where most computers have GB of RAM and TB of hard drive space? –  JB King Jul 20 '11 at 14:37
    
30 MB might NOT be large -- but considering the kind of data structure our text was crammed into -- it was really LARGE chuck of text to PROCESS -- and DIFF. –  good_computer Jul 20 '11 at 14:43
1  
Isn’t “traversing a folder structure” real REAL enough? And I completely fail to see, in your example, how recursion should be un-intuitive here, and why its use should even be particularly notable. Your colleague designed a recursive algorithm, just like any other algorithm. You might as well ask how Hoare got the idea to solve the sorting problem recursively. –  Konrad Rudolph Jul 20 '11 at 15:56
2  
Am I right in thinking that you meant "code reuse" more as "executing the same series of operations an indeterminate number of times"? That is as opposed to "code reuse" in the sense of writing generic code for use elsewhere. –  AndyBursh Jul 20 '11 at 16:04
1  
But tree traversal is a "REAL real problem", which many people encounter on almost a daily basis. –  Falcon Jul 20 '11 at 17:04

6 Answers 6

up vote 16 down vote accepted
  • what are the "problem patterns" that call for the solution of recursion

I 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 right

I 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 solution

Anything that needs to traverse trees will be properly expressed by a recursive algorithm.

share|improve this answer
5  
"Every function that can be implemented with recursion can also be implemented iteratively, often by pushing and popping a stack." After all, in languages that utilize stack-based memory, you're already pushing and popping the function data on and off the stack when using recursion. –  JAB Jul 20 '11 at 14:16
    
Only if you compile or interpret the language by a machine ;-) Also, from a very high point of view, the expression and the language are completely independent of machine and hardware and the OS, thus, there's not necessarily a stack. –  Falcon Jul 20 '11 at 14:19
    
Ah, yes, you're absolutely right. I should have said "in implementations of languages/language compilers that utilize stack-based memory". –  JAB Jul 20 '11 at 14:23
    
Generally speaking, you're right, too. I didn't want to appear nitpicking. –  Falcon Jul 20 '11 at 14:26
1  
Infinite lists can be expressed without recursion, at least without a recursive implementation. Python generators can do it, as can the generators in Icon that Python seems to have borrowed the idea from. I believe F# can do this trick, though I'm not sure. Basically, generators are a special case of co-routines (like co-operative multitasking) which are well suited to implementing lazy lists. Each time a generator "yields" a result, the caller regains control and the generator stays idle until the next result is requested. –  Steve314 Jul 20 '11 at 16:05

is recursion a form of "divide & conquer" strategy or a form of "code reuse" -- or, is a design pattern in its own right

Neither. Divide & conquer uses recursion. But recursion isn’t necessarily divide & conquer since the latter means dividing a problem into two (or more) parts and solving each of those symmetrically. In recursion, you don’t do this.

Code reuse is completely unrelated, and a design pattern comes into play at a much higher level. For instance, even divide & conquer (also a higher-level pattern than recursion) is still not considered a design pattern – rather, it’s an algorithmic pattern.

can you give us an example of a real world problem where recursion comes to mind as an immediate solution

Tree traversal. Or more generally graph traversal. This notably includes traversing a folder structure.

And of course anything that uses divide & conquer or dynamic programming since both are naturally expressed in terms of recursion.

share|improve this answer
    
Dynamic programming isn't always naturally expressed as recursion. In fact, dynamic programming strictly refers to tabular approaches - excluding memoization. Opinions seem to vary about this, but the "programming" in "dynamic programming" is actually a math term, referring to tabular approaches (a piece of trivia I picked up from the MIT opensourceware algorithms course). So strictly, dynamic programming exploits optimal substructure using what is often most easily expressed as a simple loop. Memoization is much more likely to imply recursion, but not necessarily. –  Steve314 Jul 20 '11 at 9:21
    
+1 overall, though. –  Steve314 Jul 20 '11 at 9:21
1  
@Steve314 I agree that the practical implementation of DP (be it in a computer program or manually) rarely uses recursion. But the idea is inherently based on a recurrence relation – which is just a recursive formula! – and a base case. –  Konrad Rudolph Jul 20 '11 at 9:29
    
I agree that "optimal substructure" (an optimal solution has optimal partial solutions) is a recursive idea. That's a math/computer science view of recursion, not relating directly to implementation - but the role of recursion in computer science is an important point to make. Few algorithms (and probably no design patterns) are important tools in computer science - most are purely subjects to study rather than tools to be used in studying something else. –  Steve314 Jul 20 '11 at 15:50

Well, recursion can be understand easily if one will try to transform imperative loops to functional functions. Anyway, let's try to give answers to all questions:

what are the "problem patterns" that call for the solution of recursion

If you have a tree-like structure or algorithm you'll need recursion. If your imperative code deals with a stack, you'll need recursion. If a certain step in your algorithm depends on previous steps (think loops), you need recursion. Need here is to be interpreted as can use.

is recursion a form of "divide & conquer" strategy or a form of "code reuse" -- or, is a design pattern in its own right

None. Divide and conquer uses recursion but can be implemented with stacks. Code reuse refers to something else. Design patterns are more complicated than simple recursion.

can you give us an example of a real world problem where recursion comes to mind as an immediate solution

Parsing and everything which deals with tree structures. Even implicit tree structures.

share|improve this answer

what are the "problem patterns" that call for the solution of recursion

In very general terms, recursion is called for when you're solving a problem where f(x) = f(g(x)). Unless you're okay with infinite recursion, g(x) shouldn't evaluate to x.

is recursion a form of "divide & conquer" strategy or a form of "code reuse" -- or, is a design pattern in its own right

None of the above. It's just a way to do the same thing repeatedly, sometimes based on variations on the input. The concept has been around much longer than design patterns, code reuse or even computers, for that matter.

can you give us an example of a real world problem where recursion comes to mind as an immediate solution

Factorials, the Fibonacci sequence, tree traversal and a lot of other problems can be solved with recusrion. Recursion in the sense of a function calling itself isn't necessarily the best way to implement those sorts of things; there are other ways to achieve the same effect (e.g., a stack and loop) that might be more desirable.

share|improve this answer
what are the "problem patterns" that call for the solution of recursion

Derived from the self-similarity of fractals, I would say that self-equality or self-identity (or however it is called) is a typical problem pattern for recursion. I.e. a problem can be splitted into sub-problems that have the very same structure as the main problem.

In the mentioned tree traversal, each sub-tree is a full tree in itself, just like the main tree, and the main tree can be a sub-tree within another tree.

So I guess that your colleague discovered the self-equality properties of your indexing problem. Or he went the other way around and transformed the problem into a self-equal representation.

share|improve this answer
1  
+1 for "a problem can be splitted into sub-problems that have the very same structure as the main problem" –  good_computer Jul 21 '11 at 4:44
    
+1 and to paraphrase: where the solution of problem applies to child layers. My real world example is finding credit card charges that contribute to a "batch". Accounting software will have the individual charges and the batch deposit into the checking account. My case might become a question here as stackoverflow wasn't too sharp about it. stackoverflow.com/questions/14719806 –  Chris K Feb 13 '13 at 22:08

If there is a way to simplify it so that it is easy, that can be the clue that recursion could work. You could take sorting and searching for examples where there do exist recursive solutions like Merge Sort and Binary Search respectively.

Something to keep in mind is how some problems can be solved poorly with recursion like a factorial.

As for a real world example where I'd use recursion, looking up a book off a book shelf can be done quite easily in a recursive manner. I just look at the book and if it isn't what I want I move on to the next one. I stop when I either find the book or hit the end of the row. The looping on checking a book and moving on to the next one could be done recursively. Perhaps this is too real of an example.

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.