Recursion -- is it "divide and conquer" or "code reuse"

Question

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?

Answer 1

• 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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

When you write a recursive algorithm, you usually translate a recursive definition of the problem to the code. Then you don't even need to know how it will be executed.

It's what happens in functional programming. In fact, you specify what (definition) rather than how. In other words, you define the base and then define your problem in the term of a sub-problem.

For example consider Factorial algorithm

• Define the base: Factorial(1) = 1;
• Define Factorial n : Factorial(n) = n* Factorial(n-1);

Then when you encounter a problem, you should think if you can define it recursively or not, if you can define it recursively, you almost have solved it.

However, any recursive function shouldn't be a recursive definition. You can define the base and relate (define) the solution of the main problem to solution (definition) of sub-problems. But for this relation you may need a procedure.

An example is MergeSort in which merge could be an imperative procedure to relate the definition or solution of sorting the whole array to the sort of the sub-arrays.