.. _chap-recursion:

===========
 Recursion
===========

[status: partially-written]

Motivation, prerequisites, plan
===============================


Visual examples
===============

- Point a webcam at the screen.

- https://i.stack.imgur.com/0DaD5.jpg (or other paintings -- Escher?).

- Break sections from broccoli.

- Draw koch snowflake or Sierpinski gasket.

Word examples
=============

- Read this sentence and do what it says twice.

- Dialogs from Godel, Escher, Bach


.. _sec-simple-math:

Simple math
===========

Define power with recursion:

.. math::

   3^5 = 3*3^4 = 3*(3*3^3) = 3*(3*(3*3^2)) = 3*(3*(3*(3*3)))

which suggests this generalization:

.. math::
   :nowrap:

   \begin{align}
   x^n & =  1            & {\rm \; when \; } n = 0 \\
   x^n & =  x            & {\rm \; when \; } n = 1 \\
   x^n & =  x*x          & {\rm \; when \; } n = 2 \\
   x^n & =  x*x^{n-1}    & {\rm \; when \; } n > 2
   \end{align}

Factorials are defined like this:

.. math::
   :nowrap:

   \begin{align}
   2! &= 2 \times 1 = 2 \\
   3! &= 3 \times 2 \times 1 = 6 \\
      &\dots \\
   n! &= n \times (n-1) \times (n-2) \dots \times 2 \times 1
   \end{align}

which lends itself to a very simple recursive definition:

.. math::
   :nowrap:

   \begin{align}
   n! & = 1               & {\rm \; when \; } & n = 1 \\
   n! & = n \times (n-1)! & {\rm \; when \; } & n > 1
   \end{align}


.. _sec-programming-simple-math-recursion:

Programming simple math recursion
=================================

In :numref:`listing-recursive-power-py`: you can see a simple program
which calculates :math:`x^n`.  Go ahead and try it out to calculate
powers.

.. _listing-recursive-power-py:

.. literalinclude:: recursive-power.py
   :language: python
   :caption: Program which calculates powers using recursion.

Exercises
~~~~~~~~~

* Write an analogous program that calculates :math:`n!` You may use
  :numref:`listing-recursive-power-py` as a guide.

* The `fibonacci numbers`, which appear in many beautiful
  manifestations of nature, are defined recursively:

.. math::
   :nowrap:

   \begin{align}
   fib(n) & = 1                   & {\rm \; when \; } & n = 0\ or\ n = 1 \\
   fib(n) & = fib(n-1) + fib(n-2) & {\rm \; when \; } & n > 1
   \end{align}

Now write a program that calculates :math:`fib(n)` You may once again
use :numref:`listing-recursive-power-py` as a guide.


.. _sec-towers-of-hanoi:

Towers of Hanoi
===============

The Towers of Hanoi is a puzzle in which you have three pegs and a
pile of discs on one of them.  The discs always *must* be piled with
bigger discs below smaller discs.  The goal is to move the discs from
their initial peg to another peg, using the extra peg if you need to.

:numref:`listing-hanoi-py`:

.. _listing-hanoi-py:

.. literalinclude:: hanoi.py
   :language: python
   :caption: Recursive solution to the Towers of Hanoi game

This is a surprisingly short program because the information about the
state of the pegs and discs is not in any of the program variables!
It's all stored in function stack as part of recursive calls.

Exercises
~~~~~~~~~

* Count how many disc movements are made in total to solve the puzzle,
  and plot that as a function of how many discs you picked for that
  run.

* Find a way to intercept the program to draw (in simple ascii art, or
  with a canvas as shown in :numref:`sec-drawing-on-a-canvas`) the
  intermediate stages of the solution.

Further exploration
~~~~~~~~~~~~~~~~~~~

* I should give references to visualizations.


Should we really use recursion in programming?
==============================================

We saw in :numref:`sec-towers-of-hanoi` and we will see again in
:numref:`chap-getting-to-philosophy` that some problems are expressed
very simply using recursive algorithms.  Should we always look for
recursive solutions?

The trade-offs come when you are dealing with very high numbers of
recursive calls.  If you imagine yourself reciting this in your head:

   Seven factorial is seven times six factorial which is seven times
   six times five factorial which is ... which is seven times six
   times five times four times three times two times one times zero
   factorial; that last one is one so I can now finally multiply them
   all together: seven times six times five times four times three
   times two times one times one which is fivethousand and fourty.

you can see that you have to keep a lot of stuff in mind.  The simpler
algorithm:

.. code-block:: python

   def factorial_nonrecursive(n):
       result = 1
       for i in range(n):
           result = result * i
       return result

never juggles more than two numbers at once in its memory.