.. role:: python(code)
   :language: python


.. index::
    recursion
    base case
    recursive case

..
   `Factorial <ex:factorial>`_
   `Horner polynomial evaluation <ex:horner>`_
   `Laplace determinant <ex:determinant>`_
   `Permutations <ex:permutation>`_
   `Cartesian product <ex:cartesian>`_
   
.. _`sec:recursion`:

Recursion
=========


This section and the following ones develop three fundamental approaches to algorithm design:

* recursion
* divide and conquer
* dynamic programming

The emphasis is on algorithmic reasoning rather than programming syntax:

* identify recursive structures
* formulate appropriate base cases
* distinguish recursion from divide and conquer
* recognize overlapping subproblems
* define dynamic programming states
* reason about algorithmic complexity

A useful guiding principle is to ask:

1. Can the problem be expressed using smaller instances of itself?
2. Are the resulting subproblems independent?
3. Do identical subproblems occur repeatedly?

The answers often suggest the appropriate algorithmic paradigm.

Definition
----------

A recursive algorithm solves a problem by reducing it to one or more smaller 
instances of the same problem.

Every recursive algorithm requires:

* a **base case**, solved directly;
* a **recursive case**, reducing the problem size.

Correct recursive algorithms require both progress and termination.

During the descent phase, the problem is decomposed. During the return phase,
partial solutions are combined.


.. admonition:: Exercise (easy)

    The canonical problem to introduce recursion is the computation of :math:`N!`.

    1. Write the base case, the recursive case.
    2. Implement and test.

.. _`ex:factorial`:

.. collapse:: Correction

    1.

        .. math::

            \begin{cases}
            0! = 1 \\
            N! = (N-1)! \, N
            \end{cases}

    2.

        .. literalinclude:: ../../../../src/algo/recursion/recursion.py
            :pyobject: factorial
            :name: factorial
            :linenos:       
            :caption: src

        .. literalinclude:: ../../../../tests/algo/recursion/test_recursion.py
            :pyobject: test_factorial
            :name: test_factorial
            :linenos:       
            :caption: tests            

        .. literalinclude:: ../../../../tests/algo/recursion/test_recursion.py
            :pyobject: test_factorial_error
            :name: test_factorial_error
            :linenos:       
            :caption: tests   


.. admonition:: Exercise (easy)

    A method to evaluate the numerical value of a polynomial is described below. 
    A sequence contains the polynomial coefficients. 
    The coefficients are sorted in descending powers of the polynomial: 
    the first coefficient :math:`A_n` is for the highest power term :math:`x^n`. 

    .. math::

        \left( \underbrace{ \left( \underbrace{ \left( \underbrace{A_n} \right)  \cdot x + A_{n-1} } \right) \cdot x + A_{n-2}  }\cdots \right) \cdot x + A_0

    1. Write the base case, the recursive case.
    2. Implement and test.

.. _`ex:horner`:

.. collapse:: Hint

    The underbrace indicates successive return values of the function.

    The function :python:`np.polyval` does the same job as Horner's method.

.. collapse:: Correction     

    1. The sequence of coefficients is noted :math:`s`

    .. math::

        \begin{cases}
        \textrm{horner}([\emptyset], x) = 0  \\
        \textrm{horner}(s_{\textrm{without last}} ,x) \cdot x + s_{\textrm{last}}
        \end{cases}       


    2. Two possible implementations:

      

    .. literalinclude:: ../../../../src/algo/recursion/recursion.py
        :pyobject: horner
        :name: horner
        :linenos:       
        :caption: src

    .. literalinclude:: ../../../../tests/algo/recursion/test_recursion.py
        :pyobject: test_horner
        :name: test_horner
        :linenos:       
        :caption: tests          

    .. literalinclude:: ../../../../src/algo/recursion/recursion.py
        :pyobject: horner_no_copy
        :name: horner_no_copy
        :linenos:       
        :caption: src

    .. literalinclude:: ../../../../tests/algo/recursion/test_recursion.py
        :pyobject: test_horner_no_copy
        :name: test_horner_no_copy
        :linenos:       
        :caption: tests  


.. admonition:: Exercise (intermediate)
    
    The Laplace expansion expresses the determinant of a matrix in terms of its minors. 
    The minor :math:`M_{i,j}` is defined to be the determinant of the :math:`(n-1) \times (n-1)` matrix 
    that results from :math:`A` by removing the :math:`i` th row and the :math:`j` th column.  
    
    
    For every :math:`i`, so just choose one arbitrarily the first row, one has the equality:

    .. math::

        \det(A)=\sum _{j=1}^{n}(-1)^{i+j}a_{ij}M_{ij}

    If you do not understand this definition, take a look at this `example <https://en.wikipedia.org/wiki/Laplace_expansion>`_.

    1. Write the base case, the recursive case.
    2. Implement and test.
    3. Complexity. Assuming it takes in average 2 s to compute the determinant of a matrix of size 10. 
       How long will it take for a matrix  of size 20?

