lisp - 定义迭代求幂和斐波那契程序

Question

我正在尝试定义两个函数，expo-iter 和 fibonacci-iter，它们是指数函数和斐波那契函数的迭代版本。我了解如何执行阶乘函数(见下文)，但我没有得到这两个函数。对于 expo-iter 应该有两个变量 (b e) 而对于 fibonnaci-iter 有一个变量 (n)。

(define factorial (lambda (n) (fact-iter 1 1 n)))

(define fact-iter 
  (lambda (product counter max)
    (if (> counter max) 
        product 
        (fact-iter (* counter product) (+ counter 1) max))))

; (factorial 4)
; (fact-iter 1 1 4)
; (fact-iter 1 2 4)
; (fact-iter 2 3 4)
; (fact-iter 6 4 4)
; (fact-iter 25 5 4)
; (24)

Answer 1

求幂

求幂在这里可能是更简单的情况。首先，让我们考虑简单的递归 解决方案。 xⁿ 等于 x(x^n-1)，所以一个简单的递归 em> 解决方案是

(define (expt x n)
  (if (= n 0)
    1
    (* x (expt x (- n 1)))))

现在这不是尾递归，但你非常类似于递归阶乘的结构

(define (fact n)
  (if (= n 0)
    1
    (* n (fact (- n 1)))))

并且您已经证明可以将其转换为使用尾递归和累加器的形式:

(define (fact n)
  (let loop ((n n) (f 1))
    (if (= n 0)
      f
      (loop (- n 1) (* f n)))))

在阶乘的情况下，辅助函数将“部分阶乘”与其一起传递。首先是n，然后是n(n-1)，然后是n(n-1)(n-2)，依此类推继续，直到最终 n(n-1)...1 = n!。对于指数，您的累加器应该是“部分指数”，首先是 x，然后是 x²，然后是 x ³ 直到最终 xⁿ。

斐波那契数列

现在，阶乘和指数方法使用单个累加器的原因是“部分结果”可以仅在一个值中捕获。在阶乘的情况下，它是“部分阶乘 n(n-1)...(n-m)。在指数的情况下，它是 x^m (其中 m < n)。

要计算斐波那契数，计算下一个值所需的部分结果实际上是一对值。要获得 n^th 斐波那契数，您需要 n-1^th 和 n-第 2。无论您是考虑前两个斐波纳契数 0 和 1 还是 1 和 1，要计算第三个，您只需要考虑这两个。要计算第四个，你只需要记住第三个和第二个。要计算第五个，您只需要第四个和第三个。那么迭代算法看起来像这样:

a=0 ; f_i-2
b=1 ; f_i-1
while n > 0
    b = a + b ; b is now f_i
    a = b - a ; a is now f_i-1, so we can compute f_i+1
    n = n - 1
end while
return b ; b is now f_n

如果您愿意将迭代过程转换为尾递归 Scheme 过程，这应该不会太困难。请注意，辅助函数中有两个 额外值，而不仅仅是一个。