Recursion
=========

.. index:: recursion

If you look up on the Internet for a definition of recursion, you will
often see something like the following:

**Recursion**
    See recursion.

This is wrong, wrong, *wrong*, **wrong** .... WRONG!

If you were a computer program, trying to parse the above definition,
you would get stuck in an infinite loop. Since you are reading this, it
means that either you did not behave like a computer and got stuck in an
infinite loop OR that you did not read everything here and, in
particular, skipped over the above definition.

Recursion is sometimes described as being difficult to grasp. Do not
believe this. If you understand loops, you can understand recursion.

So, what is recursion you ask?...

Recursion is the process of repeating items in a self-similar way. For
computer programs, it means repeating instructions - like in a loop.
And, like in a loop, we do not want to get stuck forever.


.. toctree::
   :maxdepth: 2
   :numbered:

   recursion1
   recursion2
   recursion3
   recursion4


.. admonition:: For educators

    Some consider recursion to be a very difficult concept to grasp;
    you should feel free to skip over this part which essentially
    stands alone.

    I've chosen to introducer recursion here because, on the one hand
    all the required prerequisites have been seen and, on the other hand,
    the recent introduction of the ``while`` loop which can often
    be replaced by recursion, and vice-versa, gives an opportunity to
    strengthen the understanding of looping.  If one waits until later,
    when the student is thoroughly familiar with ``while`` loops which
    has become second nature to them, the concept of recursion may look
    to them as something very different and suddenly "very difficult"
    in comparison.