When to Use Recursion?

Nowadays, many programming languages such as Haskell, Scala, JavaScript, etc. use Functional Programming. An important concept of functional programming is recursion. Entire languages are now being based on recursion.

In general, problems that can be solved with a non-recursive code can also be solved by recursion. However, the interesting part is, most problems that cannot be solved by a non-recursive code can also be solved by recursion.

It is important to note, even if it is possible to solve any problem with recursion, it does not mean that we should.

Let’s have a look at some pointers that will help us identify whether to use recursion or the conventional iterative method for solving a specific problem:

Use Where Appropriate

Recursion should be used where you feel like it is appropriate or it just feels natural. You will most likely encounter problems where you cannot come up with an iterative solution for it and that is where recursion fits in nicely.

Problem Breaks Down Into Smaller Similar Subproblems

The most obvious sign to use recursion is when a problem can be broken down into smaller subproblems. When you encounter a problem and you observe a pattern of it breaking down into similar subproblems, then that question can likely be solved using recursion.

Problem Requires an Arbitrary Number of Nested Loops

For some problems, we might have to nest an arbitrary number of loops, to solve them. However, since we do not know the number of loops, the solution might get complicated. Such problems can be more easily solved using recursion.

If you know the number of loops that have to be nested, use the iterative approach otherwise use recursion.

For example, iterating through a graph or a tree, finding all permutations of a string, etc.

---

In the next lesson, we will have a look at a recursive problem.