0

我正在尝试定义两个函数，它们是指数函数和斐波那契函数的迭代版本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)
4

1 回答 1

1

求幂

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

(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 2，然后是x 3，直到最后是x n。

斐波那契数列

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

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

a=0 ; f i-2
b=1 ; f i-1
而 n > 0
    b = a + b ; b 现在是 f i
    a = b - a ；a 现在是 f i-1，所以我们可以计算 f i+1
    n = n - 1
end while
return b ；b 现在是 f n

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

于 2013-11-01T00:06:28.707 回答