Numberphile recently posted a video about an interesting recursive function called “Fly Straight, Dammit!” which, when plotted, initially seems chaotic, but after six hundred thirty eight iterations, instantly stabilizes.

This sounds like a perfect opportunity to flex our J muscles and plot this function ourselves!

## An Imperative Solution

The simplest approach to plotting our “Fly Straight, Dammit!” graph using the J programming language is to approach things imperatively:

```
a =: monad define
if. y < 2 do.
1
else.
py =. a y - 1
gcd =. y +. py
if. 1 = gcd do.
1 + y + py
else.
py % gcd
end.
end.
)
```

We’ve defined our `a`

monadic verb to return `1`

if we pass in a “base case” value of `0`

or `1`

. Otherwise, we recursively execute `a`

on `y - 1`

to get our `py`

, or “previous `y`

”. Next, we check if the `gcd`

of `y`

and `py`

equals `1`

. If it does, we return `1 + y + py`

. Otherwise, we return `py`

divided by `gcd`

.

This kind of solution shouldn’t look too foreign to anyone.

Let’s plot values of `a`

to verify our solution:

```
require 'plot'
'type dot' plot a"0 i. 1000
```

This works, but it’s very slow. We know that our recursive calls are doing a lot of duplicated work. If we could memoize the results of our calls to `a`

, we could save quite a bit of time. Thankfully, memoizing a verb in J is as simple as adding `M.`

to the verb’s declaration:

```
a =: monad define M.
...
)
```

Now our imperative solution is much faster.

## Using Forks and Hooks

While our initial solution works and is fast, it’s not taking advantage of what makes J a unique and interesting language. Let’s try to change that.

The meat of our solution is computing values in two cases. In the case when `y`

and `py`

have a greatest common divisor equal to `1`

, we’re computing `1`

plus `y`

plus `py`

. Our imperative, right to left implementation of this computation looks like this:

```
1 + y + py
```

We could also write this as a “monadic noun fork” that basically reads as “`1`

plus the result of `x`

plus `y`

:

```
a_a =: 1 + +
```

Similarly, when we encounter the case where the greatest common divisor between `y`

and `py`

is greater than `1`

, we want to compute `py`

divided by that `gcd`

. This can be written as a “dyadic fork”:

```
a_b =: [ % +.
```

We can read this fork as “`x`

divided by the greatest common divisor of `x`

and `y`

.”

Now that we’ve written our two computations as tacit verbs, we can use the “agenda” verb (`@.`

) to decide which one to use based on the current situation:

```
a_a =: 1 + +
a_b =: [ % +.
a =: monad define M.
if. y < 2 do.
1
else.
py =. a y - 1
has_gcd =. 1 = y +. py
py (a_b ` a_a @. has_gcd) y
end.
)
```

If `has_gcd`

is `0`

, or “false”, we’ll return the result of `py a_b y`

. Otherwise, if `has_gcd`

is `1`

, we’ll return the result of `py a_a y`

.

## More Agenda

We can elaborate on the idea of using agenda to conditionally pick the verb we want to apply to help simplify out base case check.

```
<p>I find myself producing lots of ranging content from books and articles, like the one you're reading now, to open source software projects. If you like what I'm doing, <strong>nothing shows your support more than signing up for <a href="#newsletter">my mailing list</a></strong>.</p>
```

First, let’s define our base case and recursive case as verbs that we can combine into a gerund. Our base case is simple. We just want to return `1`

:

```
base_case =: 1:
```

Our recursive case is just the (memoized) `else`

block from our previous example:

```
recursive_case =: monad define M.
py =. a y - 1
has_gcd =. 1 = y +. py
py (a_b ` a_a @. has_gcd) y
)
```

Our function, `a`

wants to conditionally apply either `base_case`

or `recursive_case`

, depending on whether `y`

is greater or less than one. We can write that using agenda like so:

```
a =: base_case ` recursive_case @. (1&<)
```

And because our `base_case`

verb is so simple, we can just inline it to clean things up:

```
a_a =: 1 + +
a_b =: [ % +.
recursive_case =: monad define M.
py =. a y - 1
has_gcd =. 1 = y +. py
py (a_b ` a_a @. has_gcd) y
)
a =: 1: ` recursive_case @. (1&<)
```

Using agenda to build conditionals and pseudo-“case statements” can be a powerful tool for incorporating conditionals into J programs.

## Going Further

It’s conceivable that you might want to implement a tacit version of our `recursive_case`

. Unfortunately, my J-fu isn’t strong enough to tackle that and come up with a sane solution.

That said, Raul Miller came up with a one-line solution (on his phone) and posted it on Twitter. Raul’s J-fu is strong.

Posted on by:

## Discussion