:tocdepth: 2

.. _loop_for:

Loops, I:  **for**
============================================================================

.. contents:: :local:

.. highlight:: python

We have noted previously how Python will generally move through a
script file while interpreting it (its **flow**): by default, the
interpreter starts at the top of the file and moves downward,
executing each successive line of commands/expressions one time.  

We also saw one way that we could affect this flow, :ref:`using the
if/elif/else conditionals <cond_if>`: these allow us to direct the
interpreter to execute some commands *only if* some condition(s) were
true and perhaps skip over others.  Even in that case, however, each
set of commands in a conditional branch were only executed once, at
most.

In the present section, we introduce a control statement that allows
us to have a set of commands be executed repeatedly, by instructing
Python to "loop" back over a set of lines for a specific number of
times.  This allows us to translate a large class of mathematical
expressions (particularly ones that use indices) to compact code,
which yet again conveniently mirrors the maths itself. All this is
done with a **for loop**.


.. _loop_motivate:

Motivating example for loops
----------------------------

In the previous sections we looked at making arrays and then at
visualizing some.  These objects store a set of values of a particular
type in sequence.  There were several ways to create and provide
values for arrays. We could quickly make an array with a constant
value (all zeros or ones) or one with evenly spaced values, but
anything else became much more difficult: we had to type the values
ourselves.  While this might understandable with entering essentially
arbitrary values, what about when we have a mathematical formula?

