Recursive Programming


Despite often being introduced early-on in most ventures into programming, the concept of recursion can seem strange and potentially off-putting upon first encountering it. It seems almost paradoxical: how can we find a solution to a problem using the solution to the same problem?

Believe it or not, once we get to grips with it, some problems are easier to solve using recursion than they are to solve using iteration. Sometimes recursion is more efficient, and sometimes it is more readable; sometimes recursion is neither faster nor more readable, but quicker to implement. There are data-structures, such as trees, that are well-suited to recursive algorithms. There are even some programming languages with no concept of a loop — purely functional languages such as Haskell depend entirely on recursion for iterative problem solving. The point is simple: You don’t have to understand recursion to be a programmer, but you do have to understand recursion to start to become a good programmer. In fact, I’d go as far as to say that understanding recursion is part of being a good problem solver, all programming aside!

The Essence of Recursion

In general, with recursion we try to break down a more complex problem into a simple step towards the solution and a remainder that is an easier version of the same problem. We can then repeat this process, taking the same step towards the solution each time, until we reach a version of our problem with a very simple solution (referred to as a base case). The simple solution to our base case aggregated with the steps we took to get there then form a solution to our original problem.

Read more at Towards Data Science