.. collapse:: Hint

    Careful, the math index notation starts at 1 whereas python indexes start at 0.

    The function :python:`np.linalg.det` computes the determinant.  

    .. figure:: det.png
        :width: 600
        :alt: Laplace expansion

        Determinant by Laplace expansion

.. _`ex:determinant`:

.. collapse:: Correction  

    1. 

    .. math::

        \begin{cases}
        \det({\textrm{scalar}}) = \textrm{scalar} \\
        \det(A) = \sum _{j=0}^{n-1}(-1)^{j}a_{0j} \det( A_{\textrm{without row 0 and column j}} )
        \end{cases}   

    2.   

    .. code-block:: python

        import numpy as np
        import numpy.typing as npt

        type Matrix = npt.NDArray      

    .. literalinclude:: ../../../../src/algo/recursion/recursion.py
        :pyobject: determinant
        :name: determinant
        :linenos:       
        :caption: src

    .. literalinclude:: ../../../../tests/algo/recursion/test_recursion.py
        :pyobject: test_determinant
        :name: test_determinant
        :linenos:       
        :caption: tests             

    3.


        Remember that:

        .. math::

            e - 1 = \sum_{i=1}^\infty \cfrac{1}{i!}

        Let's define the costly operation as the computation of :math:`(-1)^{i+j}a_{ij}` 
        times the scalar value of whatever is the results of :math:`M_{ij}`. 
        This does not include all the operations required to get this :math:`M_{ij}`. 
        Here, :math:`M_{ij}` is just seen as  a scalar. 
        This costly operation has a constant time which does not depend on the problem size. 
        The idea is now to count as function of :math:`n` the number of times this operation occurs.

        For a :math:`n\times n` matrix, the first level of recursion makes :math:`n` calls. 
        At every call, the costly operation takes place. 
        The second level of recursion makes :math:`n-1` calls *for each* case of the first level of recursion. 
        The third level makes :math:`n-2` calls per case of level :math:`n-1`, and so on.

        At the deepest level of recursion the determinant of a scalar is the scalar itself. 
        It terminates the chain of recursion. 
        At this bottom level, :math:`M_{ij}` is truly a scalar (the determinant of a scalar is himself).

        So, all things considered, you can just count the number of costly operations: 

        .. math::

            \mathcal{n} &= n + n(n-1) + n(n-1)(n-2) + \cdots + n(n-1)\cdots4\times3 + n! \\
            &= n! \underbrace{\left(\cfrac{1}{(n-1)!} + \cfrac{1}{(n-2)!} + \cfrac{1}{(n-3)!} + \cdots + \cfrac{1}{2} + 1\right)}_{ \textrm{asymptotically } e - 1}


        It leads to a number of costly operations proportional to :math:`n!`. 
        This would lead to a catastrophic explosion of computing time for larger and larger matrices.

        .. math::
            
            2\textrm{s} \times \cfrac{20!}{10!}\approx 40\,000 \textrm{years}


.. admonition:: Exercise (intermediate)
    
    Obtain all possible permutations of a sequence. 

    1. Write the base case, the recursive case.
    2. Implement and test.

.. _`ex:permutation`:

.. collapse:: Hint

    The recursive case needs some thinking. Our :python:`permutate` function is expected to return
    every permutation of a given sequence. 
    Thus, this function is able to return every permutation of the sequence *without* its last element. 
    Assuming that your function works, and that you have at your disposal all the permutations of 
    the sequence without its last element, 
    how can you produce all the permutations possible *with* the last element?


.. collapse:: Correction       

    1. The answer to the question in the hint above is: you just have to insert this element at every 
       location possible, for every permutated sequence without the last element:

       * initial sequence [1, 2, 3]
       * all permutations without last elt [[1, 2]; [2, 1]]
       * all sequences produced by inserted 3 at every location 
         [[**3**, 1, 2], [1, **3**, 2], [1, 2, **3**]; [**3**, 2, 1], [2, **3**,1], [2, 1, **3**]]

       The base case is obvious, for a empty sequence or a singleton, there is a single "permutation": the original sequence.

    2. 
   
    .. literalinclude:: ../../../../src/algo/recursion/recursion.py
        :pyobject: permutate
        :name: permutate
        :linenos:       
        :caption: src

    .. literalinclude:: ../../../../tests/algo/recursion/test_recursion.py
        :pyobject: test_permutate
        :name: test_permutate
        :linenos:       
        :caption: tests   

.. admonition:: Exercise (intermediate)
    
    Create a generator  of the cartesian product of a sequence of iterables.  Test it.

.. _`ex:cartesian`:

.. collapse:: Correction

    .. literalinclude:: ../../../../src/algo/recursion/recursion.py
        :pyobject: cartesian_product
        :name: cartesian_product
        :linenos:       
        :caption: src

    .. literalinclude:: ../../../../tests/algo/recursion/test_recursion.py
        :pyobject: test_cartesian_product
        :name: test_cartesian_product
        :linenos:       
        :caption: tests