Optimizing recursive functions

Over the years I've written a lot of F# code. As a personal challenge, I try to work as little as possible with mutable data structures. One area where I always run into problems is when my recursive functions end up being too slow or start blowing the stack.

This post is a mostly theoretical deep dive into several techniques to tackle these problems. We'll explore:

• How we can use memoization to speed up recursive functions using a mutable data type
• How we can write an immutable variant of any memoized function
• How we can rewrite any recursive function so it becomes tail recursive and does not blow the stack.

By mostly theoretical I mean that while we'll show that it is technically possible to do all this (even combine all of them), you'll soon find out with me that things quickly turn very very complicated and make the original algorithm almost unrecognizable. Now that's not a desirable feature for source code.

We'll explore all these topics and close up with trade-offs I'll be making in the future when I encounter these situations again.

A simple recursive function

let rec fac n = 
    match n with
    | 0UL -> 1UL
    | _ -> n * (fac (n - 1UL))

fac 15UL

1307674368000

While this technically works, you'll soon find that fac quickly grows too large for integers. Let's rewrite so we can calculate fac for big numbers.

type Ordering = Less | Equal | Greater
module BigInteger =

    open System.Numerics

    let fromInt (i : int) = BigInteger i
    let Zero = fromInt 0
    let One = fromInt 1

    let compare (other : bigint) (one : bigint) =
        match one.CompareTo(other) with
        | 0 -> Equal
        | n when n > 0 -> Greater
        | _ -> Less

    let rec fac (n : bigint) =
        match (n |> compare (BigInteger.Zero)) with
        | Less -> failwithf "negative input: %A" n
        | Equal -> BigInteger.One
        | Greater -> n * (fac (n - BigInteger.One))

BigInteger.fac (BigInteger.fromInt 15)

1307674368000

100 |> BigInteger.fromInt |> BigInteger.fac

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

This works. Victory! But wait, what happens if we try to calculate a really really big number?

//8_000 |> BigInteger.fromInt |> BigInteger.fac

(* This blows the stack:

    Stack overflow.
    Repeat 7379 times:
    --------------------------------
    at FSI_0003+BigInteger.fac(System.Numerics.BigInteger)

*)

One way to typically fix this is to rewrite the algorithm to a procedural style. "Never use recursion" you might hear some people yell. Well, functional programmers decided to solve it differently, by having the compiler do the rewriting for us. This only works if our recursive function is what we call "tail recursive": the last statement to evaluate has to be the recursive call. You can rewrite most recursive functions to a tail recursive variant by adding an extra "accumulator" function argument.

Let's make some tailrecursive variants of our fac functions.

let facTail n =
    let rec fac acc n = 
        match n with
        | 0UL -> acc
        | _ -> (fac (n * acc) (n - 1UL))
    fac 1UL n

module BigInteger = 
    let facTail (n : bigint) =
        let rec fac acc (n : bigint) =
            match (n |> BigInteger.compare (BigInteger.Zero)) with
            | Less -> failwithf "negative input: %A" n
            | Equal -> acc
            | Greater -> (fac (n * acc) (n - BigInteger.One))
        fac BigInteger.One n

//But tailrecursion handles this just fine:
8_000 |> BigInteger.fromInt |> BigInteger.facTail