Let's revisit making the arrays used in the :ref:`basic plotting
scenario <plot>`: to plot the relation :math:`y=x^2` over the
interval :math:`x \in [-2, 2].` We do this by making two arrays of the
same length, one of *x-*\ values and the other of corresponding *y-*\
values.  We can make the former with a nice, evenly spaced set of
values through our chosen interval::

  x = np.linspace(-2, 2, 5)

Mathematically, we now have a set of indexed *x-*\ values, :math:`x_0,
x_1, x_2,\dots` and our quadratic relation means we should be able to
generate the accompanying *y-*\ values for each one.  This could look
like the following rule (first declaring y, formally):

.. math::
   :label: ex_yx2_slow

   \mathbf{y} & \in \mathbb{R}^5 \\
   y_0 &= x_0^2  \\
   y_1 &= x_1^2  \\
   y_2 &= x_2^2  \\
   y_3 &= x_3^2  \\
   y_4 &= x_4^2  

OK, we can translate that into Python by first defining an (empty)
array of floats, and then assigning the values to each element,
one-by-one::

  y = np.zeros(5)              # same length as x, initialized with 0s

  y[0] = x[0]**2
  y[1] = x[1]**2
  y[2] = x[2]**2
  y[3] = x[3]**2
  y[4] = x[4]**2

That translation is doable, and it *does* produce the correct numbers,
*but* what if our arrays each had 1000 elements?  We would have to get
pretty good at copying-and-pasting, and that seems like far too much
work.

Well, let's go back to the mathematics first. Looking at the relations
in :eq:`ex_yx2_slow`, we might notice a pattern in the relations that
generate each *y-*\ component: each expression is the same, just
changing the index.  So, we could write it more compactly as a single
rule that applies many times, as follows:

.. NTS: 

   somehow, on the version of dvisvgm that is on this out-of-date
   computer, the following expression dropes pieces.  VERY ANNOYINGLY.
   Update on a real computer... and some of these annoying extras can
   be dropped

.. math::
   :label: ex_yx2
   
   \mathbf{y} & \in \mathbb{R}^5 \\
   y_i &= x_i^2,~~~{\rm for}~i=0,\dots,4

This is a nice compact mathematical expression. Is there a nice way to
translate *this* to programming? *Yes, there is, using the same
keyword as we see there:* **for**.

We can think of the expression in :eq:`ex_yx2` as having two parts,
each of which translates pretty directly: specification of the index
values over which the relation hold; and then the expression itself,
to be performed for each index value.  We could translate each part as
in the following table:

.. list-table::
   :header-rows: 1
   :widths: 25 5 30
   :width: 65%

   * - Math 
     - :math:`\rightarrow`
     - Comp 
   * - :math:`\mathbf{y} \in \mathbb{R}^5`
     - :math:`\rightarrow`
     - ``y = np.zeros(5)``
   * - :math:`{\rm for}~i=0,\dots,4`
     - :math:`\rightarrow`
     - ``for i in np.arange(5):``
   * - :math:`y_i = x_i^2`
     - :math:`\rightarrow`
     - ``y[i] = x[i]**2``

.. note:: :ref:`Recall <arrays_arange>` that ``np.arange`` has a
          default ``start=0`` and ``step=1``.  Due to the half-open
          interval specification "[start, stop)", a ``stop`` value of
          5 is appropriate.  If we wrote the possible integer indices
          as :math:`0\leq i <5`, this would be directly appreciable.
          And ``np.arange`` would "guess" the appropriate dtype of int
          here.

We put together the above lines with a bit of specific syntax,
creating our **for loop**:

.. code-block:: python
   :linenos:

   y = np.zeros(5)

   for i in np.arange(5):
       y[i] = x[i]**2

As promised, it very closely matches the mathematical description in
:eq:`ex_yx2`.  Just the order of pieces has been rearranged to begin
the code structure with ``for``, which is a new keyword, similar to
``if``, which we met in the earlier :ref:`introduction to conditionals
<cond_if>`.  Also similar is the style of denoting which expressions
will be *inside* the for-loop, by indenting them---in this case, only
the line ``y[i] = x[i]**2``.

The syntax and behavior are detailed below, but briefly what happens
in the above code is as follows.  The interpreter reaches the keyword
``for`` in Line 3, and will then assign the first value of
``np.arange(5)`` (which is 0) to ``i``, and then execute Line 4, which
would read ``y[0] = x[0]**2``.  After that, the code does *not*
proceed to any Line 5, but instead it *loops back* to Line 3, and
``i`` receives the next value from the array (which is 1); then it
executes Line 4, which now reads ``y[1] = x[1]**2``; and *loops back*
to Line 3.  This continues until ``i`` has iterated through all the
values in the array and executed Line 4 a final time, after which the
code finally proceeds to Line 5.  In the end ``y`` looks as it should:

.. code-block:: none

   array([4., 1., 0., 1., 4.])

For completeness, we would write the full bit of code, including the
definition of ``x`` and a couple small tweaks, as:

.. code-block:: python
   :linenos:

   N = 5
   x = np.linspace(-2, 2, N) 
   y = np.zeros(N)

   for i in range(N):
       y[i] = x[i]**2

Briefly, so many quantities depend on the number of elements in one
array that it is nicer to have a single variable defined with that
value. If we want to change the problem to have 100 points, now we can
do so by just changing the value of ``N``, rather than hunting for
every corresponding use of ``5``.  Additionally, we changed
``np.arange(N)`` to ``range(N)``.  Why?  Well, the syntax and output
of values are the exact same here; however, as discussed below,
``range`` is a more efficient way of generating the index values
(especially for large ``N``), and it only outputs ints. So we will
typically prefer to use ``range`` in these cases.


.. NTS: removed this example in favor of the quadratic one above

   Hopefully that makes sense.  But let's think about this example with
   our math-glasses on: do we notice a pattern or systematic rule here?
   There appears to be a relation between the index of each element and
   the value stored there.  Namely, the element value appears to be the
   square of the index for the first five elements, or, even more
   precisely with mathematical syntax:

   .. math::
      :label: ex_Ci

      &{\rm Let~} C \in \mathbb{Z}^5, \\ 
      &C_i = i^2, ~~{\rm for}~0 \leq i < 5.

   It would be really nice if we could translate this short mathematical
   statement into a compact programming expression.  Just think if we
   wanted to populate ``C`` with 100 values like this-- that would take a
   long time to type!

   Well, fortunately, we can do this. Let's take the above math
   expression in pieces.  

   * :math:`C \in \mathbb{Z}^5`: We previously saw how to translate an
     vector-like object into a Python array (:ref:`here <arrays>`),
     esp. if we wanted a default set of values to fill in later
     (:ref:`here <arrays_zeros>`): ``C = np.zeros(5, dtype=int)``.

   * :math:`C_i = i^2`: From our study of basic operators, assignment and
     indexing arrays, this can be translated directly into programming-ese:
     ``C[i] = i**2``.

   * :math:`{\rm for}~0 \leq i < 5`: specifies a range of ``i`` values to
     iterate over; we :ref:`have seen a way
     <arrays_arange>` to generate an array of those values
     with ``np.arange(0,5)`` (whose elements will be ints if its boundary
     values are int), but we will need something new to add in the
     "iteration" part\.\.\.

     * \.\.\. Fortunately, that ability does exist in programming: it
       translates to a control statement called a **for loop** (which is
       appropriate-- see how the word "for" appears in the math
       statement?).

   With a bit of specific programming syntax as glue, the full Python
   translation of the above pieces would be:

   .. code-block:: Python
      :linenos:

      C = np.zeros(5, dtype=int)
      for i in np.arange(0, 5):
          C[i] = i**2
      print(C)
      print("And the value of 'i' right now is:", i)

   Python evaluates these lines as follows. In Line 1, the array C is
   created, with all five int elements initialized to zero.  Then, in
   Line 2, ``for`` is recognized as a keyword, and it will be followed by
   the **loop variable** (in this case ``i``). The object after the
   keyword ``in`` is called an **iterable**, it provides the ordered set
   of values for the loop variable.  ``i`` will be assigned the
   iterable's first value, which is ``0`` here.  Reaching the colon ``:``
   at the end of the line, the interpreter will look for subsequent
   indented lines and evaluate those: since the current value of ``i`` is
   ``0``, (the indented) Line 3 will be evaluated as ``C[0] = 0**2``.
   When the indentation stops, the interpreter **loops** back to its
   start in Line 2 and assigns ``i`` the iterable's next value ``1``, and
   then proceeds to evaluate the indented lines again but this time with
   its new ``i`` value, so back in Line 3 it performs ``C[1] = 1**2``.
   It continues this looping until it has gone through each value in the
   iterable (in this case, there are 5).  When it has gone through each
   value in the iterable, then the interpreter "exits" the loop, jumping
   to the next *un*\indented line (Line 4) and carries on as normal, with
   the loop variable retaining the last value it had (here, ``i = 4``).

There are a few things to note:

* This is very powerful.  Instead of using *N* lines of code to
  populate *N* elements, we can just use 2 lines!  Try replacing ``5``
  with ``100`` in the above for-loop code.  Much nicer than extending
  the first programmatic approach?

* This type of statement can be used quite generally when there is a
  pattern or rule among elements in an array.  If we can write a clear
  mathematical expression in terms of the index, the rest of our work
  is just translating a couple lines, like above.

* For-loops are also useful outside of working with arrays: any time
  we want simple repetition of a command, or repetition with
  variations on a pattern, or counting, or \.\.\. the list of
  applications is extensive.

* Take a look again at the mathematical expression and at the
  computational for-loop.  Read each one out loud. *Note how similar
  they are.* This is yet another excellent example of what we mean
  that programming is *not* something totally foreign or new: it is
  mainly translating mathematics to be understood by a computer.

* Computers are *not* smart.  So we have to learn Python's keywords
  (here, ``for`` and ``in``) and use its syntax (e.g., ``:`` and
  indentation).  But computers are *fast* at calculations.  So we
  could generate 100,000 values here in a split second.  That makes it
  worth us spending a bit of time to get comfortable with programming.  


``for``: basic syntax and repetition
--------------------------------------------------------------------------

The primary purpose of the ``for`` loop is to allow us to repeat a set
of commands a specific number of times.  There is also a variable that
changes value each time, which we can use in various ways or just
ignore. The basic syntax to repeat one or more commands is:

.. code-block:: python
   :linenos:

   for <loop variable> in <iterable>:
       <a command to repeat>
       <maybe more commands to repeat>
   <other commands, unrepeated>

The keyword ``for`` at the start of Line 1 alerts Python to the start
of the looping structure.  Then a **loop variable** is given, that
will take values in sequence from the **iterable** one at a time. In
the motivating example above, our first iterable was an array of ints,
but we can actually use any Python type that has a collection of
values as an iterable, even non-numeric ones like a string.  We can
also use functions that generate a set of values one-by-one such as
``range``, which was also introduced above---the values matched those
of the ``np.arange`` array, but we didn't need to store them all at
once.  The colon ``:`` ends the line, part of Python syntax we have
seen before with conditionals; the "for" structure is complete.

Following the colon, we have one or more lines of commands/expressions
to be repeatedly evaluated each time the loop variable gets a new
value.  We specify the commands in the "for" loop by indenting them
(just as we did to specify which commands :ref:`were "in" a
conditional branch <cond_if>`).  Any subsequent line that is *not*
indented is outside the loop, and will *not* be repeated.

How does Python evaluate this "for" structure?  When the interpreter
reaches Line 1, it assigns the first iterable value to the loop
variable, and then executes all the indented lines in order; these
lines can contain the loop variable, in which case their expressions
are evaluated with that first value being used.  After reaching the
end of the indented lines, *instead* of proceeding to the next line,
Python *loops back* to Line 1.  It now assigns the next iterable value
to the loop variable, and executes the lines inside the loop again;
any lines using the loop variable now use its new value when they are
evaluated.  Python then loops back to Line 1, and the pattern repeats
until all values of the iterable have been used once.  After the
evaluating the commands with that last value, the interpreter *exits
the loop* and continues on to the evaluate the unindented commands
like normal (without repetition); if the loop was at the end of the
program, it just stops.

.. nts:

   There are some noticeable similarities between this syntax and that of
   the conditionals: keyword at the start, a colon at the end of the
   keyword line, and indentation of commands that are "inside" the
   structure.

   As we will see in later examples, an iterable can be made up of
   non-float numbers or even be non-numeric; but in the case that it *is*
   made of ints, then sometimes we refer to the loop variable as a **loop
   index**. 

Consider the following example:

.. code-block:: python
   :linenos:

   for var in range(-2, 2):
       print("- I am inside the loop :)")
       print("-- Right now, var =", var)
       var2 = var**2
       print("--- & var-squared =", var2)
   print("I am outside :(")
   print("And out here now, var =", var)

Here, the loop variable is ``var`` and the iterable is ``range(-2,
2)``, which sequentially creates integers in the interval ``[-2, 2)``.
The Python interpreter reads Line 1 and the loop variable receives its
first value from the iterable (``var=-2``). Then it executes Lines
2-4, knowing that these are *inside* the loop due to their indentation
after ``:``.  Since it knows there are more values in the iterable, it
*loops back* to Line 1 to reassign the loop variable the next one
(``var=-1``). Then it executes Lines 2-4, etc. until it has worked its
way through the iterable.  At that point, it exits the for-loop and
continues on to Line 5, which is just executed once.  This produces
the following output:

.. code-block:: none
   :linenos:

   - I am inside the loop :)
   -- Right now, var = -2
   --- & var-squared = 4
   - I am inside the loop :)
   -- Right now, var = -1
   --- & var-squared = 1
   - I am inside the loop :)
   -- Right now, var = 0
   --- & var-squared = 0
   - I am inside the loop :)
   -- Right now, var = 1
   --- & var-squared = 1
   I am outside :(
   And out here now, var = 1

Indeed, the loop variable ``var`` has a different value at each
iteration (or "during each loop over the commands").  It can be used
in any expressions.  When Python exits the loop, ``var`` maintains the
last value it had, and it can be used as a normal variable in the
code.  

.. container:: qpractice

   **Q:** After the above loop (where ``var`` is the loop variable),
   does ``var2`` exist after the loop finishes?  If so, what value
   does it have?

   .. hidden-code-block:: python
      :label: + show/hide response

      # Yes, var2 exists, just as var does.
      # var2 retains the value it had during the last iteration, which is: 1


``for``: with arrays
--------------------------------------------------------------------------

One of the most powerful uses of the ``for`` loop is to combine it
with arrays.  Why is this so?

Well, any array has to have a well-defined length to be created; for
example for some 1D array ``A``, we can find its length as ``N =
len(A)``.  We then know that the set of indices of ``A``\ 's elements
are the integers in the range :math:`[0, N)`.  In the common for-loop
syntax ``for i in range(N):``, what are the values ``i`` takes across
all repetitions?  Conveniently, each of the integer values in
:math:`i\in[0, N)`.  So, if we want to go through each element of an
array and perform some calculation (using each element's value,
assigning each element's value, etc.), then the for-loop has a very
convenient structure, such as:

.. code-block::
   :linenos:
      
   A = np.zeros(N)
   for i in range(N): 
       A[i] = <some expression, likely using i>

Notice that we do have to declare (and initialize) ``A`` first, before
looping over all of its values.  This seems logical: before we can
talk about filling in element ``A[37]``, we have to now that that
element even *exists*.  (Python will not just create an array with at
least 38 entries for us if we assign to ``A[37]``---we need to define
``A`` before using any of its elements.)

Consider for example, wanting to make some integer values according to
this mathematical expression:

.. math::
   :label: ex_Bk

   \mathbf{B} & \in \mathbb{Z}^N \\
   B_k &= k^2 - 4k + 2,~~{\rm for}~~ 0\leq k < N\,.

We can translate each of the pieces as follows:

  .. list-table::
     :header-rows: 1
     :widths: 25 5 30

     * - Math expression 
       - :math:`\rightarrow`
       - Comp expression
     * - :math:`\mathbf{B} \in \mathbb{Z}^N`
       - :math:`\rightarrow`
       - ``B = np.zeros(N, dtype=int)``
     * - :math:`B_k = k^2 - 4k + 2`
       - :math:`\rightarrow`
       - ``B[k] = k**2 - 4*k + 2``
     * - :math:`{\rm for}~~ 0\leq k < N`
       - :math:`\rightarrow`
       - ``for k in range(N)``

\.\.\. where we have again used the fact that ``range`` behaves like
``np.arange``.  Therefore the above mathematical sequence would be
stored in an array by adding one final piece of information: an actual
value for *N*, for example 8::

  N = 8
  B = np.zeros(N, dtype=int)
  for k in range(N):
      B[k] = k**2 - 4*k + 2

*Note how similar the mathematical formula and the programmed version
are!* 

Why do we initialize the storage array with 0s?  Well, consider the
following potential coding mistake:

.. code-block:: Python

   N = 8
   Berr = np.zeros(N, dtype=int)
   for k in range(4):             # mistake in range, not N
       Berr[k] = k**2 - 4*k + 2
  
That doesn't lead to an error from the Python interpreter, but what
happens when we ``print(Berr)``?  We see:

.. code-block:: none

  [ 2 -1 -2 -1  0  0  0  0]

\.\.\. where the last four values of ``0`` jump out pretty quickly,
and we can go back to our code see our mismatch in array length and
iterable size.  (Though, there are certainly times where 0s in the
output *will* be expected---thus, we have to know the context and have
an expectation for whether seeing zeros is actually bad or not.  But
many times it is a useful guard.) In many cases, it is just a matter
of convenience to initialize with zeros, namely for this demonstrated
reason.

.. container:: qpractice

   **Q:** What do you need to change about the (correct) version of
   the above for-loop to be able to calculate :math:`\mathbf{B}` over
   the interval :math:`0\leq k < 25`?

   .. hidden-code-block:: python
      :label: + show/hide response

      # Just change a single value:  ``N = 8`` to ``N = 25``.  
      # Isn't that convenient?  (And that convenience is *exactly* the reason
      # we like using variables when a value is used in more than one spot in
      # the code.
   
.. note:: Above, we have seen the explicit statement of vector set and
          size provided in each case, e.g.,
          :math:`\mathbf{y}\in\mathbb{R}^5`,
          :math:`\mathbf{B}\in\mathbb{R}^5`.  This is fairly formal,
          and not always included when problems are expressed,
          particularly in more applied realms. Even if it is not
          provided, we should consider what such a statement would
          look like based on the problem at hand in order to guide our
          array declaration.

If we altered the mathematical expression in :eq:`ex_Bk` slightly to
the following one:

.. math::
   :label: ex_Ck

   C_k = k^2 - 4k + 2\cos(\pi k+0.5),~~{\rm for}~~ 0\leq k < N\,.

\.\.\. then what factors do we need to consider in adapting our
previous result to calculate an array ``C``?  Well, some things to
think about might be:

#. How many elements will ``C`` have, and what is their dtype?
   (*Always* a consideration when using arrays.)

#. How will we calculate the functional values of :math:`cos()`?

#. Does using a function like :math:`cos()` in the elementwise
   expression change the way we assign elements in an array?

.. container:: qpractice

   **Q:** Ponder the above questions, and write your own code to
   calculate ``C`` for ``N = 8``.

   .. hidden-code-block:: python
      :linenos:
      :label: + show/hide code

      import math      # -> Q2: import this module for cos() and pi; could use numpy

      N = 8
      C = np.zeros(N)  # -> Q1: element dtype must be float now

      for k in range(N):
          # -> Q3: no special considerations, just translate the math that appears!
          C[k] = k**2 - 4*k + 2*math.cos(k*math.pi + 0.5)  

   **Q:** Plot both ``B`` and ``C`` (where ``N = 8`` for both) on the
   same graph (since we covered :ref:`plotting arrays earlier
   <plot>`).

   .. hidden-code-block:: python
      :linenos:
      :label: + show/hide code

      import matplotlib.pyplot as plt

      plt.figure("B vs C")
      plt.title("I remembered to write a title!")

      # since x-axis range is ints in range [0, N), we can use single arg syntax
      plt.plot(B, label = 'B')
      plt.plot(C, label = 'C')

      plt.legend()
      plt.ion()
      plt.show()

**In summary, the key feature of both arrays and for-loops in this
context is that there is that the length/size of each are known.**
Thus, it is straightforward to traverse all the elements in a 1D array
with the index values from the for-loop, repeating one or more
commands in each case.  The mathematical part of each element will
often translate directly, as well, so be sure to write down clear
expressions before starting your code.  **Any time you are creating
arrays of sequences or other values with a formula based on index,
consider using a for-loop!**

``range`` syntax
--------------------------------------------------------------------------


.. nts: add something like this here:

   While the iterable values are the same in either case, ``np.arange()``
   produces an full array of all the numbers, which can take up a lot of
   space or memory for big ranges.  In contrast, ``range()`` generates
   the numbers in sequence, but doesn't store them at the same time.  For
   small collections of numbers, the difference is negligible, but we
   typically default to using the latter.

The above examples all specified intervals of the loop index starting
from 0, by including a single argument to be the "stop" value; this is
often useful using a for-loop to go through all elements in some
array.  However, one does not need to be restricted to this, and one
may be interested in other applications where different ranges of loop
indices are desired.  The ``range`` function can take up to three
arguments, changing the "start" and "step" as well.  The syntax
mirrors that of ``np.arange`` presented :ref:`here <arrays_arange>`,
and in typical Python style the interval is half-open, specified as
``[start, stop)``.  One can verify the following cases (we will talk
about ``list``\s later, but for now we use them to store+display the
values produced by ``range``):

.. code-block:: python

   list(range(10))          # def: start = 0, step = 1
   list(range(4, 12))       # def: step = 1
   list(range(3, 15, 2)) 

These yield the following, respectively:

.. code-block:: none

   [0, 1, 2, 3, 4, 5, 6]
   [4, 5, 6, 7, 8, 9, 10, 11]
   [3, 5, 7, 9, 11, 13]

Consider, for example, printing odd numbers from 1 to 100. This can be
done quickly with the range settings in a for-loop::

  for n in range(1, 100, 2):
      print("odd numbers: ", n)

This could also be done having a loop index from :math:`0 \leq n <
50`, since each *n*\th odd number can be written as :math:`2n+1`.
Translating this to a for-loop, one has::

  for n in range(50):
      print("the same odd numbers: ", 2*n+1)

As is often the case in programming, there are several ways to do a
given task.  Sometimes multiple ones are equivalent, while sometimes
other considerations of a problem dictate which is preferable or
meaningfully more efficient.  For example, in the above case the
values of ``n`` themselves differ, which may or may not matter in an
actual programming case.  Additionally, the ``range`` arguments in the
first case clearly show the interval of printed values :math:`[1,
100)`, while those in the latter clearly show how many times the loop
will run (50).  Which is more useful or easier to think about likely
depends on the program and the programmer.

Sequences and recursion
--------------------------------------------------------------------------

As noted above, whenever we want to store mathematical sequences, we
might first consider using arrays.  Why is that? Because the sequences
are ordered sets of values and they use indices (starting at 0), just
like arrays---so it is a convenient match.  And consider going through
the sequence (or array), index-by-index (or element-by-element): what
would be a convenient way to traverse the indices?  How about a
for-loop\.\.\.

Actually, several of the above examples have already demonstrated the
application of for-loops and arrays with sequences. We introduced the
expressions in :eq:`ex_Bk` and :eq:`ex_Bk` by saying they were arrays,
but we could have just as easily said that they were sequences to be
saved as arrays.  Even :eq:`ex_yx2` can be viewed as a sequence for
:math:``y_i``.  It can be pretty hard to tell the two apart in
computing, actually.

But we should note that all the previous examples happened to be from
a particular category of sequence, **non-recursive** ones.  That is,
no element dependended explicitly on any other one in the same
sequence.  However, it is certainly possible to represent
**recursive** sequences in essentially the same manner, with one extra
mathematical consideration to translate.  For example, a rule like
:math:`a_n = a_{n-1}/2` would be recursive: each element is half *of
the previous* element.

A recursion rule states that a given element depends on one or more
previous elements, which in turn depend on one or more previous ones,
etc.  This could go on forever, and we wouldn't be able to actually
calculate any values *unless* we were provided with an extra piece of
information: an explicit starting value (or a set of them).  This is
called having an **initial condition**. For example, consider the
following sequence:

.. math::
   :label: ex_Si

   S_i = (S_{i-1}^2+1)^{1/2},~~{\rm for}~~1\leq i < 16, ~~ {\rm
   and~with} ~S_0 = 2 \,.

Note that it mostly looks the same as previous sequences above except
that: 

#. An extra expression is included, the initial condition (here, the
   [0]th element's value).

#. The range of indices in the general formula does *not* start at 0
   (here, it starts at 1).

We can translate both of these aspects into the computational
representation, again following the mathematics veeery closely. For
point \#1, we just have to assign a value to ``S[0]`` separately from
the loop, and since it is called an *initial condition*, we might take
the hint that it should be done *before* the loop starts.  For point
\#2, we just have to make sure that the the values our loop variable
gets start with 1 instead of 0, which is controlled with our iterable
range---we can do that!

The remaining considerations remain the same: knowing the total number
of elements and their dtype, initializing the array, translating the
mathematical expression, rewriting mathematical subscripts as
bracketed indices, etc.

.. container:: qpractice

   **Q:** Have a try at translating the mathematical expression in
   Eq. :eq:`ex_Si` to Python. What does your final answer look like?

   .. hidden-code-block:: python
      :linenos:
      :label: + show/hide code

      N = 16
      S = np.zeros(N)

      S[0] = 2.                          # new step: set initial condition

      for i in range(1, N):              # new index range: just copy the math!
          S[i] = (S[i-1]**2 + 1)**0.5
      print("The values of S are:")
      print(S)

      # Note also that during each iteration of the above loop, all values
      # on the RHS of the assignment operator in line 6 are known.

   After making your own code, check how similar the above expression
   (and yours) is to the mathematical one above. Note how the new
   aspects translate directly---we really don't have any "extra
   considerations" to ponder here, we just let the mathematics guide
   us as usual.  The above code outputs the following (and check that
   you have the same element values, to within reasonable
   :ref:`floating point approximation <basic_ops_exact>`):

   .. hidden-code-block:: none
      :label: + show/hide code output

      The values of S are:
      [2.         2.23606798 2.44948974 2.64575131 2.82842712 3.
       3.16227766 3.31662479 3.46410162 3.60555128 3.74165739 3.87298335
       4.         4.12310563 4.24264069 4.35889894]

This methodology generalizes for any numbers of elements that are
specified by the initial conditions.  We might just have more lines of
initial conditions, and a new starting index.  It is good to first
make a mental note of whether your sequence is recursive or not.  But
in general **if you first write out the full mathematical formulation
for the sequence---including the range of indices and element
type---that will clearly show how to do the coding.** *So be sure to
do that, and make your life easier!*

.. note:: Above, Python's choice of the number of decimals to specify
          for each element may seem odd; we discuss controlling this
          feature with "string formatting" :ref:`in a later section
          <str_and_format_formatting>`.

.. container:: qpractice

   **Q:** What would happen in the above calculation if we forgot to
   follow the correct range ``range(1, N)``, instead using
   ``range(N)``?  Do we get an error, different results or no change?
   Why?

   .. hidden-code-block:: python
      :label: + show/hide response

      # This is a pretty subtle one in Python.  With ``range(N)``, the 
      # first loop index value will be ``i=0``.  When the expression in Line 7
      # is then evaluated, it will look like:
      #     S[0] = (S[-1]**2 + 1)**0.5
      # Using a negative array index would make an error in many other languages,
      # BUT Python will interpret a negative index as counting backward from the
      # end of the array.  So, the code will run, but with an incorrect value.
      # AND this will overwrite our initial condition with a different value,
      # so every other value in the sequence will be wrong.
      
      # The output values in the mistaken case will be:
      [1.         1.41421356 1.73205081 2.         2.23606798 2.44948974
       2.64575131 2.82842712 3.         3.16227766 3.31662479 3.46410162
       3.60555128 3.74165739 3.87298335 4.        ]

   **Q:** What are the first ten elements of the following sequence
   mentioned above :math:`a[n] = a[n-2]/2`, if :math:`a[0]=10`?

   .. hidden-code-block:: python
      :label: + show/hide code

      # Checklist: 10 elements, dtype should be float, sequence is recursive,
      #            and we DO have an IC. Cool.

      N = 10
      a = np.zeros(N)
      
      # IC
      a[0] = 10. 

      for n in range(1, N):
          a[n] = a[n-1]/2
      print("Done.  The sequence is:")
      print(a)

      # ... which outputs:
      # [10.          5.          2.5         1.25        0.625       0.3125
      #  0.15625     0.078125    0.0390625   0.01953125]

.. note:: | If you like mathematical sequences, then this is a website
            you will enjoy exploring:
          | `The On-Line Encyclopedia of Integer Sequences (OEIS)
            <https://oeis.org/>`_

