recursion - 尾调用优化 Racket

Question

我正在尝试学习一些函数式编程，并且正在方案(racket)中做项目欧拉问题来帮助我入门。我目前正在使用problem 15我认为我有一个正确的函数来计算网格中的路径数量。问题是，对于大量 gridSize，该函数需要很长时间才能运行。

(define uniqueTraverse
  (lambda (x y gridSize)
    (cond
      ((and (eq? x gridSize) (eq? y gridSize)) 1)
      ((eq? x gridSize) (uniqueTraverse x (+ y 1) gridSize))
      ((eq? y gridSize) (uniqueTraverse (+ x 1) y gridSize))
      (else (+ (uniqueTraverse (+ x 1) y gridSize)
               (uniqueTraverse x (+ y 1) gridSize))))))

我试图弄清楚如何使这个函数尾部调用递归，但我不知道该怎么做。我需要一些帮助来开始如何考虑使用尾调用优化来优化这样的函数。

Answer 1

问题在于您一遍又一遍地重新计算相同的结果。为了解决这个问题，你不需要尾部调用 - 你需要记住旧的结果并返回它们而不重新计算它们。这种技术称为记忆化。

这是一种解决方案:

#lang racket

(define old-results (make-hash))

(define uniqueTraverse
  (lambda (x y gridSize)
    (define old-result (hash-ref old-results (list x y) 'unknown))
    (cond 
      ; if the result is unknown, compute and remember it
      [(eq? old-result 'unknown)
       (define new-result
         (cond
           ((and (eq? x gridSize) (eq? y gridSize)) 1)
           ((eq? x gridSize) (uniqueTraverse x (+ y 1) gridSize))
           ((eq? y gridSize) (uniqueTraverse (+ x 1) y gridSize))
           (else (+ (uniqueTraverse (+ x 1) y gridSize)
                    (uniqueTraverse x (+ y 1) gridSize)))))
       (hash-set! old-results (list x y) new-result)
       new-result]
      ; otherwise just return the old result
      [else old-result])))

(uniqueTraverse 0 0 2)