Item — HN Reader

There may be a faster or cleverer way to do it but here's a basic tail recursive fibonacci:

    (defun nth-fibonacci (n &optional (a 0) (b 1))
      (if (= n 0) 
          a 
          (nth-fibonacci (- n 1) b (+ a b))))

3 comments

WEB> (time (nth-fibonacci 9999)) Evaluation took: 0.005 seconds of real time 0.004520 seconds of total run time (0.000168 user, 0.004352 system) 100.00% CPU 13,120,881 processor cycles 4,716,256 bytes consed

20793608237133498072112648988642836825087036094015903119682945866528501423455686648927456034305226515591757343297190158010624794267250973176133810179902738038231789748346235556483191431591924532394420028067810320408724414693462849062668387083308048250920654493340878733226377580847446324873797603734794648258113858631550404081017260381202919943892370942852601647398213554479081823593715429566945149312993664846779090437799284773675379284270660175134664833266377698642012106891355791141872776934080803504956794094648292880566056364718187662668970758537383352677420835574155945658542003634765324541006121012446785689171494803262408602693091211601973938229446636049901531963286159699077880427720289235539329671877182915643419079186525118678856821600897520171070499437657067342400871083908811800976259727431820539554256869460815355918458253398234382360435762759823179896116748424269545924633204614137992850814352018738480923581553988990897151469406131695614497783720743461373756218685106856826090696339815490921253714537241866911604250597353747823733268178182198509240226955826416016690084749816072843582488613184829905383150180047844353751554201573833105521980998123833253261228689824051777846588461079790807828367132384798451794011076569057522158680378961532160858387223882974380483931929541222100800313580688585002598879566463221427820448492565073106595808837401648996423563386109782045634122467872921845606409174360635618216883812562321664442822952537577492715365321134204530686742435454505103269768144370118494906390254934942358904031509877369722437053383165360388595116980245927935225901537634925654872380877183008301074569444002426436414756905094535072804764684492105680024739914490555904391369218696387092918189246157103450387050229300603241611410707453960080170928277951834763216705242485820801423866526633816082921442883095463259080471819329201710147828025221385656340207489796317663278872207607791034431700112753558813478888727503825389066823098683355695718137867882982111710796422706778536913192342733364556727928018953989153106047379741280794091639429908796650294603536651238230626 WEB>

You may want to put extra spaces in front of those lines, and also manually break up that massive number.

Yep, that's how you'd do it. So long as your CL implementation supports tail call optimization, that will be on par with the same algorithm using loop or another looping construct.

SBCL doesn't optimize tail calls by default.

If I recall you have to set the optimization level prior to compiling the function using `(declaim (optimize xxx))` - where xxx is something I've forgotten. Perhaps someone can come along and point out what xxx should be?

  ; disassembly for NTH-FIBONACCI
  ; Size: 94 bytes. Origin: #x2264E531                          ; NTH-FIBONACCI
  ; 31:       498B4510         MOV RAX, [R13+16]                ; thread.binding-stack-pointer
  ; 35:       488945F8         MOV [RBP-8], RAX
  ; 39:       488B55F0         MOV RDX, [RBP-16]
  ; 3D:       31FF             XOR EDI, EDI
  ; 3F:       E8AC343BFF       CALL #x21A019F0                  ; GENERIC-=
  ; 44:       750A             JNE L0
  ; 46:       488B55E8         MOV RDX, [RBP-24]
  ; 4A:       488BE5           MOV RSP, RBP
  ; 4D:       F8               CLC
  ; 4E:       5D               POP RBP
  ; 4F:       C3               RET
  ; 50: L0:   488B55F0         MOV RDX, [RBP-16]
  ; 54:       BF02000000       MOV EDI, 2
  ; 59:       E8C2323BFF       CALL #x21A01820                  ; GENERIC--
  ; 5E:       488BC2           MOV RAX, RDX
  ; 61:       488945D8         MOV [RBP-40], RAX
  ; 65:       488B55E8         MOV RDX, [RBP-24]
  ; 69:       488B7DE0         MOV RDI, [RBP-32]
  ; 6D:       E84E323BFF       CALL #x21A017C0                  ; GENERIC-+
  ; 72:       488BF2           MOV RSI, RDX
  ; 75:       488B45D8         MOV RAX, [RBP-40]
  ; 79:       488BD0           MOV RDX, RAX
  ; 7C:       488B7DE0         MOV RDI, [RBP-32]
  ; 80:       B906000000       MOV ECX, 6
  ; 85:       FF7508           PUSH QWORD PTR [RBP+8]
  ; 88:       E99507DBFD       JMP #x203FED22                   ; #<FDEFN NTH-FIBONACCI>
  ; 8D:       CC10             INT3 16                          ; Invalid argument count trap

Looks like it's doing tail call optimization to me, this is without doing anything special with declaim. Note that where it returns to the top is with JMP not CALL.

http://www.sbcl.org/manual/index.html#Debug-Tail-Recursion

Ah, so as long as optimize is 2 or less you should get tail call recursion. I found when I tried it (several years ago) the default was debug optimize.

I wonder if different installs (or perhaps it's Slime) sets this value to different levels.

Something to bear in mind anyway..

Wow, that worked, thanks!!!

WEB> (declaim (optimize (debug 0) (safety 0) (speed 3)))

NIL

WEB> (defun nth-fibonacci (n &optional (a 0) (b 1))

      (if (= n 0) 

          a 

          (nth-fibonacci (- n 1) b (+ a b))))

WARNING: redefining LOBE/SRC/WEB::NTH-FIBONACCI in DEFUN NTH-FIBONACCI

WEB> (time (nth-fibonacci 9999))

Evaluation took: 0.002 seconds of real time 0.001887 seconds of total run time (0.001887 user, 0.000000 system) 100.00% CPU 5,476,446 processor cycles 4,715,760 bytes consed

Oh thats interesting!, we don't use that but use tail recursion extensively

https://0branch.com/notes/tco-cl.html#sec-2-2