add content to journal and mindmap

1 files changed, 76 insertions, 13 deletions

diff --git a/mindmap/recursion.org b/mindmap/recursion.org
index bf42261..f500fb3 100644
--- a/mindmap/recursion.org
+++ b/mindmap/recursion.org
@@ -19,18 +19,40 @@ Yeah, but I think it's a good introduction to the subject. You can think of recu
 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]].
-* Mathematics Describes Recursion
+* [[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) \\
+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:
+    if x < 0:
+        return None
+    elif x == 0:
         return 1
     return x * factorial(x - 1)
 return factorial(5)
@@ -38,12 +60,17 @@ return factorial(5)
 
 #+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:
+    if x < 0:
+        return None
+    elif x == 0:
         print(1)
         return 1
     n = x * factorial(x - 1)
@@ -60,12 +87,48 @@ factorial(5)
 : 24
 : 120
 
-what is happening here? Why is it printing in the reverse order? Well, it is because we are calling
-the factorial function from within itself /before/ we print out the return value, which then
-keeps on happening for each iteration until it reaches the "base case" (the case in which x <= 0).
+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…?
 
-You can model this behavior with a [[id:52d255d2-114c-42f4-b362-f0b4a2f7b83d][stack]], which is why it is called a stack frame. Think about each
-iteration as getting put on the top of the stack waiting to be printed, until the base case is evaluated
-and printed all in one step.
-* Recursion is not Recursion
-* Recursion is [[id:1b1a8cff-1d20-4689-8466-ea88411007d7][duality]]?
+* TODO Recursion is not Recursive
+There are some things
+* TODO Recursion = [[id:1b1a8cff-1d20-4689-8466-ea88411007d7][duality]]?