git.iko.soy/urbit.org
on 52dc85e help sign in
urbit.org/tutorials/hoon/recursion.md
195 lines 7.6 kB history raw
1+++
2title = "1.4.1 Walkthrough: Recursion"
3weight = 7
4template = "doc.html"
5aliases = ["/docs/learn/hoon/hoon-tutorial/recursion/"]
6+++
8[Recursion](.) is a common pattern for solving certain problems in most programming
9languages, and Hoon is no exception. One of the classically recursive problems
10is that of factorial. The factorial of _n_ is the product of all positive
11integers less than or equal to _n_. Thus the factorial of 5, denoted as _5!_,
12would be:
14```
155 * 4 * 3 * 2 * 1 = 120
16```
18### Factorial In Hoon
20Let's implement a factorial calculator in Hoon. To do so, we'll write a
21recursive `gate` (Hoon's equivalent of a function) to perform the relevant
22computation. Save the code below as `factorial.hoon` in your ship's `/gen`
23directory.
25```hoon
26|= n=@ud
27?: =(n 1)
28 1
29(mul n $(n (dec n)))
30```
32Our `gate` takes one sample (argument) `n` that must nest inside `@ud`, the
33unsigned-integer type.
35Next we check to see if `n` is `1`. If so, the result is just `1`, since
36`1 * 1 = 1`.
38If, however, `n` is _not_ `1`, then we branch to the final line of the code,
39`(mul n $(n (dec n)))`, where the recursion logic lives. Here, we multiply `n`
40by the recursion of `n` minus `1`. `$` initiates recursion: it calls the [gate](/docs/glossary/gate/)
41that we're already in, but replaces its sample.
43In our example, we multiply `n` with the product of this _entire gate
44all over again_ with `$(n (dec n))`, except when that new gate has its sample
45decremented by one. This works recursively because each new gate will, of
46course, itself contain the code to call a further-decremented gate. Gates will
47continue to call new, further-decremented gates until `n` is `1`, and that `1`
48will be the final number to be multiplied by.
50Let's run the program in the Dojo:
52```
53> +factorial 5
54120
55```
57It may help to visualize the operation of our example gate. The pseudo-Hoon below
58illustrates what happens when we use it to find the factorial of 5:
60```
61(factorial 5)
62(mul 5 (factorial 4))
63(mul 5 (mul 4 (factorial 3)))
64(mul 5 (mul 4 (mul 3 (factorial 2))))
65(mul 5 (mul 4 (mul 3 (mul 2 (factorial 1)))))
66(mul 5 (mul 4 (mul 3 (mul 2 1))))
67(mul 5 (mul 4 (mul 3 2)))
68(mul 5 (mul 4 6))
69(mul 5 24)
70120
71```
73It's easy to see how we're "floating" gate calls until we reach the final
74iteration of such calls that only produces a value. The `mul n` component of the
75gate leaves something like `mul 5`, waiting for the final series of terms
76to be operated upon. The `$(n (dec n))` component is what expands out the
77expression, as illustrated by `(factorial 4)`. Once the expression cannot be
78expanded out further, the operations work backwards, successively feeding values
79into the `mul` functions behind them.
81#### Tail-Call Optimization
83Our last example isn't a very efficient use of computing resources. The
84pyramid-shaped illustration approximates what's happening on the **call stack**, a
85memory structure that tracks the instructions of the program. In our example
86code, every time a parent gate calls another gate, the gate being called is
87"pushed" to the top of the stack in the form of a frame. This process continues
88until a value is produced instead of a function, completing the stack.
90```
91 Push order Pop order
92(fifth frame) ^ |
93(fourth frame) | |
94(third frame) | |
95(second frame) | |
96(first frame) | V
97```
99Once this stack of frames is completed, frames "pop" off the stack starting at
100the top. When a frame is popped, it executes the contained gate and passes
101produced data to the frame below it. This process continues until the stack
102is empty, giving us the gate's output.
104When a program's final expression uses the stack in this way, it's considered to
105be **not tail-recursive**. This usually happens when the last line of executable
106code calls more than one gate, our example code's `(mul n $(n (dec n)))` being
107such a case. That's because such an expression needs to hold each iteration of
108`$(n (dec n)` in memory so that it can know what to run against the `mul`
109function every time.
111To reiterate: if you have to manipulate the result of a recursion as the last
112expression of your gate, as we did in our example, the function is not
113tail-recursive, and therefore not very efficient with memory. A problem arises
114when we try to recurse more times than we have space on the stack. This will
115result in our computation failing and producing a stack overflow. If we tried
116to find the factorial of `5.000.000`, for example, we would almost certainly
117run out of stack space.
119But the Hoon compiler, like most compilers, is smart enough to notice when the
120last statement of a parent can reuse the same frame instead of needing to
121add new ones onto the stack. If we write our code properly, we can use a single
122frame that simply has its values replaced with each recursion.
124#### A Tail-Recursive Gate
126With a bit of refactoring, we can write a version of our factorial gate that
127_is_ tail-recursive and can take advantage of this feature:
129```hoon
130|= n=@ud
131=/ t=@ud 1
132|-
133?: =(n 1)
134 t
135$(n (dec n), t (mul t n))
136```
138The above code should look familiar. We are still building a gate that
139takes one argument `n`. This time, however, we are also putting a face on a
140`@ud` and setting its initial value to 1. The `|-` here is used to create a new
141gate with one [arm](/docs/glossary/arm/) `$` and immediately call it. Think of `|-` as the recursion
142point.
144We then evaluate `n` to see if it is 1. If it is, we return the value of `t`.
145In case that `n` is anything other than 1, we perform our recursion:
147```hoon
148$(n (dec n), t (mul t n))
149```
151All we are doing here is recursing our new gate and modifying the values of `n`
152and `t`. `t` is used as an accumulator variable that we use to keep a running
153total for the factorial computation.
155Let's use pseudo-Hoon to illustrate how the stack is working in this example for
156the factorial of 5.
158```
159(factorial 5)
160(|- 5 1)
161(|- 4 5)
162(|- 3 20)
163(|- 2 60)
164(|- 1 120)
165120
166```
168We simply multiply `t` and `n` to produce the new value of `t`, and then
169decrement `n` before repeating. Since this `$` call is the final and solitary
170thing that is run in the default case and since we are doing all computation
171before the call, this version is properly tail-recursive. We don't need to do
172anything to the result of the recursion except recurse it again. That means that
173each iteration can be replaced instead of held in memory.
175#### A Note on `$`
177`$` (pronounced "buc") is, in its use with recursion, a reference to the gate that we are inside
178of. That's because a gate is just a [core](/docs/glossary/core/) with a single arm named `$`. The
179subject is searched depth-first, head before tail, with faces skipped, and
180stopping on the first result. In other words, the first match found in the head
181will be returned. If you wished to refer to the outer `$` in this context, the
182idiomatic way would be to use [`^$`](@/docs/reference/hoon-expressions/rune/ket.md). The `^` operator
183skips the first match of a name.
185### Exercises
1871. Write a recursive gate that produces the first _n_
188[Fibonacci numbers](https://en.wikipedia.org/wiki/Fibonacci_number)
1902. Write a recursive gate that produces a list of moves to solve the
191[Tower of Hanoi problem](https://en.wikipedia.org/wiki/Tower_of_Hanoi).
192Disks are stacked on a pole by decreasing order of size. Move all of the
193disks from one pole to another with a third pole as a spare, moving one
194disc at a time, without putting a larger disk on top of a smaller disk.