1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
: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).
* [[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 Describe Recursion
In stem, a factorial implementation might look like this:
#+begin_src stem :exports both
factorial [ dup 0 <= [ 1 + ] [ dup 1 - factorial * ] if ] def
5 factorial .
#+end_src
#+RESULTS:
: 120
and in stem, we can print out the stack every step of the way with the builtin word ~?~:
#+begin_src stem :exports both
factorial-debug [ dup 0 <= [ 1 + ] [ ? "\n" . dup 1 - factorial-debug dup . * ] if ] def
5 factorial-debug .
#+end_src
#+RESULTS:
#+begin_example
5
5
4
5
4
3
5
4
3
2
5
4
3
2
1
1
1
2
6
24
120
#+end_example
* TODO Recursion Describes…?
* TODO Recursion is not Recursive
* TODO Recursion = [[id:1b1a8cff-1d20-4689-8466-ea88411007d7][duality]]?
|
