---
tags: programming languages, Towers of Hanoi
---

(part of a course on programming languages)

# Recursion as a Problem Solving Technique

Many problems have a simple recursive solution. A recursive implementation then has the advantage that it stays close to the specification. That can save a lot of money (development, validation, maintenance, ...)

Why is recursion such a powerful problem solving technique?

First, in very general terms, recursion is one particular mathematical formalisation of the scientific method as described by [Descartes](https://en.wikipedia.org/wiki/Ren%C3%A9_Descartes) in the book that may well be the most influential work of philosophy (and [mathematics](https://archive.org/details/geometryofrene00desc/page/2/mode/2up) and science), ever written, his [Discourse on the method](https://en.wikipedia.org/wiki/Discourse_on_the_Method#Part_II:_Principal_rules_of_the_Method).

In more detail, recursion formalises items two (divide) and three (build), see [here](https://en.wikipedia.org/wiki/Discourse_on_the_Method#Part_II:_Principal_rules_of_the_Method). Software engineers will also appreciate items one and four.

So how do we use recursion as a problem solving technique?

- We think how to divde a problem in to smaller sub-problems and wirte a program `Divide`.
- We assume that we have a solution for the sub-problems.
- We write a program `Build` that builds from the solutions of the smaller problems the solution of the bigger problem.

(Instead of "divide" one can say "break down" or "analyse" and instead of "build" one can say "put together" or "synthesize".)

In pseudocode:

S = Build(S(Divide)

The trick here is that recursion (the solution `S` calls itself) allows us to solve a problem by assuming that we have already have a solution to the problem. We only need to find `Divide` and `Build`, the rest happens by itself.

And this really works? Yes, it does ...

[Any sufficiently advanced technology is indistinguishable from magic.](https://en.wikipedia.org/wiki/Clarke%27s_three_laws)

Let us look at a couple of examples.

## The Towers of Hanoi

One of the classical examples is [The Towers of Hanoi](https://hackmd.io/@alexhkurz/rJQwvpyMY). I challenge you to come up with a solution that is not recursive.

(Btw, why do we know that every recursive program can be transformed into an iterative one?)

## Fast Exponentiation

Suppose you only know how to multiply. How can you compute $3^{16}$?

If you think iteratively you probably come up with sth like
\begin{align}
3^{16} &= ((((((((((((((3\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3\\
&= (((((((((((((9\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3\\
&= ((((((((((((27\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3\\
&= (((((((((((81\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3\\
&= ((((((((((243\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3)\cdot 3\\
&= \ldots
\end{align}

Now this gets so tedious, that you don't want to continue with this ...

By the way, it is a good idea to cultivate this feeling of being annoyed by tedious tasks. If it is difficult because it is boring and repetitive we should do something about it!

Thinking iteratively, as above, means that you think about how to build a solution.

Thinking recursively means that you start by thinking about how to divide the problem into smaller problems.

How many smaller problems? If the structure of the problem does not dictate an obvious answer, try 2 first.

So how can we divide the computation of $3^{16}$ into two smaller tasks?

\begin{align}
3^{16} & = 3^8 \cdot 3^{8} \\
& &\textrm{ok that was easy}\\
& &\textrm{how do we continue?}\\
& &\textbf{divide } \textrm{in the same way!}\\
& = 3^4 \cdot 3^4 \cdot 3^8 \\
& = 3^2\cdot 3^2 \cdot 3^4 \cdot 3^8 \\
&& \textrm{now we can start to } \textbf{build}\\
& = 9\cdot 9 \cdot 3^4 \cdot 3^8 \\
& = 81 \cdot 3^4 \cdot 3^8 \\
& & \textrm{we already computed $3^4=81$}\\
& = 81 \cdot 81 \cdot 3^8 \\
& = 6561 \cdot 3^8 \\
& & \textrm{we already computed $3^8=6561$}\\
& = 6561 \cdot 6561 \\
& = 43046721
\end{align}

This idea can be turned into an algorithm for [fast exponentiantion](https://en.wikipedia.org/wiki/Exponentiation_by_squaring).

It is a nice example showing that **recursion is a powerful problem solving technique, independently of whether you implement your solution via recursion or iteration** in the end. While fast exponentiation is usually implemented iteratively, it is easier to find when you think about it recursively.

Moreover, the strategy of dividing problems in half is at the heart of so many famous algorithms that it is really good to remember it ...

## Brief Historical Excursion (Optional)

I recommend to just browse through the pages of Descartes' [Geometry](https://archive.org/details/geometryofrene00desc/page/2/mode/2up) and admire how modern it looks. This is the maths you still learn in school today. Maybe I am exaggerating a little, but any maths written before Descartes is almost impossible to understand today without spending hours on trivial details. Just look at the mess [Galileo](https://en.wikipedia.org/wiki/Galileo_Galilei) is making of the very basic equation of motion $$distance = spead \cdot time$$ If you don't believe me read through the proofs of his [theorems of motion](http://galileoandeinstein.physics.virginia.edu/tns_draft/tns_153to160.html) as formulated by himself in the celebrated *Dialogues Concerning Two New Sciences* and meditate on how easy all of this is to us who are able to use Descarte's algebra. All Galileo is doing here is to solve the equation for $distance$, $speed$ and $time$ and what we do in a line of high-school algebra takes one of the greatest minds of all time pages of almost unintelligible writing. And Galileo was a great writer, try page 2 (page 30 in the pdf) of his [Dialogues Concerning Two New Sciences](http://oll-resources.s3.amazonaws.com/titles/753/0416_Bk.pdf) where Salviati and Sagredo discuss the interesting question why scale matters in engineering but not in geometry.[^galileo] It is really captivating.
(Btw, the two new sciences here are strength of materials and the motion of objects.)
(Having praised Descartes, Galileo was at least equally influential. Nirenberg's [The Birth of Modern Science](https://www.albany.edu/~rn774/fall96/science2.html) is an excellent introduction to the influence of Galileo and Descartes. (I thought that he wrote that Galileo's most important idea was to recognise that the laws of physics do not only govern the heavens but also what happens on earth, but maybe I picked this up somewhere else.) More by Nirenberg on the [History and Philosophy of Science](https://www.albany.edu/~rn774/lecture_index.html).)

[^galileo]: Here is how they start the discussion: 

## Further Study

- The freeCodeCamp [video on dynamic programming](https://www.youtube.com/watch?v=oBt53YbR9Kk) has many examples of recursion as a problem solving technique. Moreover it teaches you dynamic programming (=recursion+memoization). I also recommend doing the other examples (`gridTraveller`, `canSum`, `howSum`, `bestSum`, `canConstruct`, `countConstruct`, `allConstruct`), in particular if you want to prepare for a coding interview. You can also try your own problems such as allSums (all sums). Make sure to develop your own answer before watching the solution in the video. The takeaway will be that once you have a correct solution, making it efficiency using memoization will be easy (in these kind of problems). The second half of the video is about turning recursive solutions into iterative ones using tabulation.
- [Techie Delight](http://www.techiedelight.com/recursion-practice-problems-with-solutions/) has a long list of recursion practice problems with solutions.