Algorithms
==========

Linear Search
-------------

- Get index
- Find object (based on some attribute)
- Get list of elements or object (based on some attribute)
- Remove elements from a list

The goal is to search a collection to discover the location (index) of a particular element.

Bubble Sort
-----------


Recursion
---------
Resursion, simply put, is when a function calls *itself*.
Unfortunately getting a working recursive function is slightly more complicated than that.

Let's take this function as an example::

    def count_from(n):
        print(n)
        count_from(n + 1)
    

    count_from(1)

Is the ``count_from`` function recursive? Yes! It is a function that calls itself. The down-side is it never *stops* calling itself.
In Python you end up getting a ``RecursionError`` after :ref:`algorithms:the call-stack` gets too large. In Java, this is called a ``StackOverflow`` error (sound `familiar <https://stackoverflow.com>`_?).

The Base Case
^^^^^^^^^^^^^
What is the absolute limit? The last possible value for ``n``
where we know the answer and we can simply return it?

The Recursive Step
^^^^^^^^^^^^^^^^^^
Take care of the smallest part and offload the rest of the answer
to "someone else".

.. code-block:: text

    factorial(5)
    -----
    5 x | (4 x 3 x 2 x 1)
    -----

    return 5 * factorial(4)

    return n * factorial(n - 1)


    bunny_ears(4)
    ----|
    2 + |  (2 + 2 + 2)
    ----|


    bunny_ears_2(5)

    bunny # 5     4   3   2   1
           ----|
    math    2 +| (3 + 2 + 3 + 2)
           ----|

The Call-Stack
^^^^^^^^^^^^^^
Understanding the call stack is vital to be able to trace and analyze recursive functions.

At the base of the call-stack, we have the "main" program or as shown in the image below, the "global frame".

Everytime a function gets executed, it is thrown to the top of the call stack.

.. code-block:: python

    def wake_up():
        print("waking up")
    
  
    wake_up()



When the function is completed, it gets removed. 

If you call functions within functions, the stack gets larger and larger.

.. warning:: Under construction.


Topics by Category::

    - Searching
      - Linear
      - Binary
    - Sorting
      - Pigeonhole
      - Bubble
      - Binary (in-sort)
      - Merge-sort
    - Recursion
      - Primary concept
      - Recursive step
      - Base case
    - Time/memory complexity
      - Big-O notation

Topics by Timeline::

  - Recursion (every day)
  - Time complexity (throughout)
  - Linear Search
  - Linear filtering
  - Pigeonhole sort
  - Bubble Sort
  - Binary Search
  - Binary in-sort
  - Merge-sort

Other (advanced) topics (that may not be covered)::

  - Memoization
  - Traversing trees
    - Breadth-first search
    - Depth-first search