.. _chap-recursion: =========== Recursion =========== [status: partially-written] Motivation, prerequisites, plan =============================== Recursion comes up in many very important computer algorithms, to the point where it's reasonable to say that it is an essential tool for most programmers. When an algorithm can be expressed recursively it almost feels like we're cheating in how we implement it: we get this complex result from two very simple statements! The only prerequisite for this chapter is the 10-hour *Serious Computer Programming for Youth* course. Our plan is to first try to get a feeling for recursion with some visual examples. Then we state the two key parts of a recursive definition (and hence of a recursive algorithm): the *recurrence relation* and the *initial condition*. With this under our belts we take on examples from math and other areas. 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 ============= .. sidebar:: History of the Liar's Paradox :subtitle: From Epimenides to Quine Epimenides said "all Cretans are Liars". The modern version is "This sentence is a lie." - "This sentence is false." - "The next sentence is true. The previous sentence is false." - Read this sentence and do what it says twice. - Dialogs from Godel, Escher, Bach - Quining: "yields falsehood when preceded by its quotation" yields falsehood when preceded by its quotation. https://en.wikipedia.org/wiki/Quine%27s_paradox - Russell's Paradox. https://en.wikipedia.org/wiki/Russell%27s_paradox - Aristotle's "law of excluded middle". https://en.wikipedia.org/wiki/Law_of_excluded_middle Components of a recursive definition ==================================== A recursive series is defined by two components: Recurrence relation Specifies what the *next* element of a sequence is, based on the previous one. If we are talking about a numbered sequence, then this means defining the :math:`n`:sup:`th`\ element in terms of the :math:`(n-1)`:sup:`th`\ element (and maybe :math:`n-2` and earlier elements as well). Initial condition You can't go on applying the recurrence relation forever, so at some point you have to stop. We do this by specifying an initial condition. For example we can set an element to have a clear value when :math:`n = 0` or :math:`n = 1`. Let us look at some examples of recursive definitions in simple math. .. _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 \times x & {\rm \; when \; } n = 2 \\ x^n & = x \times x^{n-1} & {\rm \; when \; } n > 2 \end{align} In this you can see that :math:`x^n` is defined recursively with recurrence relation :math:`x^n = x \times x^{n-1}` and initial condition :math:`x^0 = 1`. 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} This is very easily implemented in Python: .. code:: python def factorial_recursive(n): if n == 1: return 1 else: return n * factorial_recursive(n-1) .. _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 ~~~~~~~~~ .. exercise:: Write an analogous program that calculates :math:`n!` You may use :numref:`listing-recursive-power-py` as a guide. .. exercise:: 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. Recursion with data structures ------------------------------ The list is a very important data structure, and it often lends itself to surprisingly simple recursive algorithms. A simple example is to *reverse* a list in python. A list with just one element ``l = ['dude']`` will have an obvious reverse, which is just itself. And if you have reversed a list with :math:`n` elements, then to do a list with one more element is easy. Start out with: .. code:: python l = [2.5, 17, 'dude'] and imagine that you have reversed all but the last element: .. code:: python # this is not ready to run! l = [2.5, 17, 'dude'] # we have somehow reversed the first two elements l_reversed_without_last = [17, 2.5] # now we complete the task by putting the last element at the start l_reversed = [l[-1]] + l_reversed_without_last From this pseudo-code *(that will absolutely not work!)* you can get an idea for a recursive algorithm: Recurrence relation reverse(list) = [last_element] + reverse(list_without_last_element) Initial condition reverse(list_with_just_one_element) = that_list_with_just_one_element Remembering that in Python you can get the last element of a list ``l`` with ``l[-1]``, and the rest of the list with ``l[:-1]``, we can write an inline function to do this: .. code:: python def reverse_list_recursive(l): if len(l) == 1: return l else: return reverse_list_recursive(l[1:]) + [l[0]] .. code:: python # now run it with: reverse_list_recursive([2.5, 17, 'dude']) .. code:: python # do some numbers with: reverse_list_recursive(list(range(20))) .. code:: python # now do a much longer list reverse_list_recursive(list(range(200))) Visualizing what the recursion is doing ======================================= We clearly agree that the magic of recursion works, but it can be frustrating to not have an intuition of the intermediate steps. Let us modify the function so that it prints how it's putting together the pieces of the lists in the intermediate stages. .. _listing-recursive-pivot-end-py: .. literalinclude:: reverse_list_recursive_pivot_0.py :language: python :caption: Reverse a list with a recursive algorithm, breaking it into ``l[0]`` and ``l[1:]``. This prints some information on the calls to the recursive algorithm. .. _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. .. _listing-hanoi-py: .. literalinclude:: hanoi.py :language: python :caption: Recursive solution to the Towers of Hanoi game Now look at the program in :numref:`listing-hanoi-py`. 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. .. exercise:: 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. .. exercise:: 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. 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 nonrecursive algorithm: .. code-block:: python def factorial_nonrecursive(n): assert(n > 0) result = 1 for i in range(1, n+1): result = result * i return result never juggles more than two numbers at once in its memory. Another problem with recursive list-processing algorithms is that they often have to shuffle around copies of the list data. The list reversing algorithm in :numref:`listing-recursive-pivot-end-py` shows how list slices like ``l[1:]`` cause most of the list data to be copied in memory.