518418106048087693980581979742772698565110053193684177067236115459542947531660618755664354476267848215721662717783424020914023554563607596661295109473035934508368049334529053780777284244223430948668504207545761629848697390630280108045604778380793419853373373241702156878307605146518986496547492843108129850676988443139382900553680505933692323370157777611954181395779927796928247982170444256906306429759566061528421738794329359339468182701866734887806167541398761045774894243127307541875770767227297986629101155793901393578157362232516334761860506081091521685258567831245656488623686484709916159918400410323236342739061772155087262151227852898002928966166337781474091134426418627368180539561760331968886816947921436631109695661666245684235347409472399367755920005965402229576208803457199256068521551553661311155524897994758747603235461510505818523247055078948496222223442715543838081951121783330139907509699790888717222883475396658118272900322097610042509495611276615047357641584209913883188366659628343501107576294854855387214469504848112747596438888369446475019134111011501343192924809570928328743614679068177172844133742153895784205066445359373179364373724503629172015811671832744376427799953456253926254815918336720839180623672152524599032798876532000651404763090402904846377021889409054880075074330035915746013581951397679234264626325716666208358863877857354875485114368978703422452801804745912380473433938245758777857379720962836343195734870302933762389927964772487306499320425492053257884304114923600611561065059348621932000191044913247197002112598116849303073027497851336208821228098457820771418128279663636281919736682853516013750443872899773693135004411493851083885387919465847409039413722857815932350472381855940113224590016771502927089360042246524851094663866519732100544537984474106431632382996361405868123491087931409556953180023467219689666985659043507648638993185555032391476592989603817980797187079326745529992568378670466402553392065589724907786307976432282923508630080612066399364394087362940657084861741604238603058000177273737324939049242427069401233781239427064894711207138816992593324626422093000165907366304531733947379709875758419929746468759763347574605862736219062719162802934776051324915112324675051207899522543854613472700966385681597483823240290724203423746000777608901327855517703967794926759599318188419815608963705073278673613347503846276358172661685186400054227521286095944437474628828815416752946797387377803993132307977743874536886405196707116428325010008390076118085023509855901425677881215390191084968822857779764810461232801215225250453945371051887604983603210599347390415572134748871996381136420181183927908519090943765868096350062829224703049539833784333488113981222038590365224970636318615322669160702518145473457511308397306484776527581031440408269743653475030891979835839571688879568246299771375616141706254412709734535561698655132591562272543562733728037125630510522338495620247153065406673641171911247025111599127131919278119901946202202900420605841700502137363643400530449428232262208147855188442972910525926948277672435128762766226623803288675015950568693980330472897251255912752555086747699074336716429453545018715237297671770423227870308215406841968509923168373489334271228707173663770605020100887635151376402558425283231675724420477333804519100913185175833311056172362915706560173068715525641357235043852576193149496303091802382473809218898067301964100240032236672740010018709023718766499325451726553769181857598896908226610058781617074343895193549938022684502115926717558203051385840465551468182009736206263225230080920395415836964139134077374976540459014194587173401086007714588648281935796979127857978500176487837663541357704306718962709596323862328424388948855952593156121407796924204343433792959175234253099019663129924355197381560125307245937875986131702018922748275714074811125637423674499590097089771168011616237164413253261188532762246616357895677107835342651479722286390903979733889472876802052433456727054129289081777687203684206396848262729368288410829212938731059158883944802796422351899293854805220151052150255403792924966235904976721084861621417331174480499388198724665233026853951536703916582582919750767810071491528241730763106657483215591266757538045028576437215752613736240871407716553987134688010272333278635449781403820926117624889904200595388058154840847900041456449428020159837296817601709003855808023992016402258977370983537506446597820596498794127260024788516867242267969836133536982042478200975050300542586831915636143535539923136003660639505835016508002791960076149854255374904829809498247370234097701599959470899798967406248249793462468470439831797317577360617651720535704347230501297960182193175253193291346530884405078339627263638083422310621128913354357965301032620384871261082289565878660543240680612098488677496662379472499464023699794391110892279671187896710367097037598399448041050380729682279672602453763653688192887619853167370019386672798826266516085498194611006083658431522287545960922406608788280515234278556000828199933743772205192621580892857410620079364794592703445358325796124522152084379129744924850226312875933156987040594270392789396123562608445234714840989446801247212278866800503431135291309307759145876626507928635430364200225410988547052095805754729672645096735345590415506781517991901202071558500691814001155052086236840275026617314890579379132198308370863345605996821260052714506502897092981110976146098275576586226203483495564951321636768860604350374203264881475884647359468796336636772961647925528531991731768332139007384709833919057122055356801398113715260539656506222495557736309966973538283601594885658148286205703803599139582983568726286352133327966713501195384738051734513915528283985721002160794007854181272612511407105616970219836146882120646691349368513840569709621572332739957486726516503266184495143594309085324288809870112984334569382155857576419592128801325833682754482561452109640363623620516335170866014853670598927017905603375812106835560994777712199603174038304905627990760195069853017879114027518831690930907538010142363121359571196694506978470112164318189264780101629119768584529025100234674156440259901784170027486286525109206142134276060760715428793437586914648125531578832014274631894320051042067384055994350729793095948139393941954008571405599874170789924778895191048562079881915945916510486611667229874731401488635641665030418387272838297352149377892194611187186278877978779279211007733753111500513230267968068279518685349583148605779157562329072929840925154565309846270577867309364173018488325424599128280457806290896059221424585478978051880136307055948197052973839179729703352004565586316547074051590082791998630472336364275772835367704607434655555895040987462504534478846156876872291879443015135621328868080447319311789197930545169226056320179608446944334070884799048541296978551711521171662097208976028515355587530564668095557844081247818379847124522100227264717773387709812893047216734161737779244808671798863169603604702067708327225865208590852238027346814235371074353562979236469861215992536432381883527804878852556904915867492334750077615603294009371645748372619280000271819829207466455481586803576205469340966077101474742790958713889468504699001375242050840536265920344049202032712946232990628957314443860583718843731796367411004363105167021608731208960147589451175789562418808058742376774533869681099583595663570162510225185401892197554650940553033862784973940813082943528989916245759636884603592922942179089834717845623469427630970120264291626665503555870002230052700901821226528604521820641241774988412942718933630236545392854872489624025374107977924302496359457057666312900684105646750182803436192854844637909465320300432046768856779963875998356086421228482720653451286883075471880601344391757519017334326614159043363562037414769077961990945245871144350908034086651367202309658137319863540339320894196168992042443247479685739610871273779670374735288368190961659702683553474243684725516840742170713546527465351169633291477837802438109913211756794927404037780080185203800601571404273737200897929164294021760807460261106420721599900919392025243976226130332918724052430703908618179339946687720816993426189782921302903199243798320405892256295397948604154863731053612062694772069210460875609282270030938757227006473929490502103126325660596143781824160753011043140715146124558360924089715072984204779781835197788072317871999593258891547460748111727314324481807111150796794167073425814372980670823867211244790977107327425213589275407173839400672106380711507708832249672321227800963924157246597358535592913088036465860815466730795426616145137976962359560220931785295172308998636316463721676985771992558103408064851104575479435430211345962993601293187655441352782252902590527926522424591924205553834577955560496463970158005509835205933974482452101740740722504986040233648168337259827284685492851196846428036864939521956334520888087080158055515711364337412372208481630276916412221639299025700747752240531696532666686218725628350419226612214249912112272038315469235184919023735421374651477713899689902574778483971902122933012204453469461940271761205511256653508875814564524920392708526639232774005511110260617547768849421405758446738144625094052220243536057847841793512350701825943918747835269634297284950135911186919570803538296478378378375428103233426388310703317519101240879798544735807781388066249230897393702580086086491991864740301737172761764714713662746149363926422973044577653378175676090886131560515484137237606062055878441613044308279121154983569404154114872881123734064426387876102804973264492010438549956477059902218751719545599693274865317849458679217080779079532985693151854656776943943252061408393979950312691643352239662864795627434085279151391438546641956515325790952059232506729321274234501644567127828330885806257158025641500206849889991763710190411488627846123431332358157438670232102661280225814913819758864164673367639545014022683984556946285227888856016683422618517101974328190701534700049126198814129169847175048511704672829315661413922281029953877942958812652836414256893698741612147518053774066461409706781189031507794742605730069216209258121084701394688592230323495697379343272025567484297130963727950273194560496996581585585029475502566900823507684447584035332981187083641753739800475887637586877622746093668975481375106685146379691944621180344490911927307327384315812738133079051058069508430986414194004837974027668443177627531529574101286800547796932459656023892413744268103968044072911554279193040563950921330913594764707025579212259585961344209024518561900210576367846373949584642780619684626102230192604302606503700283459409047534928062321098905421105217666613170862746516609962920069953712867033703896981865630777821300649718919901691320027309879547830050596943725479115712885149439638030706739067546731791062172306957004767812540061439472486918518516851293625181315650641847909824248114795011763940815454471436935179199963557711695475074709960961068490924704550755554457069816139326652496233701415986857255906823801557687377710351317046805581647136646152348786681605128607558726664726508570839500813854656558562493531554226417140080274470357966882556808696360880416600182819640908410649963622226244348003429756253416780756119297686588603410538920904746114367613319517386368532552845938173895082671956689854882460963673708162908311991056629941819039621522066762260038865930820655028747661997523265131421444018870731106820214801084200087015858381566667949104018354215100964360361238119760727794008102384718278419383947530110799909401404187191523196007197256298836219192838192643694328614191275186771199264507055483995229751991369694991531023016389273025500153603021242089298570020310405784358039219354201906241352377061555439595390973816068142724892489333730748057037049991012057306143940928922490697874394897503031240271758315006048452158054994291318216885552017318607217708706617926694580356605384789634308661301778820015833892543621561686972258078026012470379563011537634795297082050699603359688926172854543826904965429132038847287946633035545286834183237983993089078591849380798441282875324723001511532051828469641634507556883838911862848099621480738447840752251776825179188746868033434597825646770771972904368101874622770034260305720804215333943714014839786725545926379598118539312442808321596017984420564182394160005755945970734140916638828099560093557278954937352205279627853874890852661539536004949875665230402928137689706028936264661100063672670024066161949812998910676480858243511207695537867953361484150629560592594755667780370414915335237337105298101322205825010959955481967682516942197795619581022248985924038232411270568957518735412692180396066179661832626411598555482984032402938741412543383229811170653495971125853014360102425425393171238718068204183634326188371820603595207500478697645141715210872380542402862825565323001229473571027379253814741536079924522614985780552362088272066419128301805336736660483053490253788684564898125095077864893596233537770470798291189490416401875596031440309768442323559322107371782458060545572175291496592381841146847286528241568631390318325840714441898710340151176272766455559887030163834179793895463605198272327530590064886746051912822887829494684942995299756761561386333972111414897396997687096348218137269597753249222074153005544917048458576935234496944754853987169083629014882410297523903402739411448245456665283100169224488805288725259059096708464269310555657228583412994652178729107219271266647443134189676611842668208871005900874469701931028977046278572250965106199912979014767081399206242047982797689871592039103587526580726878542693224384302683475685516796294767218846169794947761512046288531746693018660653320207273756895385543554063909920784866459926317449279472492515572202125950844904259026705220344236375434393699359913877482510638122567220612234317709414475822725880529154179271085148958130624137007814937559094107276708520761175798677288553663558355790941970123089000116988661588900089369996231453622810753529510779557684760013949293804305441802334440976357891596154811936455459093359363430597512214770118723361752663705139866877474841272005126038867666113287002516226743121216028873518378029467755963695070109542009524405499895084888529288274441859114634307929388858552508605567412147978516892525403407409592227546748877144184464724989519549604997992231151172729843015210211685038622303026640562366516093079164131896215800127836009511908249203969532506460371592899988195221069257068290811407456906629565234802001334059591600953361500438386538144912148224510507167160197028878594712497732094471536076676717727921870904806869298254047951723354320428746216244599513464499783237761039222993421874401535095581798656968275677039977373619626939100734237406261140806866086924468772071437816918317079644511676553805118811872121822446078430122472344516388032032957707503382951085021374915964819324456446537395189829711167053582705562030416916637254702679762844541606121974238374235032877206639015106102673603733412116494278484402625897273276711032768142606360965616417478105573959809673504281857296900348494674000184656379797078439517399849618768559271410055764219067491845658429670416079051733256942365897425601423003784339808118269949730305084404192739053923623238593133959720489075671535574108303801904335447278160258923244480870169478471637597986647910673484554012641544990079890748657662647921442170239790875742308660148721412279161097594273558007546631723253742063841031253394787581867976442695861885943883823023002487885368430638247722578426581578991193465577711944608741571364818908998927654632946516766481880250832753348216739830952192866223126793887085031738232829093258175116271636900053106299673943450464654199216408784321352200016877882210859110964858414880190614833591831661157997863271219099555238297799100312811421703486919039816031206818011367542755381206896247988319159872341685928975624506952434275454600889560048081549072933047345486925026922172283292388425914519814660308139779741954947878846948871450434842852217146323594736511213534517027595065988631018972926805427823694336282367097639062687741604349442619082022602674364369146026100745244516104604043336520736209524875622409566445048326501796999679279966209546513283944526809276744550567653373566027490553746733180266712143852523698203190627361657542503697122038135656154547364837695141135045002714657646479085524673891509705537454772308614785521004073822274794883444483948029614596385002888806534028172578255152746310172105614679855018894749313931271737674607696377882136074587455972431412691959353690816108647983565045705907006785585099096194089639309154301952227211512957838928395185177592095848841526902664388687157577154227017906133116231020369869238391355700979288171404887428085455590188208464275866952969340930129113980421712312857379383700921929399857891953234557795378596612840832888129620217480287768203187771349978151283965752714268708158441406793266275908126453575543257836321889633424126936300350340175256131231198765218715392862136537329311972760502238344810033589808744719682218162299987399609909153907347753543210496797294470701590452206570587438942216083306141421958285449751634098929249822792058428109780836450483662492583632583351922301241714073724373154219896451396515045519894309506929811312267798060487583807058673439455719219855167687968513180667079995155789876320603692698735872652824410014777773971550062587765097267278662693180366476323358555877527305035060834300996344518274454894054734966651584784997741943524118472442808731743036335823119001154787441382012030626011704035712890870819301545042518929175120103570839396582525955101216193510570294387376348906521081513231969896696127462464041000828430222015899110174987691040265120238554439253637004618472297746267012844592935243809635699917510083061386262600308055561400135666595723825480662780989054901903190177832119838497119701876252137584999981403590607411622901754839584592043280970562326459599279018127907537995849812394815540155155118710214928862582217599476601332173718528587656645032782330619157326793553333740025567934145046356972399294504607443125702283364163036878588239431879757217227575168781215998617178608302800242648228651440257189612209556584215040219748565778230999153944359103396363893123330702732589138833504416076293917250206344811744143596583403903664476933849303162646957740901050631671032150391876561060020667165606000829038819329867801346127460525801499142445607201210061826828700702224394979279825583401080126188892494082381807305944532261398812800189045099658061521677318841467950766946983954032054461791381417166574082617795104286891401037847414356786008631614618269240484508324047357028689786963021377775512147079505079465039079290709495208548361439560119651331188350563243783116505605044746688033395582732729994918205208314413791658389197271478367122422880377351566694969525901551386644296755838613917175738677911211131197767489950428867251899016035044473845039747303149121199220126742213218024708992444038317738150938772855865951677442396028540176322203559485815393088304856986042265425932526760779476081725906220248079218648246051091918491131594669305820039736971877228468052970310620056586225990042998742904075764997888887641347224249585653993959454439409251864620019082403910857924963083335621883110725112116969065772552563325071823055734819900598556254506551839049964715526756892384536850667001900536863534172753181937100254063521579530093224092593367027882375926579877669086930514445921083872151019543635501655188608803699759660762396019792534305939538435317714872527952889634790568830691706395709778968818142391232382135525817528721692690500096644376753070926965605757098361924331446371503856290854122315334099565151842939607166959125896455421991596631338814398485866551335778529135118116867252306355238266557330908822475510670301149543006933686116787600231879067802773920880645554984334179711459656134749317061360393785481168643826097478770564039584695975130602181175420048128396741141441662343765784680412547681863877957772758926871839815020570088699707781666671442680147814284914402491889183181140008704614287282275626499750186634986297894861748259817535394088028762955360905637361303943532152453416310702721179870819170439851648914783387696148215301717594981914949113758320644921856301191743882476422983901606084126778083419844875988733083455190669351296421583351475838552301139817607179503707851419258156644449304980136663579779448084149983107255259970771598807019625801675327986776630271716647174230926834961881336765351750548687555117081611106419103524225081655713491562767305205578350891485282821231503558401206645426743153255916118535078897672023261770167220795653391537251572761178970023666666821585701824927756307942494811953572955764497239898899709705141776754378717732032151073075777407295474896924572191041777497424248558239972069366204896708060402193103618418943264331474429954915211712907761977627437993388952684572160787709156232200827295984364947735523689918078727862052631328964123782946323623800512810930248232116892183535110224369865971324729965779337042186771352107391341011398277639819360289966479028826123626288692717048953060679147575924447224260076681969908449777442395670940662753562488730153775201287208244574010140685177691038823753076694409103833976466966489270700824198248256437268737748031522924873400415646989334262540486829698466488259767520113554902475091715336071850630870282361201725082775726442731104437606996292501427860083553888486486633598237988633653745901495453886936035807195926909326893132920426579944698127125189787541522220489920639535565646433325826264196357717305150797561686475790150073409941213688042603233638814412569699704488234128292756405672156418309054037861200398674655398354464691098144356676229734772645940788270630988622385360004618730214404010416544917371017498859767442256732988912004453892630831073871136113565265262355511926344247627110620833249582002897543848847912460790962197409582346069214486071091577886198260394377717583312346340863657571758353898389044402750355639505396344831256749108835134412029324951300913341284628897726772266638222744438931565597295576279779105482056718442498924513605985176895477003469169975768977197248456328943667149083073726897042708894044009902095556309877886252878178574300328317819532489009237812778893491662333308517002139790978343943920368186994385341336968040162404673965057155344362626021205126048206065452215215431902261978287662300944967602011216459918005968526604311194362419340124921418441603588201995086668321075309534365798867630404102775555673439838574538526808888085200679505637867171209916047505790888475908109585455667908604842063304535151366852193016369923051993124477886494372320167032602568869781561858959333454601691710908369699105963833860365749137499963308946649214132654678447159174571705335848097216526531688020423300531726610771394947417791429364404314252888169560331704994087222248492437573711028495021945008969667805459395185253447587545340139362288426293681014499502690596428513115635868159273518165694415041974822479251181465322882967180277727538632678875685168879098096802117721407417720495851977350438609166251282323874782324434304550022706792237112465988848491152393363255212968798972102010805033876405859514525338980661001416118424006555972789176746880281741310647519374101780819903666064552777205121219482319874749139040108431965511895106058680766726905421647095906638166382301304676862732091264809340141711567477435835372462311195275818123971699145672899761642929217471655272161645112837851038199456790157509866743710011857992860322137292090429914259592709407464298381788980162572831207422514907159557151993625056325326563705926738580141143455405104664876269269906014828854705567851488373059629262742155373361463826927307791963951208578820594992208833204767568549543375066768735104738615830084532551238615342594499276176378707212571188289792971026470676272174833242962001581383700496749196107658008669394186690023173029577746544805501589149199375961314795462024966192308641437552316145353065506829707895653672386423416788647079696577701790187324015109190371448858021895892862990476604393071139101823743035261822903453713527204473257897820541226849514978318804983231870540092380900655396598656801261728445562879881821309110336068613260295084315942660724654079077072109429186168602512896323760066970836334736110704055573746751836537353946980075288035664902843799899655627155884469889181296882552595954072506625887883782926591082227742598262145565974389336470293276617997199572102261263133227306105281360879836397446879484298604602969365029885780794525359998658228798660822047547489883629020633458514381094212527914606644897528812749807259831427195126686663116425437070789571280305733888767960532170267125430675333431826397137575685278248326285510089691966625833538172650873834678599776327978257610438567653781590166898148904642065369515019668208969591163657776320723889235843095502792601081701503293903105003635199754052541275940905274081092794428147829331693457527255102402657578033956554738491074711130758893222742842560972383645040883933992139920761230769540484718491736130205856602335428054158503385456186103651989314289070619283974764359936765350668419694018987648409275820318815097580690756293045688206127551465877789586718056898533402052780073130173562205108668530295775152773524829590843655654743009010673209642979116053919742875641955927440147199984107832479356327404747242746377650490699410140223157813362315651279917888625428209064795668175297168690576375852290349092318760343553622293660293540843884596919387603775311986599910065725117711824606819729765142280249307345652152974405113642240707545861840265031128803055048211957120013740544755572697980479172094682038200291449231448328842092867185409978488579585449386055197371893568574285939167997298193838543587782038459250301261131532355533084026732544000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

