recursion - 方案递归函数

Question

嘿，我一直被以下问题困扰，似乎无法提出正确的功能。

编写一个递归函数，给定一个正整数 k，计算乘积 k：(1-1/2)(1-1/3)(1-1/k)... 随着 k 减一。

我似乎无法想出正确的功能，我的程序通常运行直到它没有更多的内存。这是我的方法：

(define (fraction-product k)
  (if (= k 0)
       0
       (* (- 1 (/ 1 (fraction-product (- k 1)))))))

提前感谢您的帮助...

Answer 1

先用手做小案子。

无需尝试对其进行编码，手动计算答案应该是什么：

• （分数乘积 1）
• （分数乘积 2）
• （分数乘积 3）

在你做这些问题之前，你至少应该有三个具体的例子：它不仅有助于澄清一些混淆，而且当你得到实际代码时，它们可以作为健全的测试用例。

您在(fraction-product 1)和(fraction-product 2)之间手动计算的答案之间是否存在关系？在(fraction-product 2)和(fraction-product 3)之间怎么样？

我们需要担心(fraction-product 0)吗？检查您的问题陈述。

当你看到这样的问题时，不要直接去编码。先用手做小例子：计算答案应该是什么。它将帮助您开始对程序真正尝试计算的内容以及如何机械地进行计算的直觉。

如果您有时间，请参阅《如何设计程序》之类的书，其中描述了设计此类功能的系统方法。

Answer 2

你错了基本情况：它应该说明 if kis 1，然后返回1- 当你递归乘法时，你必须确保在1达到数字时递归停止，如果你乘以0结果将始终是0。

递归调用也是错误的，注意你必须乘以(- 1 (/ 1 k))递归的结果。尝试这样的事情：

(define (fraction-product k)
  (if (<= k 1)
      1
      (* (- 1 (/ 1 k))
         (fraction-product (- k 1)))))

正如@Axioplase 的回答所建议的那样，可以通过使用尾递归来使用恒定堆栈空间来编写相同的过程 - 递归调用是过程在返回之前执行的最后一件事，因此处于尾部位置：

(define (fraction-product k)
  (let loop ((acc 1)
             (k k))
    (if (<= k 1)
        acc
        (loop (* acc (- 1 (/ 1 k))) (- k 1)))))

只是为了好玩，很容易意识到同样的过程可以写得像这样简单：

(define (fraction-product k)
  (/ 1 k))

Answer 3

产品的论据是什么？只有一个！因此，该产品是无用的，因为(* n) == (* n 1) == n. 这应该立即告诉您您的算法没有按照您的意愿行事。

找到此类错误的一个好策略是将函数的所有参数写成单独的行……</p>

此外，当k == 0,(fraction-product 0)返回 0。然后(fraction-product 1)将计算(/ 1 (fraction-product 0)) == (/ 1 0)可能不是您想要再次执行的操作...</p>

实际上，您似乎想要计算与分数乘积完全不同的东西……而是递归分数（我忘记了这些东西的名称）。

无论如何，(1 - 1/2) * (1 - 1/3) * ... * (1 - 1/k)你可以做类似的事情

(define (f-p k)
  (define (aux n) (- 1 (/ 1 n)))
  (let loop ((i 2))
    (if (> i k)
      1 ;; base case: multiply by 1, i.e. "do nothing"
      (* (aux i) (loop (+ i 1))))))

这可以优化为使用常量堆栈空间，但这不是重点，是吗？