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: #x1001F8EBC9
...
; 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: #x1001E67663
...
; 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.