===================[ Tail Recursion ]=================== /// There are tricks for making functions tail-recursive and thus less demanding on the memory. /// They are discussed in the OnLisp book, pages 48--49. Read that chapter if you haven't yet! (defun fact (n) (cond ((eql n 0) 1) (t (* n (fact (- n 1)))))) ;; not tail-recursive: after self-call returns, (* n ..) must happen fact /// This works for in eLisp numbers up to 500. At 550 it fails due to exceeding Emacs' call stack depth: (fact 500) 122013682599111006870123878542304692625357434280319284219241358838584537315388199760\ 54964475022032818.....000000 (fact 550) Debugger entered--Lisp error: (excessive-lisp-nesting 1601) (cond ((eql n 0) 1) (t (* n (fact (- n 1))))) fact(20) (* n (fact (- n 1))) (cond ((eql n 0) 1) (t (* n (fact (- n 1))))) fact(21) ...skipped... /// From the debugger stack trace we can figure out that 529 is the largest that fits: (fact 529) 533526216060012988756025127348557303528841881219005404343449448568436062992673648778\ 23815647824928827692...000000000 //// To avoid the need for storing the "n" we can push the last multiplication by n into //// the second argument of the function: (defun fact1 (n acc) (cond ((eql n 0) acc) (t (fact1 (- n 1) (* n acc))))) fact1 (fact1 750 1) 258080348888515099592332164484462756339873138465439573430307783197416299243027155954\ 177662782377988121786330241704205895696...00000000000 ;;;; However, it fails at 800: (fact1 800 1) Debugger entered--Lisp error: (excessive-lisp-nesting 1601) (cond ((eql n 0) acc) (t (fact1 (- n 1) (* n acc)))) fact1(5 64254417611282167012053283147919030049629700151334186596950916169497570985$ (cond ((eql n 0) acc) (t (fact1 (- n 1) (* n acc)))) fact1(6 10709069601880361168675547191319838341604950025222364432825152694916261830$ (cond ((eql n 0) acc) (t (fact1 (- n 1) (* n acc)))) //// From the debugger stack trace we can figure out the last n for which it succeeds: (fact1 794 1) 29971333221090040829395683....0000 //// So Emacs LISP doesn't do the proper job of stack frame elimination for tail calls. /// However, the Steel Bank Common Lisp (SBCL) does: sergey@snowball lisp % rlwrap sbcl This is SBCL 2.5.3, an implementation of ANSI Common Lisp. More information about SBCL is available at . SBCL is free software, provided as is, with absolutely no warranty. It is mostly in the public domain; some portions are provided under BSD-style licenses. See the CREDITS and COPYING files in the distribution for more information. * (defun fact1 (n acc) (cond ((eql n 0) acc) (t (fact1 (- n 1) (* n acc))))) FACT1 * (fact1 800 1) 7710530113353860041446393977750283605955564018160102391634109940339708518270930693670907697955390330926478... * (fact1 8000 1) 5184181060480876939805819797427726985651100531936841770672361154595429475316606187556643544762678482157216...0000 * (fact1 30000 1) 275953724621938459937994216642546278398076204452933098552963503680007586885036056583297297765120425434165...0000 * (fact1 100000 1) 28242294079603478742934215780245355184774949260912248505789180865429779509010630178725517714138311636107136117373619629514749961831239180227260734090938324220055569688667840380377379444961268380147875111966906386...0000 // Let's see why this is happening: * (disassemble (function fact)) ; disassembly for FACT ; Size: 99 bytes. Origin: #xB800ADF1D0 ; FACT ; 1D0: 498B4510 MOV RAX, [R13+16] ; thread.binding-stack-pointer ; 1D4: 488945F8 MOV [RBP-8], RAX ; 1D8: 488B55F0 MOV RDX, [RBP-16] ; 1DC: 31FF XOR EDI, EDI ; <<-- make a 0 ; 1DE: 41FF942431FDFFFF CALL [R12-719] ; [#5200000FFCC8] = #B800001260 ; GENERIC-= ; <<-- call a generic "=" compare function ; 1E6: 7442 JE L1 ; <<-- if arg is 0, jump to L1 (base case) ; 1E8: 488B55F0 MOV RDX, [RBP-16] ; 1EC: BF02000000 MOV EDI, 2 ; 1F1: 41FF942409FDFFFF CALL [R12-759] ; [#5200000FFCA0] = #B8000010A0 ; GENERIC-- ; <<-- that's subtracting 1 from the argument "n" ; 1F9: 4883EC10 SUB RSP, 16 ; 1FD: B902000000 MOV ECX, 2 ; 202: 48892C24 MOV [RSP], RBP ; 206: 488BEC MOV RBP, RSP ; 209: 498B442429 MOV RAX, [R12+41] ; LISP-LINKAGE-TABLE ; 20E: FF9060060000 CALL [RAX+1632] ; FACT <<<--- recursive call to self ; 214: 480F42E3 CMOVB RSP, RBX ; 218: 488BFA MOV RDI, RDX ; 21B: 488B55F0 MOV RDX, [RBP-16] ; 21F: 41FF942411FDFFFF CALL [R12-751] ; [#5200000FFCA8] = #B800001110 ; GENERIC-* ; <<-- multiple by the argument "n" ; 227: L0: C9 LEAVE ; 228: F8 CLC ; 229: C3 RET ; 22A: L1: BA02000000 MOV EDX, 2 ; <<--- this is returning a FIXNUM "1", see above ; 22F: EBF6 JMP L0 ; 231: CC0F INT3 15 ; Invalid argument count trap NIL // Now compare with the tail-recursive form of the same function: * (defun fact1 (n acc) (if (= n 0) acc (fact1 (- n 1) (* n acc)))) FACT1 * (disassemble (function fact1)) ; disassembly for FACT1 ; Size: 102 bytes. Origin: #xB800ADF294 ; FACT1 ; 94: 498B4510 MOV RAX, [R13+16] ; thread.binding-stack-pointer ; 98: 488945F8 MOV [RBP-8], RAX ; 9C: 488B55F0 MOV RDX, [RBP-16] ; A0: 31FF XOR EDI, EDI ; A2: 41FF942431FDFFFF CALL [R12-719] ; [#5200000FFCC8] = #B800001260 ; GENERIC-= ; AA: 7507 JNE L0 ; AC: 488B55E8 MOV RDX, [RBP-24] ; B0: C9 LEAVE ; B1: F8 CLC ; B2: C3 RET ; B3: L0: 488B55F0 MOV RDX, [RBP-16] ; B7: BF02000000 MOV EDI, 2 ; BC: 41FF942409FDFFFF CALL [R12-759] ; [#5200000FFCA0] = #B8000010A0 ; GENERIC-- ; C4: 488BF2 MOV RSI, RDX ; C7: 488975E0 MOV [RBP-32], RSI ; CB: 488B55F0 MOV RDX, [RBP-16] ; CF: 488B7DE8 MOV RDI, [RBP-24] ; D3: 41FF942411FDFFFF CALL [R12-751] ; [#5200000FFCA8] = #B800001110 ; GENERIC-* ; DB: 488BFA MOV RDI, RDX ; DE: 488B75E0 MOV RSI, [RBP-32] ; E2: 488BD6 MOV RDX, RSI ; E5: B904000000 MOV ECX, 4 ; EA: FF7508 PUSH QWORD PTR [RBP+8] ; ED: 498B442429 MOV RAX, [R12+41] ; LISP-LINKAGE-TABLE ; F2: FFA0D8040000 JMP [RAX+1240] ; FACT1 <<<--- JMP, not CALL! It's a loop now. The tail call has been optimized down to a loop. ; F8: CC0F INT3 15 ; Invalid argument count trap NIL *