Эффективно вычисляйте значение треугольника Паскаля с помощью мемоизации и рекурсии

Итак, читайте о функциональном программировании, приложениях для динамического программирования и изучении Scala. Я подумал, что могу попробовать это с популярным примером, треугольником Паскаля, тесты на известные значения работают нормально. Какие-нибудь советы по оптимизации? Я что-то делаю неправильно? Есть ли способ сделать это с помощью хвостовой рекурсии, которую мне не хватает? Любая обратная связь приветствуется.

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) -> 1)
    var i = 0
    for(i <- 1 to r){
       cache += ((0,i) -> 1)
       cache += ((i,i) -> 1)
    } 

    def getPascalValue(c: Int, r: Int): Int = {
        if (cache.contains((c, r))) {
            cache((c, r))
        } else {
            cache += ((c, r) -> (getPascalValue(c, r - 1) + getPascalValue(c - 1, r - 1)))
            cache((c, r))
        }
    }
    getPascalValue(c,r)
}

Ваш код четко организован и хорошо представлен, но он страдает рядом проблем, от простых до серьезных.

• var i = 0 никогда не используется и не должен быть там.
• безопасность: Нет проверки на неправильный ввод. pascal(2,1) будет с радостью java.lang.StackOverflowError.
• Ваш код указывает на незнание стандартной библиотеки Scala. Инициализация cache, например, можно выполнить с помощью одного оператора.

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

• Точно так же вместо неизменного Map в var переменная для кеша, если вы используете изменяемый Map в val переменная тогда getPascalValue() можно свести к одному утверждению.

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

Но настоящая проблема здесь в том, что вы вкладываете много накладных расходов без вознаграждения.

• небольшая проблема: The cache инициализируется некоторыми значениями, которые май никогда не ссылаться.
• большая проблема: The cache обновляется значениями, которые буду никогда не ссылаться.

Верно. Ничего не добавлено к cacheпосле инициализации служит любой цели. Это просто неэффективная рутинная работа.

И причина, по которой ваш кеш не работает: каждая итерация (рекурсия) начинается с исходного, инициализированного, cache. Эта версия обновлена, +=, с вновь вычисленным числом Паскаля, но это обновление теряется, когда кадр стека появляется и выполнение возвращается к вызывающему.