;;; Recursion is great fun to write, but it tends to run out of stack.
;;;  Luckily, Emacs 29 and above provides a primitive that guarantees
;;;   tail call optimizations, named-let. See:
;;;     https://www.gnu.org/software/emacs/manual/html_node/elisp/Local-Variables.html


;; Stack-crashing non-tail-call version:
(defun fact1 (n)
  (if (= n 0) 1
    (* n (fact1 (1- n)))))
fact1

(fact1 5)
120

(fact1 100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

(fact1 300)
306057512216440636035370461297268629388588804173576999416776741259476533176716867465515291422477573349939147888701726368864263907759003154226842927906974559841225476930271954604008012215776252176854255965356903506788725264321896264299365204576448830388909753943489625436053225980776521270822437639449120128678675368305712293681943649956460498166450227716500185176546469340112226034729724066333258583506870150169794168850353752137554910289126407157154830282284937952636580145235233156936482233436799254594095276820608062232812387383880817049600000000000000000000000000000000000000000000000000000000000000000000000000


(fact1 500)
1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

(fact1 700)
;; Debugger entered--Lisp error: (excessive-lisp-nesting 1601)

;; Work through this bytecode
(disassemble-internal #'fact1 2 nil)
    doc:   ...
    args: (arg1)
  0	  dup	    
  1	  constant  0
  2	  eqlsign   
  3	  goto-if-nil 1
  6	  constant  1
  7	  return    
  8:1	  dup	    
  9	  constant  fact1
  10	  stack-ref 2
  11	  sub1	    
  12	  call	    1    ; <<-- runs out of stack
  13	  mult	         ; <<-- must return here to multiply (fact1 (1- n)) by n  
  14	  return    
nil


;; Tail recursive variant with the accumulator trick
(defun fact2 (n acc)
  (if (= n 0) acc
    (fact2 (1- n) (* acc n))))
fact2

;; we can do this now!
(fact2 700 1)
2422040124750272179867875093812352218590983385729207299450679664929938160215647420444519051666484819249321456671497049842327525093874817343838393757631459228450828499972271274140160311057830558463636337124079332447820739281101037112665387537180790257577919273108262916904750405235055060084012219492892375635136296622020023178109619818046179906897450420548912610870589088056503913584562211037693288782960900195074130999799035970711436279339094292032866260496375825461427727555710003007752906141470639574390024988514914264449865006458873226951941899545970333910351588559232940829569276986080222200289966128343931630028789203382654749603473516314765262772257171154686716862814184728741187147936349501653197457455660413134506049122044947052623384682088864790673309569292384215611788014274954905914148362303226200246816441301934846080254998647325270606104512088058712293349862185399243309054299576381718806247238195232604642614329894070636163753672091232751612378348273840757873567717532879242518337119540602943609411629349009566043720836737401090882392975031224612531245642687296717053747734506443314924558119560479901478736209556925161517737110399754730551854066328420014728657896286936523787080206476327157136441318773432751007263108056958251693811280957243202460157111778617472683761623869704457588005158037495665069625778930898095725794710701639238231528115579619120287378689238934335198508665933917257143975277707590597511989345068701735940169672561864713107115016747368992690116082633762172346688969840862517264384000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

;; But not this :(
(fact2 1700 1)

(disassemble-internal #'fact2 2 nil)
    doc:   ...
    args: (arg1 arg2)
  0	  stack-ref 1
  1	  constant  0
  2	  eqlsign   
  3	  goto-if-nil 1
  6	  return    
  7:1	  constant  fact2
  8	  stack-ref 2
  9	  sub1	    
  10	  stack-ref 2
  11	  stack-ref 4
  12	  mult	    
  13	  call	    2  ; <<-- still a stack-using call despite there being no real action
  14	  return       ;;        to return to; tail-recursive optimization was not applied 
nil

;;; Luckily, starting with Emacs 29 (check your version with "emacs-version")
;;;  there is a special form that guarantees tail-recursive optimization
;;;  Doc: https://www.gnu.org/software/emacs/manual/html_node/elisp/Local-Variables.html

(defun fact (n)
  (named-let fact-tc ((x n) (acc 1))
    (if (= x 0) acc
      (fact-tc (1- x) (* x acc)))))
fact

;; Look, no call! Just a goto and a loop. Tail call optimization applied!
;;  Work through this bytecode to convince yourself this is a loop that computes
;;  the factorial!

(disassemble-internal #'fact 2 nil)
    doc:   ...
    args: (arg1)
  0	  dup	          ;; saves the golden copy of the argument at the stack bottom   
  1	  constant  1
  2	  constant  nil
  3:1	  stack-ref 2     ; <----+   label "1"  
  4	  stack-ref 2     ;      |
  5	  stack-ref 4     ;      |
  6	  constant  0     ;      |
  7	  eqlsign         ;      |
  8	  goto-if-nil 2   ;      |
  11	  stack-ref 3     ;      |
  12	  return          ;      |
  13:2	  stack-ref 4     ;      |
  14	  sub1	          ;      |
  15	  stack-set 5     ;      |
  17	  stack-ref 1     ;      |
  18	  stack-ref 4     ;      |
  19	  mult	          ;      |
  20	  stack-set 4     ;      |
  22	  discardN  2     ;      |
  24	  goto	    1     ; -----+   loop back to label "1"
nil

;; We can do this now :)
(fact 5000)
422857792...0000

;;;;;;;;;;;;;;;;;;;;; Emacs interlude ;;;;;;;;;;;;;;;;;;

;;; I want to type λ when pressing Option-l on my Mac. By default it gives "¬"  

(global-set-key (kbd "¬") (lambda () (interactive (insert "λ"))))
(closure (t) nil (interactive (insert "λ")))

;; Now my Option+l presses result in λs being inserted into the buffer
;;λλλλλλλλλλλλλλ

;;; Also, I want Option-; (by default "…") to insert ";; " at the start of the line,
;;;   so that I can comment out lines with one press of a button. Also, I want 
;;;   to keep my point in the same column every time (for lines with at least 
;;;   that many characters; for other lines it'll be the end of the line)
(global-set-key (kbd "…")
		(lambda () (interactive)
		  (let ((saved-column (current-column)))  
		    (beginning-of-line)
		    (insert ";; ")
		    (forward-line)
		    (move-to-column saved-column)
		  )))

;;; Adapt the above to draw a line like the one illustrating the loop above with
;;;  one keystroke per line.