What is the best way to plan a recursive solution to a problem?

Question

I am learning about recursion. I have solved some other problems using recursion, such as creating a binary tree, Towers of Hanoi, etc. So, I understand what recursion is, but I find myself having difficulty planning and implementing a correct recursive solution.

Are there any general tips out there for planning, thinking about, or implementing recursive solutions to a problem?

Answer 1

Recursion is all about identifying "self-similarity" within the process of solving a problem. A typical example of recursion, calculating the factorial of a positive integer shows this process very well.

Since factorial, n!, is defined as n * (n-1) * (n-2) ... * 1, you should be able to see that

n! = n * (n-1)!

In other words, The factorial of n is "n times the factorial of (n-1)".

If you can understand that statement, and how it exhibits "self-similar" behavior, then you are well primed to tackle recursion. The critical thing when programming recursion is identifying when to stop, and NOT perform the recursive call. In the case of factorial, you stop when the number you are trying to determine the factorial of is 1. The result is simply defined as 1, so you return that value instead of returning the value of the recursive function call.

So my suggestion when thinking about how to tackle a problem recursively is to try to identify this self-similarity in the problem at hand. If you can easily identify such similarity then the problem probably has an efficient and elegant recursive solution. If such self-similarity is not evident, it is probably better suited to an iterative approach.