Elementwise multiplication and dot products
--------------------------------------------

Let's take two mathematical vectors of real numbers, each of length 12,
i.e., :math:`\mathbf{U}, \mathbf{V}\in \mathbb{R}^{12}`.  Consider
performing **elementwise multiplication** to create a new vector
:math:`\mathbf{W}`, so its new components would be calculated as:

   .. math::
      :label: ex_Wi_pre

      W_0 &= U_0 V_0 \\
      W_1 &= U_1 V_1 \\
      W_2 &= U_2 V_2 \\
      &... 

The new vector would necessarily have the same length as the other
two, so :math:`\mathbf{W}\in \mathbb{R}^{12}`.

We are now always on the lookout for indexed expressions with patterns
that allow us to write them compactly.  For the above, we might notice
we could write the above rules compactly as:

.. math::
   :label: ex_Wi

   W_i = U_i\, V_i, ~~{\rm for}~0 \leq i < 12.

Now that we have written it down mathematically and clearly, we should
see a lot of similarity in structure with our previous examples.

.. container:: qpractice

   **Q:** Translate Eq. :eq:`ex_Wi` to Python, and calculate ``W``
   from::

     U = np.array([5.3, 3.3, 2.3, 5. , 9. , 1.9, 2.9, 7.4, 3.2, 6.9, 0.6, 1. ])
     V = np.array([9.1, 5.8, 6.3, 2. , 9.4, 4.2, 5.4, 5.5, 3. , 0.9, 8.3, 2.5])

   .. hidden-code-block:: python
      :linenos:
      :label: + show/hide code

      N = 12
      W = np.zeros(N)

      for i in range(N):            
          W[i] = U[i] * V[i]
      print("The values of W are:")
      print(W)

   .. hidden-code-block:: python
      :label: + show/hide code output

      The values of W are:
      [48.23 19.14 14.49 10.   84.6   7.98 15.66 40.7   9.6   6.21  4.98  2.5 ]

