You use memoization. Inserts and lookups on an immutable [persistent](https://en.wikipedia.org/wiki/Persistent_data_structure) hash table are [effectively constant](http://docs.scala-lang.org/overviews/collections/performance-characteristics.html). While technically that constant value is a little bit longer than a mutable data structure, in practice you won't usually care. [Here's](http://programmers.stackexchange.com/a/310287/3965) an example from one of my previous answers where I memoized overlapping collatz sequences to get a result that returned pretty much instantaneously in my REPL.