:PROPERTIES:
:ID:       8f265f93-e5fd-4150-a845-a60ab7063164
:END:
#+title: recursion
#+author: Preston Pan
#+html_head: <link rel="stylesheet" type="text/css" href="../style.css" />
#+html_head: <script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script>
#+html_head: <script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script>
#+startup: latexpreview
#+OPTIONS: broken-links:t
* Recursion is Recursion
Exactly as I say in the title.
** but what is recursion?
Recursion.
** No, seriously, what is it?
Self reference.
** haha, very clever, it's not like that joke has been made 10 million times
Yeah, but I think it's a good introduction to the subject. You can think of recursion
as [[id:42dbae12-827c-43c4-8dfc-a2cb1e835efa][self-assembly]] and it has deep connections to topics such as [[id:b005fb71-2a16-40f9-9bb6-29138f4719a2][emergence]]. I will first
describe it in a mathematics context, and then a programming context.
For demonstration purposes, I will use [[id:5d2e2f3b-96ac-4196-9baf-4c3d6d349c98][python]].
* [[id:a6bc601a-7910-44bb-afd5-dffa5bc869b1][Mathematics]] Describes Recursion
For this example, I will be using the factorial. One might define it like so:
\begin{align*}
f: \mathbb{N}\rightarrow\mathbb{N}\ s.t. \\
f(0) = 1 \\
f(n) = nf(n - 1)
\end{align*}
in other words, we want a function defined over [[id:2d6fb5ac-a273-4b33-949c-37380d03c076][natural numbers]] that is one when the input is zero,
and otherwise multiplies the input with a copy of itself, only the input is one less. Let's try evaluating
this function at $x = 3$.
\begin{align*}
f(3) = 3 * f(3 - 1) = 3 * f(2) \\
f(2) = 2 * f(1) \\
f(1) = 1 * f(0) \\
f(0) = 1
\end{align*}
once we substitute $f(0) = 1$ in, you will see it all collapses.
\begin{align*}
f(0) = 1 \\
f(1) = 1 * f(0) = 1 * 1 = 1 \\
f(2) = 2 * f(1) = 2 * 1 = 2 \\
f(3) = 3 * f(2) = 3 * 2 = 6
\end{align*}
and so the result is multiplying $3 * 2 * 1 * 1 = 6$. If you observe what we did, you'll see that we started
by trying to replace unknown variables by trying to evaluate $f(x)$ one number down, and eventually we reach
a "base case" -- zero. As soon as the "base case" occurs, we then "go back up" by replacing all the unknown
values with known ones -- and that's how we evaluate recursive functions.
* Programming Describes Recursion
Even if you don't understand programming, it should be clear that this represents the factorial function:
#+begin_src python :exports both
def factorial(x):
    if x < 0:
        return None
    elif x == 0:
        return 1
    return x * factorial(x - 1)
return factorial(5)
#+end_src

#+RESULTS:
: 120

And it also prints the result that we expect for the factorial of 5. Take note that just like in our mathematics
example, ~factorial~ calls itself until it reaches a base case, ~x == 0~.
** The stack frame
We are now going to modify the code to be more transparent in the sense that it is going to print
each factorial call out:
#+begin_src python :results output :exports both
def factorial(x):
    if x < 0:
        return None
    elif x == 0:
        print(1)
        return 1
    n = x * factorial(x - 1)
    print(n)
    return n
factorial(5)
#+end_src

#+RESULTS:
: 1
: 1
: 2
: 6
: 24
: 120

what is happening here? Why is it printing in the reverse order? Well, it is the /exact same phenomenon/
as the "going back up" procedure we did before!

You can model this behavior with a [[id:52d255d2-114c-42f4-b362-f0b4a2f7b83d][stack]], which is why it is called a stack frame. What's interesting is that
the "going down until you reach the bottom and then building back up" procedure we did to solve $f(3)$ in the
math section is actually modeled well by a stack. Just look at the far right hand side of all our equations in
that example: we try but fail to evaluate $f(2)$, then $f(1)$, then $f(0)$. Then, we succeed in evaluating
$f(0)$, which leads to being able to evaluate $f(1)$, which leads to being able to evaluate $f(2)$. This reverse
ordering is exactly what we see by pushing a list of items onto a stack then removing them from one. Additionally,
the second equation block from that section's right hand side is identical to the first few entries we see in the
results block of this one, and you can see an exact mirroring of the first block in its evaluations of $f(n)$.

So, the "going down" procedure is the same thing as pushing values onto some sort of stack, and the "going back up"
procedure is exactly the same as popping those values off a stack!
** Computer Hardware Describes Recursion
Even though we can analogize pushing and popping off the stack to this recursion, there still isn't a clear definite
link to the two ideas in hardware. Therefore, I will do a demonstration using assembly.

To start with, we will be comparing an assembly function that takes the factorial to this one in C:
#+begin_src C :results output :exports both
#include <stdio.h>

int factorial(int x) {
    if (x < 0) return -1;
    else if (x == 0) return 1;
    return x * factorial(x - 1);
}
int main(int argc, char **argv) {
    printf("factorial of five: %d\n", factorial(5));
    return 0;
}
#+end_src

#+RESULTS:
: factorial of five: 120

Because C is a compiled language, it is easier to see what is actually happening human-wise. However,
we will need to write and analyze some assembly in order to figure out what is actually going on.

Assembly language section coming soon! We will be using NASM due to its readability.
* TODO Recursion Describes…?

* TODO Recursion is not Recursive
There are some things
* TODO Recursion = [[id:1b1a8cff-1d20-4689-8466-ea88411007d7][duality]]?