That's cool. The accumulator trick doesn't always work though. Let's take a look at a more complex recursive function, fib:

let rec fib n = 
    match n with
    | 1 -> 1
    | 2 -> 1
    | _ -> (fib (n - 1)) + (fib (n - 2))

fib 40 //Takes almost a second!

102334155

This takes almost a second to calculate! In order to understand why, let's see what the recursive calls look like:

fib 42 = fib 41 + fib 40

fib 41 = fib 40 + fib 39

fib 40 = fib 39 + fib 38

fib 39 = fib 38 + fib 37

fib 38 = fib 37 + fib 36

In order to calculate fib 42, we need the results of fib 41 and fib 40. In order to calculate fib 41, we also need the value of fib 40 but we just re-do the entire calculation from scratch. This gets very bad very quickly. So, what would help? Keeping track of intermediate results a.k.a. memoization!

open System.Collections.Generic

let fibMemo n = 
    let d = new Dictionary<int,int>()
    let rec f n =
        match d.TryGetValue(n) with
        | true, result -> result
        | false, _ ->
            let result = 
                match n with
                | 1 -> 1
                | 2 -> 1
                | _ -> (f (n - 1)) + (f (n - 2))
            d.Add(n, result) //Mutable reference, we're actually updating the dictionary here!
            result
    f n

