Efficiently calculate value of Pascal's Triangle using memoization and recursion So reading about functional programming, applications to dynamic programming, and learning Scala. I figured I would try it out with a popular example, Pascal's Triangle, tests against known values work out fine. Any tips for optimization? Am I doing anything totally wrong? Is there a way to do this with tail recursion that I'm missing? Any feedback appreciated.
def pascal(c: Int, r: Int): Int = {
    // use a cache; map if (c,r) pair to value
    // fill in value recursively
    var cache: Map[(Int,Int), Int] = Map()
    cache += ((0,0) -&gt; 1)
    var i = 0
    for(i &lt;- 1 to r){
       cache += ((0,i) -&gt; 1)
       cache += ((i,i) -&gt; 1)
    } 

    def getPascalValue(c: Int, r: Int): Int = {
        if (cache.contains((c, r))) {
            cache((c, r))
        } else {
            cache += ((c, r) -&gt; (getPascalValue(c, r - 1) + getPascalValue(c - 1, r - 1)))
            cache((c, r))
        }
    }
    getPascalValue(c,r)
}
Your code is clearly organized and well presented, but it suffers from a number of problems, from the trivial to the profound.

var i = 0 is never used and doesn't need to be there.
safety: There's no check for bad input. pascal(2,1) will happily java.lang.StackOverflowError.
Your code indicates a lack of familiarity with the Scala Standard Library. Initializing the cache, for example, can be accomplished with a single statement.

var cache: Map[(Int,Int), Int] =
  (0 to r).flatMap(n =&gt; Seq((0,n)-&gt;1, (n,n)-&gt;1)).toMap


Likewise, instead of an immutable Map in a var variable for the cache, if you use a mutable Map in a val variable then getPascalValue() can be reduced to a single statement.

def getPascalValue(c: Int, r: Int): Int =
  cache.getOrElseUpdate((c,r), getPascalValue(c, r-1) +
                               getPascalValue(c-1, r-1))

But the real problem here is that you're putting in a lot of overhead for no reward.

small problem: The cache is initialized with some values that may never be referenced.
big problem: The cache is updated with values that will never be referenced.

That's right. Nothing added to the cache, after initialization, serves any purpose. It's just inefficient busywork.
And the reason your cache isn't working: each iteration (recursion) starts with the original, initialized, cache. That version is updated, +=, with the newly computed pascal number, but that update is lost when the stack frame pops and execution returns to the caller.