: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
#+description: A description of recursive hierarchies in everything.
* 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 my own programming language, [[https://ret2pop.nullring.xyz/blog/stem.html][Stem]] (warning: link takes you outside of mindmap).
Again, stem is a prerequisite as it is the standard programming language in the mindmap.
* [[id:a6bc601a-7910-44bb-afd5-dffa5bc869b1][Mathematics]] Describes Recursion
For this example, I will be using the [[id:aed6b5dc-c2ec-4e8c-b793-538cd5d6e355][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 [[id:b1f9aa55-5f1e-4865-8118-43e5e5dc7752][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 [[id:b1f9aa55-5f1e-4865-8118-43e5e5dc7752][function]] at $x = 3$.
\begin{align*}
f(3) = 3f(3 - 1) = 3f(2) \\
f(2) = 2f(1) \\
f(1) = 1f(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) = 1f(0) = 1 \times 1 = 1 \\
f(2) = 2f(1) = 2 \times 1 = 2 \\
f(3) = 3f(2) = 3 \times 2 = 6
\end{align*}
and so the result is multiplying $3 \times 2 \times 1 \times 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
In emacs-lisp, a factorial implementation may look like the following:
* Self Reference Problems
A big part of [[id:654280d8-82e8-4a0e-a914-bd32181c101b][infinite]] [[id:8f265f93-e5fd-4150-a845-a60ab7063164][recursion]] has to do with self reference problems. For instance, Russel's paradox with respect to
set theory: does a set that contains all sets that do not contain themselves contain itself?

Such a set would contain itself if and only if it didn't contain itself. This apparent contradiction in set theory is an
example of using recursion to reach self reference paradoxes. There are more examples, such as Godel's theorems and
Turing's computability theorem.