Revisiting recursion with Lisp

As a newbie programmer, recursion took some time getting used to and once something worked, it usually appeared like magic. So, when working on an evening Lisp project, nostalgia kicked in and encouraged a little bit of exploration!

Let's consider a program that computes that the nth-power of a number. I usually tend to think in C (just like my thought process is mostly in my mother tongue which is not English) and looks as simple as:

int nth-power(int number, int n)
{
    if (n == 1)
        return number;
    else
        return number * nth-power(number, n - 1);
}

The Lisp (elisp) version is easy enough and almost identical:

(defun nth-power (number n)
   (let* ((result number))
   (if (eq n 1)
        number
        (setq result (* result (nth-power number (-n 1)))))
        result))

This works for small numbers but let's try a large number:

(nth-power 200 10000)
Debugger entered--Lisp error: (error "Lisp nesting exceeds `max-lisp-eval-depth`")
...

Ok, elisp gives up but what about SBCL:

(nth-power 200 10000)
(SB-KERNEL::CONTROL-STACK-EXHAUSTED-ERROR)

However, if we slightly modify the program to look like this:

(defun nth-power (number n acc)
   (let ((result (* number acc)))
     (if (eq n 1)
          result
     (nth-power number (- n 1) result))))

The result is:

Some huge number

The point is there's no more stack overflow. How so ?

Notice how the recursive call is the last statement in the above definition. That enables the compiler to do a Tail call-optimization. In simple terms, it means that the stack from the previous call can be reused and won't grow over time.

A disassembly makes it clearer. With the first example program, we have:

0] (disassemble 'nth-power)
; disassembly for NTH-POWER
					; Size: 130 bytes. Origin: <a href="https://th.oughts.org/tag:x1001F8EBC9" class="hashtag"><span>#</span><span class="p-category">x1001F8EBC9</span></a>
...
; C18:       488B0559FFFFFF   MOV RAX, [RIP-167]              ; #<SB-KERNEL:FDEFN NTH-POWER>
; C1F:       B904000000       MOV ECX, 4
; C24:       48892B           MOV [RBX], RBP
; C27:       488BEB           MOV RBP, RBX
; C2A:       FF5009           CALL QWORD PTR [RAX+9]
; C2D:       480F42E3         CMOVB RSP, RBX
; C31:       488B75E0         MOV RSI, [RBP-32]
; C35:       488BFA           MOV RDI, RDX
; C38:       488BD6           MOV RDX, RSI
; C3B:       41BB80030020     MOV R11D, 536871808             ; GENERIC-*
; C41:       41FFD3           CALL R11
; C44:       488BF2           MOV RSI, RDX
; C47:       EB98             JMP L0
; C49:       CC10             BREAK 16                        ; Invalid argument count trap

Notice how recursion is implemented with the call instruction on line C2A. This signifies switching to a new stack frame. In contrast, with our modified nth-power program, we have:

0] (disassemble 'nth-power)

; disassembly for NTH-POWER
; Size: 105 bytes. Origin: <a href="https://th.oughts.org/tag:x1001E67663" class="hashtag"><span>#</span><span class="p-category">x1001E67663</span></a>
...
; 98: L0:   488B55E8         MOV RDX, [RBP-24]
; 9C:       BF02000000       MOV EDI, 2
; A1:       41BB10030020     MOV R11D, 536871696              ; GENERIC--
; A7:       41FFD3           CALL R11
; AA:       488BFA           MOV RDI, RDX
; AD:       488B5DD8         MOV RBX, [RBP-40]
; B1:       488B55F0         MOV RDX, [RBP-16]
; B5:       488BF3           MOV RSI, RBX
; B8:       488B0549FFFFFF   MOV RAX, [RIP-183]               ; #<SB-KERNEL:FDEFN NTH-POWER>
; BF:       B906000000       MOV ECX, 6
; C4:       FF7508           PUSH QWORD PTR [RBP+8]
; C7:       FF6009           JMP QWORD PTR [RAX+9]
; CA:       CC10             BREAK 16                         ; Invalid argument count trap

The call instruction has been replaced with a jmp on line C7. This signifies that the stack size won't grow as was the case with the call instruction.

Note that, when using optimization with gcc, it will always try to optimize tail calls. It's easy to experiment with the optimization switches(-O0 -O1 -O2) and check the generated assembly code.

#lisp #programming