方案-加速一个重递归函数

Question

我必须编写一个Scheme谓词来计算函数f(N -> N)，定义为：

• 若n<4 :f(n)= (n^2) +5
• 若n≥4 :f(n) = f(n−1) + f(n−2) * f(n−4)

我编写了一个可以工作的简单谓词：

(define functionfNaive
  (lambda (n)
    (if (< n 4) (+ (* n n) 5)
        (* (+ (functionfNaive (- n 1)) (functionfNaive (- n 2))) 
           (functionfNaive (- n 4))))))

现在，我用累加器尝试了一种方法，但是它不起作用.我的代码：

(define functionf
  (lambda(n)
    (functionfAux n 5 9 14)))

(define functionfAux
 (lambda (n n1 n2 n4)
   (cond
     [(< n 4) (+ (* n n) 5)]
     [(= n 4) (* n1 (+ n2 n4))]
      [else (functionfAux (- n 1) n2 n4 (* n1 (+ n2 n4)))])))

Answer 1

按照要求，下面是您代码的回忆录版本，它比天真的版本表现得更好：

(define functionf
  (let ((cache (make-hash)))
    (lambda (n)
      (hash-ref!
       cache
       n
       (thunk
        (if (< n 4)
            (+ (* n n) 5)
            (* (+ (functionf (- n 1)) (functionf (- n 2))) (functionf (- n 4)))))))))

顺便说一句。为n的大值计算结果非常快，但是打印需要大量的时间。要测量时间，请使用以下内容

(time (functionf 50) 'done)

这是一个通用的回忆录程序，如果你需要的话：

(define (memoize fn)
  (let ((cache (make-hash)))
    (λ arg (hash-ref! cache arg (thunk (apply fn arg))))))

在你的情况下可以像

(define functionf
  (memoize
   (lambda (n)
     (if (< n 4) 
         (+ (* n n) 5)
         (* (+ (functionf (- n 1)) (functionf (- n 2))) (functionf (- n 4)))))))

Answer 2

首先，这不是谓词。谓词是返回布尔值的函数。

要计算n_th结果，请从前四个元素开始，然后进行计数，维护最后四个已知元素。到达_n时停止：

(define (step a b c d n)
  (list b c d (* (+ c d) a)) (+ n 1)))

等等很简单。第一个电话是(step 5 6 9 14 3)。

Answer 3

递归树的深度可能是最大的问题，因此可以使用迭代，这意味着使用一些变量来存储中间进程。

#lang racket
(define (functionf n)
        (define (iter now n1 n2 n3 n4 back)
          (if (= n now)
              back
              (iter (+ now 1) back n1 n2 n3 (* n3 (+ back n1)))))
        (if (< n 4)
            (+ 5 (* n n))
            (iter 4 14 9 6 5 125)))

(functionf 5)

这样，堆栈的深度仅为1，代码就会加快。