..  _recursion-revisited:

Functions That Call Themselves
##############################

This idea is a bit shocking to beginners. 

Suppose you iare writing the code for a function, and it occurs to you that using the same
funciton you are writing to solve the problem you are trying to solve would
help. How would that work?

Let's consider the classic first example of this.

Factorial
*********

You should have learned about this at some point in your math classes:

..  math::

    5! = 5 * 4 * 4 * 2 * 1

    n! = n * (n-1) * (n-2) ... * 1

But wait!

..  math::

    n! = n * (n-1)!

This looks interesting. However, there is a catch to this formula. It does not
work for any value of ``n`` (only positive numbers), and we need a way to stop it.

That way is found by noting that 1! is simply 1. That is called a ``base
case``. The factorial of any other (positive) value of ``n`` can be figured out
using that simple "recursive" formula.

But what does it look like in code?

..  literalinclude::    code/ex1.py
    :linenos:
    :caption: ex1.py

That is about as simple as it gets! We have produced a short chunk of code that
should work. It is hard to mess up a piece of code this short. But does it
work?

Let's run it and see:

..  command-output::   python ex1.py
    :cwd: code

Here is another classic recursive problem:

The formula for a ``Fibonacci Number`` for some parameter "n" is defined as:

    * F(0) = 0
    * F(1) = 1
    * F(n) = F(n-1) + F(n-2)

In this case, there are two ```base cases``, one for ``1`` and one for ``0``. Here is the code:

..  literalinclude::    code/ex2.py
    :linenos:
    :caption: ex2.py

here is this code in action:

..  command-output::    python ex2.py
    :cwd: code

Recursion in detail
********************

Is there anything wrong with this?

Let's modify that last program, and see what is really happening:

..  literalinclude::    code/ex3.py
    :linenos:
    :caption: ex2.py

Running this gives this output:

..  command-output::    python ex3.py
    :cwd: code

Now we can see the issue. We are actually calling the function over and over,
actually solving a problem we may have already worked out. But, we did not keep
that old solution around, so we need to figure it out again. This wastes
processing time. 

For a small number like five, this is no big deal, but what about 10,000. How
many wasted calls do we make then.

Can we do better?

To answer that, we need to think of a way to save our old answers!

Since we will want to check for old answers based on a value of ``n``, it looks
like a Python dictionary will do the job. Here is a modified program that
should be faster:

..  literalinclude::    code/ex4.py
    :linenos:
    :caption: ex4.py

Running this gives this output:

..  command-output::    python ex4.py
    :cwd: code

It looks like this still works, but have we actually improved anything. There
is a simple way to see. Let's time the code:

Using a standard Python package called ``timeit`` we can create a stopwatch:

..  literalinclude::    code/ex5.py
    :linenos:
    :caption: ex5.py

Now, we should see some time data:

..  command-output::    python ex5.py
    :cwd: code

To see our improvement, we need to add timing code to the simple recursive
version:


..  literalinclude::    code/ex6.py
    :linenos:
    :caption: ex6.py

Running this gives this output:

..  command-output::    python ex6.py
    :cwd: code

That is a pretty significant improvement.


Using Recursion on Lists
************************

If you think about it, a linked list is a recursive thing as well. We start off
with an empty list, then add a node. If we are using a simple node object, with
a number and a pointer to the next node in the list, that "next node" pointer
is NULL, indicating that it is the last one in the list. If we add one more
node to the end, we have yet another linked list, this one consisting of a head
object, and what can be considered as another linked list (with one item in
it). By making use of this fact, we can write routines that access our list
using recursion.

As a refresher, here are the original routines we used to build a simple linked
list of names:

So Which is better?
*******************

For every recursive routine you write, there is an equivalent non-recursive
method that will do the same thing. In general, the non-recursive routine will
be harder to write, and may be easier to write wrongly. So, most of the time,
it is probably better to start off writing recursive routines if you can, then
rewrite them if you need more speed, and need to use less memory to get your
job done.