Let's now try taking the **dot product** of the two vectors.  This
procedure is described mathematically in index notation as:

.. math::
   :label: ex_D

   D &= U_0 \, V_0 + U_1 \, V_1 + ... + U_i \, V_i + ... + U_{11} \, V_{11} \\
     &= \sum_{i=0}^{11} U_i\, V_i\,.

The second line contains a compact way of writing the dot product,
using the summation notation with :math:`\Sigma`.  Note that the
output :math:`D` in this case is a scalar, not a vector.

We see indices, but how can we translate Eq. :eq:`ex_D`?  Let's start
by reading the summation syntax: *for i in range 0 through 11, sum up
the product of* :math:`U_i` *and* :math:`V_i`. This expression sounds
and looks like it actually has several features that are similar to
Eqs. :eq:`ex_Wi_pre` and :eq:`ex_Wi` above: we go through all indices
and calculate the elementwise products :math:`U_i\,V_i` for each one.
But instead of storing the resulting products in separate [i]th
components, we add them all up and accumulate the result in ``D``.
So, if we think about forming our programmatic expression, we might
think of some pieces.  We know we need to calculate ``U[i] * V[i]``
for each index *i*, and also do something to store it each iteration;
here is a start to coding this:

.. code-block:: python
   :linenos:

   N = 12
   for i in range(N):
       # zeroth attempt: a schematic or brainstorming idea
       <somehow store U[i]*V[i] within D>

