*****
Loops
*****

* ``if``/``else`` are great for having a block of code run when some condition is ``True``
* Sometimes we need a block to repeatedly run *while* some condition is ``True``


Reusing and Updating Variables
==============================

* Before we look at loops, consider the following code

.. code-block:: python
    :linenos:

    a = 5
    print(a)

    b = 6
    print(a)

    a = a + b
    print(a)

    a = 3
    a = a + 1
    print(a)


.. admonition:: Activity

    What is the value of ``a`` at each print statement? In other words, ``a`` is printed out four times --- what values
    are printed out?


* The point being emphasized is that there is nothing stopping us from reusing variables

    * Assign a value to some variable
    * Update/change the value stored in that variable


* A very common pattern for incrementing the value of some variable in programming is as follows

.. code-block:: python
    :linenos:

    a = a + 1

* The above example will add one to whatever value is stored in ``a`` and then store that new value back to ``a``
* For example

    * If ``a`` starts with the value ``5``
    * Calculate ``a + 1``, which is ``6`` in this example
    * Store the newly calculated value of ``6`` in ``a``

* This and similar patterns are so common that many programming languages have shorthand operators for this


.. code-block:: python
    :linenos:

    a += 1      # Effectively the same as a = a + 1

* The above example is effectively identical to the previous
* It means, add ``1`` to ``a`` and put the newly calculated value back into ``a``


.. admonition:: Activity
    :class: activity

    Start with ``a = 5``.

    #. Figure out what ``a += 2`` does.
    #. See what happens when you use ``a *= 2``.
    #. Try other operators to see what works.


While loops
===========

* So far, if we need to run the same code multiple times, we repeat the code as many times as we need

    * For example, if I wanted to ``print("Hello, world!")`` five times, I need to write that print statement 5 times

* The trouble with this is

    * It's tedious
    * It doesn't scale well
    * It's prone to errors
    * It will not work for some variable number of times

        * For example, what if I want to print ``n`` times where ``n`` is some parameter to a function

* This is where the ``while`` statement comes in
* It will repeat some code ``while`` some condition is ``True``

    * ``while some_condition:``
    * The indented code will run while the condition is ``True``

.. code-block:: python
    :linenos:

    counter = 0
    while counter < 10:
        print(counter)
        counter += 1


* The above example will print out the numbers ``0`` -- ``9``

    * We initialized a ``counter`` variable outside the loop
    * Before each iteration, Python checks the ``while`` condition
    * If the condition is ``True``, the indented code runs

        * ``print`` out the value of ``counter``
        * Increment ``counter``
        * Repeat the loop until the condition is ``False``


.. warning::

    Off-by-one errors are very common when writing loops. For example, be careful about whether your stopping condition
    should *include* the final value or stop *before* it.

    Starting with ``counter = 0``:

    * ``while counter < 10:`` prints ``0`` through ``9``

        * Runs 10 times

    * ``while counter <= 10:`` prints ``0`` through ``10``

        * Runs 11 times


.. admonition:: Activity
    :class: activity

    What would happen if ``counter += 1`` was not included in the loop? Try to answer based on what you know. Confirm
    what happens by trying to run the code.

    To stop the infinite loop, select the stop button in Colab.

    A loop usually needs something inside to change, otherwise the condition may never become ``False``.


.. raw:: html

    <iframe width="560" height="315" src="https://www.youtube.com/embed/I3wMZ5jkiyc" frameborder="0" allowfullscreen></iframe>


Tracing Through A Function By Hand
----------------------------------

* Trace through the below code by hand for a few values of ``n``
* See if you can figure out what this function is doing

    * Note that ``n -= 1`` is short hand for ``n = n - 1``

.. code-block:: python
    :linenos:

    def trace_through_me_by_hand(n: int) -> int:
        result = 1
        while n > 1:
            result = result * n
            n -= 1
        return result


* ``while`` loops can get complex quickly

    * Comments here would have helped make the intent clearer

* When tracing through the code, don't try to do it all in your head
* Create a table to keep track of the values
* Below is an example with ``trace_through_me_by_hand(4)``

+------------------------+---------------+
|          n             | result        |
+========================+===============+
|          4             | 1 -> 4        |
+------------------------+---------------+
|          3             | 4 -> 12       |
+------------------------+---------------+
|          2             | 12 -> 24      |
+------------------------+---------------+
|          1             | Stop          |
+------------------------+---------------+


.. admonition:: Activity
    :class: activity

    Write a function called ``int_sum(n)`` that takes a single integer ``n`` as a parameter and returns the sum of all
    the numbers between ``0`` and ``n`` inclusively (include ``n`` in the summation).

    When you finish writing the function, do not run it right away --- trace through the program by hand like with the
    ``trace_through_me_by_hand`` above.

    .. raw:: html

        <iframe width="560" height="315" src="https://www.youtube.com/embed/sUNBswKrmJY" frameborder="0" allowfullscreen></iframe>


.. admonition:: Activity
    :class: activity

    Create a new function called ``int_sum_print`` that is the same as ``int_sum``, however this function should
    ``print`` out the values of all the variables each time in the loop. Ideally this should be formatted similar to the
    table created with ``trace_through_me_by_hand``, but do not worry too much about how the ``print``\s format the
    output.


Algorithm
=========

* Functions like ``trace_through_me_by_hand`` and ``int_sum`` are examples of *algorithms*
* An algorithm is a description of steps one could take to solve a given problem

    * Driving directions and cookie recipes are algorithms

* Although algorithms can be explained in a natural language like English, when programming we write our algorithms in code
* Finding an algorithm for a problem takes practice

    * You can make a career out of coming up with algorithms
    * `There are certain open problems that, if you solve, will literally get you a million dollars and plenty of fame <https://en.wikipedia.org/wiki/Millennium_Prize_Problems>`_


.. admonition:: Activity
    :class: activity

    #. Write down (in English) an algorithm for calculating the sum of all the even numbers between ``0`` and ``n``.
    #. Convert the algorithm into a Python function ``sum_even_numbers(n: int) -> int``.
    #. Write some ``assert`` tests to verify correctness.


For Next Topic
==============

* Read `Chapter 8 of the text <https://openbookproject.net/thinkcs/python/english3e/strings.html>`_