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

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?

• Is 30 MB really large these days where most computers have GB of RAM and TB of hard drive space? Jul 20, 2011 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. Jul 20, 2011 at 14:43
• 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. Jul 20, 2011 at 15:56
• 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. Jul 20, 2011 at 16:04
• But tree traversal is a "REAL real problem", which many people encounter on almost a daily basis. Jul 20, 2011 at 17:04

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

• "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, 2011 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. Jul 20, 2011 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, 2011 at 14:23
• Generally speaking, you're right, too. I didn't want to appear nitpicking. Jul 20, 2011 at 14:26
• 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.
– user8709
Jul 20, 2011 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.

• 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.
– user8709
Jul 20, 2011 at 9:21
• @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. Jul 20, 2011 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.
– user8709
Jul 20, 2011 at 15:50
``````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.

• +1 for "a problem can be splitted into sub-problems that have the very same structure as the main problem" Jul 21, 2011 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 Feb 13, 2013 at 22:08

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.

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.

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.

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.