recursion - 将递归函数定义为迭代？

Question

我有以下递归函数需要在 Scheme 中转换为迭代

(define (f n)
  (if (< n 3) n 
    (+ 
      (f (- n 1))
      (* 2 (f(- n 2)))
      (* 3 (f(- n 3)))
      )
    ))

我的问题是我很难将其转换为迭代(即使递归具有线性执行时间)。我想不出有什么办法可以做到这一点，因为我就是不知道该怎么做。

函数定义如下:

f(n) = n if n<3 else f(n-1) + 2f(n-2) + 3f(n-3)

我试过像这样线性计算 5

1 + 2 + f(3) + f(4) + f(5)

但是为了计算说f(5)我需要引用 f(4), f(3), f(2)和 f(4)我必须引用 f(3), f(2), f(1)

这是SICP书中的一道题。

Answer 1

在书中，作者有一个制定计算斐波那契数列的迭代过程的示例。

(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
    b
    (fib-iter (+ a b) a (- count 1))))

这里的重点是在计算时使用两个参数a和b来内存f(n+1)和f(n)。类似的可以应用:我们需要a，b，c来记住f(n+2)，f(n+1)和f(n)

;; an interative process implementation                                                                                                                       
(define (f-i n)                                                                                                                                               
  ;; f2 is f(n+2), f1 is f(n+1), f0 is f(n)                                                                                                                   
  (define (interative-f f2 f1 f0 count)                                                                                                                       
    (cond                                                                                                                                                     
      ((= count 0) f0)                                                                                                                                         
      (else (interative-f                                                                                                                                      
              (+ f2 (* f1 2) (* f0 3))                                                                                                                          
              f2                                                                                                                                                
              f1                                                                                                                                                
              (- count 1)))))                                                                                                                                   
  (interative-f 2 1 0 n))