How can we accumulate the calculated products?  As a first guess at
what to put there, we might write something like the following (NB:
since we are making a few attempts, we use ``D1`` for try \#1, ``D2``
for try \#2, etc. as the variable storing the summation, to be able to
compare results:

.. code-block:: python
   :linenos:

   N = 12
   for i in range(N):
       # first attempt at accumulating products (spoiler alert: not successful)
       D1 = U[i]*V[i]

   print("D1 is:", D1)

What is the output?  ``D1 is: 2.5``.  Does that seem correct? It
definitely seems a little smaller than what I would expect given the
numbers in the original arrays\.\.\.  In fact, the above code
**overwrites** ``D1`` at each iteration, and we end up with ``D1`` being
assigned the result of only ``U[11]*V[11]``, rather than accumulating
this sum with the other eleven elementwise products.  To see this, you
could put a ``print(D)`` command inside the loop, to see what
intermediate values of ``D1`` really are---this is a useful debugging
approach.

.. container:: qpractice

   **Q:** Add a ``print`` inside the loop to debug what is happening in
   this part of the code.

   .. hidden-code-block:: python
      :linenos:
      :label: + show/hide code

      N = 12
      for i in range(N):
          D1 = U[i]*V[i]
          print(D1)

      print("D1 is:", D1)

   .. hidden-code-block:: none
      :linenos:
      :label: + show/hide code output

      48.23
      19.139999999999997
      14.489999999999998
      10.0
      84.60000000000001
      7.9799999999999995
      15.66
      40.7
      9.600000000000001
      6.210000000000001
      4.98
      2.5
      D is: 2.5

The way forward is to use an operator that doesn't just *assign* the
value each time, but *adds to* the value already in ``D1`` from the
previous operation.  We have seen :ref:`such an operator previously
<assignment_var_inplace>`, namely the in-place addition ``+=``.  Think
about what the following would do in Line 3 for each iteration:

.. code-block:: python
   :linenos:

   N = 12
   for i in range(N):
       # second attempt at accumulating products (better)
       D2+= U[i]*V[i]

It would first take the result ``U[0]*V[0]`` and add it to ``D2``; in
the next iteration, it would take ``U[1]*V[1]`` and add it to ``D2``;
etc.  *That is what a summation should do!*

\.\.\. except that, if we run the above code, we get the following
error::

   <ipython-input-46-20ecc4e1957a> in <module>
         1 N = 12
         2 for i in range(N):
   ----> 3     D2+= U[i]*V[i]

   NameError: name 'D2' is not defined

\.\.\. because in the first loop iteration, we tried to add to ``D2``,
even though it hadn't been defined or assigned any value yet.

.. note:: You might not see an error message, because you might have
          ``D2`` already used somewhere in your existing example code.
          Even so, we need to properly define ``D2`` for this
          application here, because the it is accumulating value, not
          being replaced/overwritten.

We must initialize ``D2`` before we start our summation in the loop,
picking an appropriate type+value to start.  What value would be
useful?  Well, before we add ``U[0]*V[0]``, it ``D2`` shouldn't have
any magnitude, so how about one more try:

.. code-block:: python
   :linenos:

   N  = 12
   D3 = 0.0          # initialize our accumulator

   for i in range(N):
       # third attempt: accumulating well, and D3 is initialized well :) 
       D3+= U[i]*V[i]
   print("D3 is:", D3)

At this point we should get the more reasonable estimate of ``D3``:

.. code-block:: none

   D3 is: 264.09

This might have been a lengthy discussion, but now we see how to
translate the math expression for summation (and in a compact way):
**use a for-loop with the in-place summation** ``+=`` **and an initial
condition like** ``D = 0.0``.

.. container:: qpractice

   **Q:** What would the following tweaked-version of the above code
   produce?  What (bad thing) is happening?

   .. code-block:: python
     :linenos:

     N = 12
     for i in range(N):
         D4 = 0.0
         D4+= U[i]*V[i]
     print("D4 is:", D4)

   .. hidden-code-block:: python
      :label: + show/hide response

      # ``D4 = 0.0`` has moved *inside* the loop now, so at the start of 
      # each iteration, the value of D4 is reset to 0.  Effectively, it   
      # no longer accumulates values, and the final output will just be 
      # the result of the final product, ``U[11]*V[11]``.

   **Q:** What might be a better way to define ``N`` in all of the
   following summation code examples?

   .. hidden-code-block:: python
      :label: + show/hide response

      # This looks better:  N = len(U)
      # That way, if we change the length of U and V (both would have
      # to change together for a dot-product to be viable), the summation
      # will still apply directly.  So, this new way would be more general
      # and extensible.

.. note:: A quick final note here: summations do *not* always just
          increase with each iteration or have large values.  Here,
          all components of ``U`` and ``V`` were positive, so ``D``
          *did* increase with each product.  But quite often,
          components can be negative or zero, so the "accumulation" of
          products can decrease or not increase the value of ``D``.

Practice 
-------------------------


.. NTS: not sure why this is here:
 
   Firstly, you can download :download:`this PDF of practice questions
   <media/prac_prob_01.pdf>`.

#. What are the first 31 multiples of 17 (not including 0)?

#. Make an array of 25 evenly spaced floats in the interval :math:`x
   \in [-6, 6]`.  Then print out a 3 column table of values: each
   element index, each element value, and the cube of each element
   value.

#. What is the sum of the first 31 multiples of 17 (not including 0)?

#. Let ``c`` be an array of 151 floating point values evenly spaced in
   the interval :math:`[-10, 10]`.  Make an array ``z`` where:

   .. math::
      :label: ex_zi

      z_i = \cos(2\pi c_i/T) + \cos(2\cdot2\pi c_i/T) + \cos(3\cdot2\pi c_i/T)

   where :math:`T=12`. Plot the result (i.e., ``z`` vs ``c``).

#. Translate to an array:

   .. math::
      :label: ex_Gn

      &G_n = (-1)^n\,n, ~~{\rm for}~0 \leq n < 10.

#. Translate to an array:

   .. math::
      :label: ex_Hj

      &H_j = \mbox{True and bool}(j~\%~3), ~~{\rm for}~0 \leq j < 10.

#. The following is a method for calculating the square root of a
   positive number *S* (known as the *Babylonian method* or *Heron's
   method*):
   
      .. math::
         :label: ex_babylon

         x_0 &= 1 \\
         x_k &= \dfrac{1}{2}\left(x_{k-1} + \dfrac{S}{x_{k-1}}\right)\,,~k>0.
         
   Use 15 iterations to estimate :math:`\sqrt{2}`, :math:`\sqrt{36}`
   and :math:`\sqrt{987654321}`. Check the approximation by squaring
   the result.  (NB: one can actually select :math:`x_0` to be any
   positive number; setting it to be closer to the actual square root
   accelerates the convergence.  However, :math:`x_0 = 1` is fine for
   convergence here.)

#. | a) Write a code to calculate, store and print the first 20 numbers
     of the Fibonacci sequence, whose *n*\ th digit is the sum of the
     previous two.  The first few numbers are:
   | 0, 1, 1, 2, 3, 5, 8, 13\, \.\.\.

   | b) What is the ratio of successive elements of the Fibonacci,
     with the larger number in the numerator (ignoring the
     divide-by-zero case)?  In the limit of having an infinite number
     of terms, this value approaches and defines the `Golden Ratio
     <https://en.wikipedia.org/wiki/Golden_ratio>`_, :math:`\varphi`.

#. Write a code block that asks the user to input an integer ``n`` and
   then draws a right angle isosceles triangle with asterisks
   (``'*'``) of height ``n``. For example, for ``n=4``, the output
   should look like:

   .. code-block:: none

      *
      **
      ***
      ****

#. Make an array whose values are :math:`P = \cos(3\pi t)`, for
   :math:`t \in [-5,5]`. Also make an array whose values are :math:`Q =
   \sin(5.5\pi t)`, over the same domain of :math:`t`.  (Choose a number
   of elements per array that makes a pretty plot.)

   a. Plot ``P`` vs ``t`` and ``Q`` vs ``t`` on the same graph (label each).

   #. Plot:``P`` vs ``Q`` on a separate graph.

#. Consider the sequence defined by :math:`x_0 = 2` and :math:`x_n =
   2x_{n-1}-1`. Ask the user for an integer :math:`n`, then calculate
   and print the first :math:`n` terms of the sequence in a simple
   table. For example, for :math:`n=4` we would get:

   .. code-block:: none

      i    x[i]
      ---------
      0    2
      1    3
      2    5
      3    9
      4    17
      


.. NTS: this question might belong in a different section?


   #. Make a list of your name, the name of the person to your left and
      right, and then sort the list alphabetically.


.. NTS: excellent questions when we have combined loops and conditions

   #. Write a code block that prints all the factors of a positive integer.

   #. How many four-digit numbers are divisible by both 3 and 7?

   #. The digit 8 appears: once in 8, twice in 88, and twice
      in 828. Write a program to calculate the number of times the digit
      8 appears in numbers in the interval [1000, 9999].

   #. Across *all* positive integers, what is the 1000th number divisible
      by both 3 and 7 but not by either 14 or 9 (e.g., 21 would be
      counted, but not 42)?



.. NTS: not introducing nested loops yet:

   #. Write the first 50 terms of the sequence into an array:

      .. math::
         :label: ex_Pn

         P_n = \sum_{i=0}^n \frac{(-1)^i}{2i+1}` 

      Based on the values, what can you say about the apparent
      convergence of this sequence?


.. NTS:

   old example from arrays

    #. Use ``for`` loops to make the following:

       i. :math:`~\displaystyle x_i = \log_{10}(i+1)`, for
          :math:`~\displaystyle 0 \leq i < 11`

       #. :math:`~\displaystyle y_n = \sqrt{4n}+1`, for
          :math:`~\displaystyle 0\leq n < 17`

       #. :math:`~\displaystyle z_k = (3k + 4i)^3`, for
          :math:`~\displaystyle k \in [0, 20]`. Note that ``i`` in this
          expression is the imaginary number.

       #. Define an array ``flip`` as follows: ``flip[i]`` equals
          :math:`\displaystyle i^3` for even ``i`` and
          :math:`\displaystyle i^2` for odd ``i``, over the
          interval :math:`~\displaystyle 0\leq i < 20`

       #. An array ``zabs`` whose values are the absolute values of ``z``
          from the previous question.

       #. :math:`~\displaystyle M_{i,j} = 30 - 6i - j`, for
          :math:`~\displaystyle 0 \leq i < 6;~ 0 \leq j < 5`


       #. Ask the user for an integer between 77 and 88 (inclusively);
          to get input from the user, you can use the basic python
          command ``input()``. If they do, say "Thanks!" and
          finish. If they don't, then have the prompt repeated until
          they do.