Yesterday I posted a macro recording and asked if you could guess what it would do when played back.

Today, we find out the answer!

A Really Recursive Macro: Fibonacci

It’s a macro that will calculate the Nth member of the Fibonacci Sequence for the number under the cursor¹.

Implementing it required overcoming several challenges, so I wrote a sort of Literate Programming inspired explanation of how it works. I recommend downloading it and opening it in Vim² so you can try out the macro, but if you’re a hands-off kinda gal, then you can also read a webified version below.

 ___   ____  __    _     ___   __   _   _      ____
| |_) | |_  / /`  | | | | |_) ( (` | | \ \  / | |_
|_| \ |_|__ \_\_, \_\_/ |_| \ _)_) |_|  \_\/  |_|__
 _       __    __    ___   ___
| |\/|  / /\  / /`  | |_) / / \
|_|  | /_/--\ \_\_, |_| \ \_\_/
 ____  _   ___   ___   _       __    __    __    _
| |_  | | | |_) / / \ | |\ |  / /\  / /`  / /`  | |
|_|   |_| |_|_) \_\_/ |_| \| /_/--\ \_\_, \_\_, |_|

When sourced, this Vimscript file constructs a macro in the "qregister that will calculate the Nth value in the Fibonacci sequence for the number under the cursor when the macro is invoked.

:so %

Introduction

One of my favourite features in Vim is macro recording. I love how the incredibly simple mechanism of letting you record keystrokes converts the standard normal mode commands into a RIDICULOUSLY powerful automation tool.

Any macro recording ENTHUSIAST will soon discover a neat little trick: the RECURSIVE MACRO. By making the last step of a macro be the invoking of itself, you can run the macro tens or thousands of times with a single @command, performing MASSIVE numbers of laborious edits almost instantly.

After using these for a while it occurred to me that really what this gets used for isn’t a recursive process at all. It’s just an iterative loop. Syntactically it’s recursion, but semantically it’s 10 PRINT VIM FTW 20 GOTO 10. And then I got to thinking, can you implement a more traditionally recursive algorithm in a macro recording?

And what is the classic Introduction-to-Recursion algorithm that you’ll find in any CompSci 101 course? Okay yeah it’s the factorial function, but what’s the one I thought of first when deciding to do this?

La Fibonacci!

The Fibonacci Algorithm

The Fibonacci sequence is a series of numbers where each value is calculated by adding the previous two numbers together:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

If you google ‘recursive fibonacci’ and look at the top few results, you’re likely to find an algorithm that looks something like this:

function fib(N) {
    switch (N) {
        case 0: return 0
        case 1: return 1
        default: return fib(N - 1) + fib(N - 2)
    }
}

UNfortunately, it’s IMPOSSIBLE to translate this directly into a recursive macro, because the only way we have of ending the macro ‘function’ is to cause an ’error’, and as soon as we do this, ALL computation stops. There is no way of returning the value from e.g. the call to fib(N - 1) and then adding something to this value. Weak.

FORtunately, COMPUTER SCIENCE has a solution to this. Instead of using the algorithm above, we can use a ’tail-recursive’ algorithm. This is one where the recursive call is at the end of the function. i.e. No computation takes place after the recursive call.

Using MATHS, it’s actually possible to translate ANY recursive algorithm into a tail-recusive one. Astounding!

But I just barely scraped through my Computer Science degree, so here’s an example of a tail recursive fibonacci function that I copied off the internet:

function _fib(N, left, right) {
    switch (N) {
        case 0: return 0
        case 1: return right
        default: return _fib(N - 1, right, left + right)
    }
}

function fib(N) {
    return _fib(N, 0, 1)
}

Basic Method

What do we need to implement this algorithm as a recursive macro?

Our basic approach is going to be to build little bits of functionality from normal mode keystrokes, which we are going to store in the alphabetical registers and invoke via the standard macro run command:@. Each register essentially contains a tiny function that you can call with @.

Next, we need to handle that switch statement. The trick here is to write the keystrokes required to perform each case as a single line in the buffer. If we place these lines in order at and above the cursor, then we can move to the line corresponding to the value of N passed in by moving upwards withkthe required number of times. Once we’re on the correct case line, we can yank the line’s contents and then execute the code by running the yank register as a macro. Sneaky!

Finally, we need some method of addition and subtraction. Vim’s normal mode provides this via theCTRL-AandCTRL-Xkeystrokes.

The RULES of the Game

In order to prevent this from being an EVEN MORE pointless endeavour than SOME would claim it already is, when I started working on it I decided to disallow certain Vim features:

Reasonable Restrictions

• No Ex commands,

• No expression register,

• No Vimscript functions,

The above would make this task EASY and therefore BORING. So: no programmatic scaffolding, and other than the aforementioned increment/decrement number commands, nothing that facilitates ARITHMETIC.

• Must work regardless of position of number in file (so long as it is a standard Vim word).

This one, on the other hand, is really just a matter of panache.

Unreasonable Ones. Why Did I Impose These on Myself?

• No searches,

• No setting or jumping to marks,

• No storing state in registers: only macros!

• Avoid CLUTTERING up the buffer with state: only do it when absolutely necessary and leave it there for the shortest time possible,

• Other than the fib and _fib functions, no storing macros in alphabetical registers.

  It’s actually possible to encapsulate the entire algorithm within just TWO macros (Type622Gto see this version.) But for EDUCATIONAL PURPOSES only, when constructing the macro in this file, I’ve used alphabetical registers to break down the computation into smaller pieces. This is purely to make it easier to to understand, though. During the running of the macro, no further alphabetical registers may be used for storing macros (or anything else!)

There’s not really a good argument for why any of the above shouldn’t be allowed. They just made me feel FANCY.

Implementation

Let’s build this thing!

Because I am a Vimscript file and not a person typing at a keyboard, I can’t record the macro with theqcommand, so we’re going to build it by directly setting the register contents with:letcommands.

"\<Esc>"

"\<C-A>"

Fibonacci Function

Let’s start with our fib function! We are going to store this in the "qregister, because that is the register I most often use for my macro recordings.

:let @q = "@p@fIFibonacci: \<Esc>"

What steps does this macro take?

@p

play back macro "p

@f

play back macro "f

IFibonacci: \<Esc>

insert the label ‘Fibonacci: ’ at the start of the line, and then exit insert mode.

Okay, so what does the macro in register"pdo?

Preamble

:let @p = "yiwo\<Esc>pA 0 1\<Esc>2b"

yiw

yank the number under the cursor

o\<Esc>

add a new line below the cursor

p

put the number you yanked at the start of the line and then

A 0 1

append the text ‘ 0 1’

<Esc>

leave insert mode, and then

2b

move back two words to place the cursor back on the first number.

ASTUTE readers will have noticed that the new line now contains the contents: ‘[N] 0 1’ which looks SUSPICIOUSLY similar to the arguments we want to pass into the _fib function. COINCIDENCE? Read on to find out!

So, the"pstands for ‘preamble’. What do you think the"fmight stand for?

_fib Function

"fstands for ‘underscore-fib’!

:let @f = "@c@j@s@0@d@0"

Okay, so the macro we’re storing in"fjust plays back a bunch of other, as yet undefined, macros. Lets define these:

Case-Writing Macro

"cis for case!

First we are going to add three more lines to the buffer, above the current cursor position, each containing one of the cases from the switch block in the fib() function.

:let @c = "@z@o@n3+"

@z

play back "z

@o

play back "o

@n

play back "n

3+

move down three lines, placing the cursor on the first non-blank character.

YAY More macros! Let’s continue.

Zero case

"zstands for ‘zero’!

:let @z = "Occ0\<C-V>\<Esc>\<Esc>"

Okay, finally we are actually doing something instead of just calling more and more macros:

O

create a new line and insert

cc0

‘cc0’

\<C-V>\<Esc>

in insert mode,CTRL-Vtells Vim that the next character should be inserted literally, so this will insert an ESC into the buffer

\<Esc>

leave insert mode

So the"zmacro will insert a line above the cursor which contains the contentscc0followed by a literal ESC character. These, the more EAGLE-EYED of you will already have spotted, are the keystrokes required toccchange a line, enter a zero, and then exit insert mode. This is the code that writes out the result when executing our ‘zero’ case! But we’re not actually running the code here. We’re just writing it into our buffer.

One case

"ostands for ‘one’:

:let @o = "Od2w\<Esc>"

O

again, create a new line above the cursor and insert:

d2w

‘d2w’

\<Esc>

and leave insert mode

RECALL that our three parameters are simply written on the current line. To return right we just need to delete the first two numbers, which the keystrokesd2wwill achieve.

Man, writing recursive macros is EASY.

Default case

"nstands for ‘N>1’.

This one’s a teensy bit longer.

:let @n = "O\<C-V>\<C-X>g_yiwA \<C-V>\<Esc>p2ge\<C-V>\<C-A>daw@b@a\<C-V>\<C-X>0@f\<Esc>"

O

Are you noticing a pattern? Create a new line above the cursor and insert keystrokes that:

\<C-V>\<C-X>

same trick as before: we use CTRL-V to allow us to insert a CTRL-X command in the macro that will subtract one from `N`

g_

jump to the last non-blank on the line

yiw

yank the number the cursor is now on: the ‘right’ parameter

A \<C-V>\<Esc>

append a space to the end of the line and exit insert mode

p

put the copy of ‘right’ that we just yanked

2ge

jump two words backwards to place the cursor on ‘left’

\<C-V>\<C-A>

We are going to perform addition by passing ‘left’ as a count to the normal mode CTRL-A command. But 'left' might be zero, which would BREAK EVERYTHING (or at least, it would break our addition: if you pass a count of 0 to CTRL-A, it adds one instead of doing nothing), so we add one to 'left' now, also by using CTRL-A, and we'll subtract one from the result of our addition later to account for this.

daw

delete ‘left’. This operation will save the value deleted in the ‘small delete register’ "-.

@b@a

run a couple of macros to do something. We'll come back to this in a minute.

\<C-V>\<C-X>

subtract one from our updated ‘right’ to balance out the addition we did a couple of steps ago

0

move back to the start of the line

@f

recurse, recurse!

\<Esc>

Finally, we leave the insert mode that we started with the O command at the start of the "n macro.

So, ignoring @b@a for a second longer, the"nmacro writes out a line of code that, when run as a macro, will change the line the cursor is on from:

N left right

into

N-1 right right

leaving ’left’ in the small delete register“-You’ll recall that our goal is to get to:

N-1 right left+right

…so @b@a just needs to…

Perform Addition

We now have the value of ’left’ stored in the small-delete register“-. Using normal mode commands, there’s no way to add this directly to the copied value of ‘right’ at the end of the line, so the macro we’re going to store in"bdoesn’t perform the addition itself: instead it writes out normal mode commands that CAN do this into the buffer, and then it immediately yanks the commands, storing them in the yank register"0so we can execute them as a macro.

:let @b = "O\<C-R>-\<Esc>s\<C-V>\<C-A>\<Esc>0y$dd"

O

create a new line above the cursor and enter insert mode

\<C-R>-

in insert mode, CTRL-R allows you to insert the contents of a register directly into the buffer. Using it with `-` will enter the contents of the small delete register "- i.e. the last delete command that removed less than a line. In this case: the value of 'left'!

\<Esc>

leave insert mode

s

when we deleted ‘left’, we did it with the command daw, which will also have deleted the trailing space. We use s to delete this space and enter insert mode

\<C-V>\<C-A>

insert a literal CTRL-A

\<Esc>

exit insert mode

0

move to the very start of the line

y$

yank the entire contents of the line, saving it in the yank register

dd

delete the line we just added.

So when"bis run, if the small delete register contains e.g. the number 4, the yank register will be populated with a number 4, followed by a literal CTRL-A character. TheCTRL-Anormal mode ‘add’ command takes a count, so we now have a macro in"0that will add the contents of the small delete register to the number under the cursor!

To perform the addition, we just need a macro that will move to the correct position in the line, and then run the macro in the yank register:

:let @a = "g_@0"

g_

move to the last non-blank character on the line

@0

play back the macro in the yank register "0

(In case you were wondering,"astands for ‘Add’, and"bstands for ‘Build a macro that performs addition’. It’s hard to name functions when they all have one-letter names!)

Returning to"cwe can now see more clearly what it does:

@z

write out a line of code that handles our zero case

@o

write out a line of code that handles our one case

@n

write out a line of code that handles our N case

3+

Move back down to the line we started on

When run, the"cmacro writes out code for the three cases into the three lines in the buffer above the cursor: the zero case is one line up, the one case is two lines up, and the N case is three lines up.

Select Case

Let’s presume for the time being that we have the number of lines we need to move up to get to the correct case stored in the yank register"0. Then we need a macro that:

• moves up the number of lines stored in yank register,
• yanks the whole line,
• returns to the home row.

Again, like in the macro we stored in"b, we can’t setup the macro we need directly with a :let command, so instead we’re going to write an intermediate macro that writes the macro we really need into the buffer and then yank it for playback.

:let @s = "O\<C-R>0-y$\<C-R>0+\<Esc>^y$dd"

O

Begin a new line above the cursor and start insert mode.

\<C-R>0

We use CTRL-R again to insert the contents of a register into the buffer. This time we pass it 0 to access the yank register, inserting the number of lines we need to move up to get to the desired case.

-

The - command takes a count, so when the macro we're writing is run, we will move up the number of lines that we just wrote into the buffer, placing the cursor at the start of the line.

y$

yank the entire contents of the line

\<C-R>0

Write out the number in the yank register again

+

and move back down

\<Esc>

leave insert mode, and stop writing out the new macro

^

move to the start of the line

y$

yank the new macro, saving it in the yank register

dd

now we have the macro saved in the yank register, delete its code from the buffer.

Now we have the case macro we need to run stored in the yank register, we can delete the code for the cases from the buffer:

:let @d = "3k3dd"

3k

move up three lines

3dd

delete three lines

The"sstands for ‘select’. I guess it could also stand for switch. The choice is yours!

Ceiling

We now have a way to yank the code for the case we want to handle. But wait! In order to create the"smacro we need to deal with the presumption I made above: we need some way of setting the yank register to contain the correct value from 1-3 so that the ‘select case’ macro will pick the right case.

Depending on the value of N, we need to yank:

 N=0:  yank 1
 N=1:  yank 2
N>=2:  yank 3

The first two are easy. We can simply add 1 to N temporarily and yank it. For the third, we can again start by adding 1 to N, but then we’ll also need to create a ‘ceiling’ macro that caps any result higher than 3 to 3.

I’m afraid at this point I’ve run out of NIFTY mnemonic names for my macros, so I’m just going to call the macros I need to implement this"jthrough “r(skipping"n,"o, and"p, which we’ve already used.) I told you naming these was hard!

:let @j = "\<C-A>yiw@k@l@m@r@l\<C-X>"

\<C-A>

Add one to N (temporarily)

yiw

yank it

@k@l@m@r@l

waves hands around, theatrically

\<C-X>

subtract one from N again

But how are we going to implement this ceiling without the benefit of any arithmetic functions?!

pauses for dramatic effect

Well, first we’ll write out N 3s onto a line. e.g. for N=8:

33333333

Then we’ll replace the first two characters with 1 and 2:

12333333

Then we just move to the Nth character on the line and yank it! Easy-peasy macro-squeezy!

We’ll start by writing out the 3s

:let @k = "OO\<C-V>\<Esc>\<C-R>0a3\<C-V>\<Esc>\<Esc>"

O

Create a new line above the cursor to write a new macro into, and start insert mode

O

The first command of our new macro is ALSO O. Macro-ception!

\<C-V>\<Esc>

insert a literal ESC to leave insert mode in our inner-macro (but remember we're still in insert mode in the outer macro)

\<C-R>0

insert the contents of the yank register. We're going to pass this as a count to our next command:

a3

append a 3. Because of the count, this will actually append N 3s.

\<C-V>\<Esc>

insert an ESC to leave the insert mode we started with a

\<Esc>

and then actually leave insert mode!

So if we run"kwith 8 in the yank register, it will write out the following into the line above the cursor:

O<Esc>8a3<Esc>

And if we yank that and run it, it will write out a line with eight 3s on it. Next step is to do just that!

:let @l = "0y$dd@0"

0

move to the start of the line

y$

yank the entire contents of the line

dd

delete the line

@0

playback the macro we just yanked

:let @m = "2|r2^r1+yiw-"

2|

move to the 2nd character on the line by using a count of 2 with the normal mode | command

r2

replace the character under the cursor with a 2

^

move to the 1st character on the line

r1

replace that with a 1

+

move downwards to the start of the next line i.e. onto our current N value

yiw

re-yank N

-

move back up to the start of the line above

Now we are at the start of a line with the contents ‘123333…’, and we have N in the yank register.

:let @r = "O\<C-R>0|vydd\<Esc>"

O

You know the drill.

\<C-R>0

insert the contents of the yank register

|

insert a |. Combined with the N count we just inserted, this will jump to the Nth character on the line.

v

enter visual mode to select a single character

y

yank it

dd

delete the line with all the 3s on it

\<Esc>

exit insert mode

Armed with the macros above, let’s review the middle section of"j:

@k

write a macro that adds a line with N 3s on it

@l

yank it and run it to actually add the 3s-line

@m

replace the first two characters of that line with 12

@r

compose a macro that yanks the Nth character of the line and then tidies up

@l

yank that macro and run it

All done!

Now we can finally return to our _fib function in register"fand see what it does:

The completed _fib function

@c

write out three lines of code to handle the three cases and return to our home line

@j

load yank register with the correct number of lines to move up in order to get to the correct case for the current value of N

@s

write select case macro into yank register and return to home line

@0

select case, (reading its code into the yank register)

@d

delete cases

@0

run case

And that’s it!"qnow contains a macro that will calculate the Nth value in the Fibonacci sequence for the number under the cursor!

So! To try this out, type the following, now:

:so %

This will source this file, running all the :let commands above, thus setting up the macro, while ignoring all the explanation (which is formatted as comments).

Recording It

“But wait!” I hear you say, “This is a bunch of :let commands! That doesn’t answer the question you originally asked! I want to know if you can really RECORD a macro that does this?

The answer is yes. To record a version of this macro, simply type out the following short sequence of keystrokes:

q       q       q       q       f       q       q       q
y       i       w       o       Esc     p       A       Space
0       Space   1       Esc     2       b       @       f
I       R       e       d       a       c       t       e
d       :       Space   Esc     q       q       f       O
c       c       0       Ctrl-V  Esc     Esc     O       d
2       w       Esc     O       Ctrl-V  Ctrl-X  g       _
y       i       w       A       Space   Ctrl-V  Esc     p
2       g       e       Ctrl-V  Ctrl-A  d       a       w
O       Ctrl-V  Ctrl-R  -       Ctrl-V  Esc     x       a
Ctrl-V  Ctrl-V  Ctrl-V  Ctrl-A  Ctrl-V  Esc     0       y
$       d       d       g        _      @       0       Ctrl-V
Ctrl-X  0       @       f       Esc     3       +       Ctrl-A
y       i       w       O       O       Ctrl-V  Esc     Ctrl-R
0       a       3       Ctrl-V  Esc     Esc     0       y
$       d       d       @       0       2       |       r
2       ^       r       1       +       y       i       w
-       O       Ctrl-R  0       |       v       y       d
d       Esc     0       y       $       d       d       @
0       Ctrl-X  O       Ctrl-R  0       -       y       $
Ctrl-R  0       +       Esc     ^       y       $       d
d       @       0       3       k       3       d       d
@       0       q

Just be sure not to make any typos. Easy!

The End

So that’s it! Hope you’ve enjoyed reading about how this macro was built. If you haven’t tried running it yet you can do so now, by entering the command:

:so %

If you liked this, why not check out my boneheaded first attempt at writing this macro or some of my other SCINTILLATING Vim content.