fibMemo 4_000

1489622139

Cool, that's way faster. But hold up, that's not tail recursive anymore.

//fibMemo 20_000

(*Here we go again:

Stack overflow.
   at System.Collections.Generic.Dictionary`2[[System.Int32, System.Private.CoreLib, Version=8.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[System.Int32, System.Private.CoreLib, Version=8.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].FindValue(Int32)
   at System.Collections.Generic.Dictionary`2[[System.Int32, System.Private.CoreLib, Version=8.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[System.Int32, System.Private.CoreLib, Version=8.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].TryGetValue(Int32, Int32 ByRef)
   at FSI_0003+f@48.Invoke(Int32)
*)

There's two problems I want to tackle:

1. Can we rewrite fibMemo so it gets rid of the mutable Dictionary in favor of an immutable data type?
2. Can we make fibMemo tail recursive so it does not blow the stack anymore?

Making fibMemo immutable

Turns out we can create an immutable variant. One approach that always works is by threading and updating the lookup table explicitly through recursive calls.

Threading the lookup table

let fibThreading n = 
    let rec f d n = //Note how the signature has changed: the function takes an extra argument (the lookup table) and returns a richer type: the result along with an updated lookup table. 
        match d |> Map.tryFind n with
        | Some result -> result,d
        | None ->
            match n with
            | 1 -> 1,d |> Map.add 1 1
            | 2 -> 1,d |> Map.add 2 1
            | _ -> 
                let (n1,d1) = f d (n - 1)
                let (n2, d2) = f d1 (n - 2) //we thread the memo from n-1 into the n - 2 call
                let result = n1 + n2
                let nd = d2 |> Map.add n result //Instead of mutating the map, we create a new and updated version of it!
                result, nd
    let (result, _) = f Map.empty n
    result

fibThreading 4_000

1489622139

Sidebar: Extracting the memoize using a Y-combinator approach

Can we make a higher-order "memoize" function that can memoize any recursive function? You can somewhat, but we still need to tweak the original function a bit.

• Combine memoization and tail recursion, stackoverflow, user kvb
• The Y combinator, mvanier
• Y in practical programs, Bruce McAdam

open System.Collections.Generic
let memoY f =
  let cache = Dictionary<_,_>()
  let rec fn x =
    match cache.TryGetValue(x) with
    | true,y -> y
    | _ -> let v = f fn x
           cache.Add(x,v)
           v
  fn

let fib_ fib n = //note that this is not a recursive function but rather takes an input argument fib that substitutes for the recursive call.
    match n with
    | 1 -> 1
    | 2 -> 1
    | _ -> (fib (n-1)) + (fib (n-2))

let fib = memoY fib_

fib 2000

1392522469

While this works and doesn't seem to impact performance that much, all versions of our memoized function still blow the stack:

//fibThreading 20_000
(*
Stack overflow.
Repeat 6852 times:
--------------------------------
   at FSI_0003+f@62-1.Invoke(Microsoft.FSharp.Collections.FSharpMap`2<Int32,Int32>, Int32)
*)

So can we make our memoized functions tail recursive as well?

CPS as a way to rewrite anything to tail recursion

Continuation passing style can make anything (?) tail recursive!

bouncing around with recursion

let rec fib n c =
    match n with
    | 1 -> c 1
    | 2 -> c 1
    | _ -> 
        fib (n-1) (fun n1 -> fib (n-2) (fun n2 -> c (n1 + n2))) //note how the last thing we do is call the recursive function. "Next steps" get delayed to the continuation functions. This effectively moves our calculation from the stack to the (much bigger) heap.

fib 40 id

102334155

Let's apply this CPS technique to our fully immutable memoized version!

type Ordering = Less | Equal | Greater
module BigInteger =

    open System.Numerics

    let fromInt (i : int) = BigInteger i
    let Zero = fromInt 0
    let One = fromInt 1

let fibThreadingTail n = 
    let rec f d n c =
        match d |> Map.tryFind n with
        | Some result -> (result,d) |> c
        | None ->
            match n with
            | 1 -> (BigInteger.One,d |> Map.add 1 BigInteger.One) |> c
            | 2 -> (BigInteger.One,d |> Map.add 2 BigInteger.One) |> c
            | _ -> 
                f d (n - 1) (fun (n1,d1) ->
                    f d1 (n - 2) (fun (n2,d2) ->
                        let result = n1 + n2
                        let nd = d2 |> Map.add n result
                        (result, nd) |> c))
                
    let (result, _) = f Map.empty n id
    result

Well. There you have it. A memoized fib function that uses tail recursion. It's fast. It works for big inputs without blowing the stack. It does appear to be working, if you've ever wondered what the 100.000th number in the Fibonacci sequence looks like, here you go:

fibThreadingTail 100_000

2597406934722172416615503402127591541488048538651769658472477070395253454351127368626555677283671674475463758722307443211163839947387509103096569738218830449305228763853133492135302679278956701051276578271635608073050532200243233114383986516137827238124777453778337299916214634050054669860390862750996639366409211890125271960172105060300350586894028558103675117658251368377438684936413457338834365158775425371912410500332195991330062204363035213756525421823998690848556374080179251761629391754963458558616300762819916081109836526352995440694284206571046044903805647136346033000520852277707554446794723709030979019014860432846819857961015951001850608264919234587313399150133919932363102301864172536477136266475080133982431231703431452964181790051187957316766834979901682011849907756686456845066287392485603914047605199550066288826345877189410680370091879365001733011710028310473947456256091444932821374855573864080579813028266640270354294412104919995803131876805899186513425175959911520563155337703996941035518275274919959802257507902037798103089922984996304496255814045517000250299764322193462165366210841876745428298261398234478366581588040819003307382939500082132009374715485131027220817305432264866949630987914714362925554252624043999615326979876807510646819068792118299167964409178271868561702918102212679267401362650499784968843680975254700131004574186406448299485872551744746695651879126916993244564817673322257149314967763345846623830333820239702436859478287641875788572910710133700300094229333597292779191409212804901545976262791057055248158884051779418192905216769576608748815567860128818354354292307397810154785701328438612728620176653953444993001980062953893698550072328665131718113588661353747268458543254898113717660519461693791688442534259478126310388952047956594380715301911253964847112638900713362856910155145342332944128435722099628674611942095166100230974070996553190050815866991144544264788287264284501725332048648319457892039984893823636745618220375097348566847433887249049337031633826571760729778891798913667325190623247118037280173921572390822769228077292456662750538337500692607721059361942126892030256744356537800831830637593334502350256972906515285327194367756015666039916404882563967693079290502951488693413799125174856667074717514938979038653338139534684837808612673755438382110844897653836848318258836339917310455850905663846202501463131183108742907729262215943020429159474030610183981685506695026197376150857176119947587572212987205312060791864980361596092339594104118635168854883911918517906151156275293615849000872150192226511785315089251027528045151238603792184692121533829287136924321527332714157478829590260157195485316444794546750285840236000238344790520345108033282013803880708980734832620122795263360677366987578332625485944906021917368867786241120562109836985019729017715780112040458649153935115783499546100636635745448508241888279067531359950519206222976015376529797308588164873117308237059828489404487403932053592935976454165560795472477862029969232956138971989467942218727360512336559521133108778758228879597580320459608479024506385194174312616377510459921102486879496341706862092908893068525234805692599833377510390101316617812305114571932706629167125446512151746802548190358351688971707570677865618800822034683632101813026232996027599403579997774046244952114531588370357904483293150007246173417355805567832153454341170020258560809166294198637401514569572272836921963229511187762530753402594781448204657460288485500062806934811398276016855584079542162057543557291510641537592939022884356120792643705560062367986544382464373946972471945996555795505838034825597839682776084731530251788951718630722761103630509360074262261717363058613291544024695432904616258691774630578507674937487992329181750163484068813465534370997589353607405172909412697657593295156818624747127636468836551757018353417274662607306510451195762866349922848678780591085118985653555434958761664016447588028633629704046289097067736256584300235314749461233912068632146637087844699210427541569410912246568571204717241133378489816764096924981633421176857150311671040068175303192115415611958042570658693127276213710697472226029655524611053715554532499750843275200199214301910505362996007042963297805103066650638786268157658772683745128976850796366371059380911225428835839194121154773759981301921650952140133306070987313732926518169226845063443954056729812031546392324981793780469103793422169495229100793029949237507299325063050942813902793084134473061411643355614764093104425918481363930542369378976520526456347648318272633371512112030629233889286487949209737847861884868260804647319539200840398308008803869049557419756219293922110825766397681361044490024720948340326796768837621396744075713887292863079821849314343879778088737958896840946143415927131757836511457828935581859902923534388888846587452130838137779443636119762839036894595760120316502279857901545344747352706972851454599861422902737291131463782045516225447535356773622793648545035710208644541208984235038908770223039849380214734809687433336225449150117411751570704561050895274000206380497967960402617818664481248547269630823473377245543390519841308769781276565916764229022948181763075710255793365008152286383634493138089971785087070863632205869018938377766063006066757732427272929247421295265000706646722730009956124191409138984675224955790729398495608750456694217771551107346630456603944136235888443676215273928597072287937355966723924613827468703217858459948257514745406436460997059316120596841560473234396652457231650317792833860590388360417691428732735703986803342604670071717363573091122981306903286137122597937096605775172964528263757434075792282180744352908669606854021718597891166333863858589736209114248432178645039479195424208191626088571069110433994801473013100869848866430721216762473119618190737820766582968280796079482259549036328266578006994856825300536436674822534603705134503603152154296943991866236857638062351209884448741138600171173647632126029961408561925599707566827866778732377419444462275399909291044697716476151118672327238679208133367306181944849396607123345271856520253643621964198782752978813060080313141817069314468221189275784978281094367751540710106350553798003842219045508482239386993296926659221112742698133062300073465628498093636693049446801628553712633412620378491919498600097200836727876650786886306933418995225768314390832484886340318940194161036979843833346608676709431643653538430912157815543512852077720858098902099586449602479491970687230765687109234380719509824814473157813780080639358418756655098501321882852840184981407690738507369535377711880388528935347600930338598691608289335421147722936561907276264603726027239320991187820407067412272258120766729040071924237930330972132364184093956102995971291799828290009539147382437802779051112030954582532888721146170133440385939654047806199333224547317803407340902512130217279595753863158148810392952475410943880555098382627633127606718126171022011356181800775400227516734144169216424973175621363128588281978005788832454534581522434937268133433997710512532081478345067139835038332901313945986481820272322043341930929011907832896569222878337497354301561722829115627329468814853281922100752373626827643152685735493223028018101449649009015529248638338885664893002250974343601200814365153625369199446709711126951966725780061891215440222487564601554632812091945824653557432047644212650790655208208337976071465127508320487165271577472325887275761128357592132553934446289433258105028633583669291828566894736223508250294964065798630809614341696830467595174355313224362664207197608459024263017473392225291248366316428006552870975051997504913009859468071013602336440164400179188610853230764991714372054467823597211760465153200163085336319351589645890681722372812310320271897917951272799656053694032111242846590994556380215461316106267521633805664394318881268199494005537068697621855231858921100963441012933535733918459668197539834284696822889460076352031688922002021931318369757556962061115774305826305535862015637891246031220672933992617378379625150999935403648731423208873977968908908369996292995391977217796533421249291978383751460062054967341662833487341011097770535898066498136011395571584328308713940582535274056081011503907941688079197212933148303072638678631411038443128215994936824342998188719768637604496342597524256886188688978980888315865076262604856465004322896856149255063968811404400429503894245872382233543101078691517328333604779262727765686076177705616874050257743749983775830143856135427273838589774133526949165483929721519554793578923866762502745370104660909382449626626935321303744538892479216161188889702077910448563199514826630802879549546453583866307344423753319712279158861707289652090149848305435983200771326653407290662016775706409690183771201306823245333477966660525325490873601961480378241566071271650383582257289215708209369510995890132859490724306183325755201208090007175022022949742801823445413711916298449914722254196594682221468260644961839254249670903104007581488857971672246322887016438403908463856731164308169537326790303114583680575021119639905615169154708510459700542098571797318015564741406172334145847111268547929892443001391468289103679179216978616582489007322033591376706527676521307143985302760988478056216994659655461379174985659739227379416726495377801992098355427866179123126699374730777730569324430166839333011554515542656864937492128687049121754245967831132969248492466744261999033972825674873460201150442228780466124320183016108232183908654771042398228531316559685688005226571474428823317539456543881928624432662503345388199590085105211383124491861802624432195540433985722841341254409411771722156867086291742124053110620522842986199273629406208834754853645128123279609097213953775360023076765694208219943034648783348544492713539450224591334374664937701655605763384697062918725745426505879414630176639760457474311081556747091652708748125267159913793240527304613693961169892589808311906322510777928562071999459487700611801002296132304588294558440952496611158342804908643860880796440557763691857743754025896855927252514563404385217825890599553954627451385454452916761042969267970893580056234501918571489030418495767400819359973218711957496357095967825171096264752068890806407651445893132870767454169607107931692704285168093413311046353506242209810363216771910420786162184213763938194625697286781413636389620123976910465418956806197323148414224550071617215851321302030684176087215892702098879108938081045903397276547326416916845445627600759561367103584575649094430692452532085003091068783157561519847567569191284784654692558665111557913461272425336083635131342183905177154511228464455136016013513228948543271504760839307556100908786096663870612278690274831819331606701484957163004705262228238406266818448788374548131994380387613830128859885264201992286188208499588640888521352501457615396482647451025902530743172956899636499615707551855837165935367125448515089362904567736630035562457374779100987992499146967224041481601289530944015488942613783140087804311431741858071826185149051138744831358439067228949408258286021650288927228387426432786168690381960530155894459451808735197246008221529343980828254126128257157209350985382800738560472910941184006084485235377833503306861977724501886364070344973366473100602018128792886991861824418453968994777259482169137133647470453172979809245844361129618997595696240971845564020511432589591844724920942930301651488713079802102379065536525154780298059407529440513145807551537794861635879901158192019808879694967187448224156836463534326160242632934761634458163890163805123894184523973421841496889262398489648642093409816681494771155177009562669029850101513537599801272501241971119871526593747484778935488777815192931171431167444773882941064615028751327709474504763922874890662989841540259350834035142035136168819248238998027706666916342133424312054507359388616687691188185776118135771332483965209882085982391298606386822804754362408956522921410859852037330544625953261340234864689275060526893755148403298542086991221052597005628576707702567695300978970046408920009852106980295419699802138053295798159478289934443245491565327845223840551240445208226435420656313310702940722371552770504263482073984454889589248861397657079145414427653584572951329719091947694411910966797474262675590953832039169673494261360032263077428684105040061351052194413778158095005714526846009810352109249040027958050736436961021241137739717164869525493114805040126568351268829598413983222676377804500626507241731757395219796890754825199329259649801627068665658030178877405615167159731927320479376247375505855052839660294566992522173600874081212014209071041937598571721431338017425141582491824710905084715977249417049320254165239323233258851588893337097136310892571531417761978326033750109026284066415801371359356529278088456305951770081443994114674291850360748852366654744869928083230516815711602911836374147958492100860528981469547750812338896943152861021202736747049903930417035171342126923486700566627506229058636911882228903170510305406882096970875545329369434063981297696478031825451642178347347716471058423238594580183052756213910186997604305844068665712346869679456044155742100039179758348979935882751881524675930878928159243492197545387668305684668420775409821781247053354523194797398953320175988640281058825557698004397120538312459428957377696001857497335249965013509368925958021863811725906506436882127156815751021712900765992750370228283963962915973251173418586721023497317765969454283625519371556009143680329311962842546628403142444370648432390374906410811300792848955767243481200090309888457270907750873638873299642555050473812528975962934822878917619920725138309388288292510416837622758204081918933603653875284116785703720989718832986921927816629675844580174911809119663048187434155067790863948831489241504300476704527971283482211522202837062857314244107823792513645086677566622804977211397140621664116324756784216612961477109018826094677377686406176721484293894976671380122788941309026553511096118347012565197540807095384060916863936906673786627209429434264260402902158317345003727462588992622049877121178405563348492490326003508569099382392777297498413565614830788262363322368380709822346012274241379036473451735925215754757160934270935192901723954921426490691115271523338109124042812102893738488167358953934508930697715522989199698903885883275409044300321986834003470271220020159699371690650330547577095398748580670024491045504890061727189168031394528036165633941571334637222550477547460756055024108764382121688848916940371258901948490685379722244562009483819491532724502276218589169507405794983759821006604481996519360110261576947176202571702048684914616894068404140833587562118319210838005632144562018941505945780025318747471911604840677997765414830622179069330853875129298983009580277554145435058768984944179136535891620098725222049055183554603706533183176716110738009786625247488691476077664470147193074476302411660335671765564874440577990531996271632972009109449249216456030618827772947750764777446452586328919159107444252320082918209518021083700353881330983215894608680127954224752071924134648334963915094813097541433244209299930751481077919002346128122330161799429930618800533414550633932139339646861616416955220216447995417243171165744471364197733204899365074767844149929548073025856442942381787641506492878361767978677158510784235702640213388018875601989234056868423215585628508645525258377010620532224244987990625263484010774322488172558602233302076399933854152015343847725442917895130637050320444917797752370871958277976799686113626532291118629631164685159934660693460557545956063155830033697634000276685151293843638886090828376141157732003527565158745906567025439437931104838571313294490604926582363108949535090082673154497226396648088618041573977888472892174618974189721700770009862449653759012727015227634510874906948012210684952063002519011655963580552429180205586904259685261047412834518466736938580027700252965356366721619883672428226933950325930390994583168665542234654857020875504617520521853721567282679903418135520602999895366470106557900532129541336924472492212436324523042895188461779122338069674233980694887270587503389228395095135209123109258159006960395156367736067109050566299603571876423247920752836160805597697778756476767210521222327184821484446631261487584226092608875764331731023263768864822594691211032367737558122133470556805958008310127481673962019583598023967414489867276845869819376783757167936723213081586191045995058970991064686919463448038574143829629547131372173669836184558144505748676124322451519943362182916191468026091121793001864788050061351603144350076189213441602488091741051232290357179205497927970924502479940842696158818442616163780044759478212240873204124421169199805572649118243661921835714762891425805771871743688000324113008704819373962295017143090098476927237498875938639942530595331607891618810863505982444578942799346514915952884869757488025823353571677864826828051140885429732788197765736966005727700162592404301688659946862983717270595809808730901820120931003430058796552694788049809205484305467611034654748067290674399763612592434637719995843862812391985470202414880076880818848087892391591369463293113276849329777201646641727587259122354784480813433328050087758855264686119576962172239308693795757165821852416204341972383989932734803429262340722338155102209101262949249742423271698842023297303260161790575673111235465890298298313115123607606773968998153812286999642014609852579793691246016346088762321286205634215901479188632194659637483482564291616278532948239313229440231043277288768139550213348266388687453259281587854503890991561949632478855035090289390973718988003999026132015872678637873095678109625311008054489418857983565902063680699643165033912029944327726770869305240718416592070096139286401966725750087012218149733133695809600369751764951350040285926249203398111014953227533621844500744331562434532484217986108346261345897591234839970751854223281677187215956827243245910829019886390369784542622566912542747056097567984857136623679023878478161201477982939080513150258174523773529510165296934562786122241150783587755373348372764439838082000667214740034466322776918936967612878983488942094688102308427036452854504966759697318836044496702853190637396916357980928865719935397723495486787180416401415281489443785036291071517805285857583987711145474240156416477194116391354935466755593592608849200546384685403028080936417250583653368093407225310820844723570226809826951426162451204040711501448747856199922814664565893938488028643822313849852328452360667045805113679663751039248163336173274547275775636810977344539275827560597425160705468689657794530521602315939865780974801515414987097778078705357058008472376892422189750312758527140173117621279898744958406199843913365680297721208751934988504499713914285158032324823021340630312586072624541637765234505522051086318285359658520708173392709566445011404055106579055037417780393351658360904543047721422281816832539613634982525215232257690920254216409657452618066051777901592902884240599998882753691957540116954696152270401280857579766154722192925655963991820948894642657512288766330302133746367449217449351637104725732980832812726468187759356584218383594702792013663907689741738962252575782663990809792647011407580367850599381887184560094695833270775126181282015391041773950918244137561999937819240362469558235924171478702779448443108751901807414110290370706052085162975798361754251041642244867577350756338018895379263183389855955956527857227926155524494739363665533904528656215464288343162282921123290451842212532888101415884061619939195042230059898349966569463580186816717074818823215848647734386780911564660755175385552224428524049468033692299989300783900020690121517740696428573930196910500988278523053797637940257968953295112436166778910585557213381789089945453947915927374958600268237844486872037243488834616856290097850532497036933361942439802882364323553808208003875741710969289725499878566253048867033095150518452126944989251596392079421452606508516052325614861938282489838000815085351564642761700832096483117944401971780149213345335903336672376719229722069970766055482452247416927774637522135201716231722137632445699154022395494158227418930589911746931773776518735850032318014432883916374243795854695691221774098948611515564046609565094538115520921863711518684562543275047870530006998423140180169421109105925493596116719457630962328831271268328501760321771680400249657674186927113215573270049935709942324416387089242427584407651215572676037924765341808984312676941110313165951429479377670698881249643421933287404390485538222160837088907598277390184204138197811025854537088586701450623578513960109987476052535450100439353062072439709976445146790993381448994644609780957731953604938734950026860564555693224229691815630293922487606470873431166384205442489628760213650246991893040112513103835085621908060270866604873585849001704200923929789193938125116798421788115209259130435572321635660895603514383883939018953166274355609970015699780289236362349895374653428746875

Closing thoughts

Can you rewrite any function that both memoizes intermediate results using an immutable data structure and is tail recursive? You sure can! There's even a mechanical way to do it:

1. In order to speed up a recursive function, we can use memoization. We can even extract a generic memoizer higher-order function if we really really want to, but in order to to that we have to tweak the original function so it accepts a "recursive function" argument. We saw this with our Y combinator approach.
2. In order to memoize any function using an immutable data structure, we can explicitly thread the lookup table through subsequent recursive calls. This requires even more tinkering with the original function.
3. In order to make any function tail recursive, you can rewrite it using Continuation Passing Style (CPS).

But should you? That's a final question I leave you with which you can ponder to yourself. I might be grabbing for CPS next time I blow the stack, but I think I'll stick to using mutable lookup tables for now.