尾调用优化球拍

Question

我正在尝试学习一些函数式编程,并在计划(球拍)中进行项目euler问题以便让我开始.我目前正处理问题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

问题是你一遍又一遍地重新计算相同的结果.要解决这个问题,您不需要尾调用 - 您需要记住旧结果并返回它们而不重新计算它们.这种技术称为memoization.

这是一个解决方案:

#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)