scheme - 在 Scheme 中编写递归过程。（减半 ab）

Question

对从 a 到 b 的整数求和的一种方法是将区间分成两半，递归地将两半相加，然后将两个和相加。如果区间有奇数个整数，则尽可能将其分成两半。您可以使用该floor函数返回小于某个实际值的最大整数。

(define sum-by-halves (lambda (a b) your_code_here))

有没有人有解决这个问题的想法？

Answer 1

如果您要递归解决问题，那么您需要 i) 确定停止条件，ii) 弄清楚如何将较大的问题分解为相同但较小的问题。你已经有了'ii'（除了细节）。“我”会是什么？

停止条件将是当两个数字“a”和“b”相同时。所以，你的出发点是：

(define (sum-by-halves a b)
  (if (= a b)
      a
      ...))

对于“...”，您需要在“a”和“b”之间的“c”。

(define (sum-by-halves a b)
  (if (= a b)
      a
      (let ((c (div (+ a b) 2)))
        (+ (sum-by-halves a c)
           (sum-by-halves (+ c 1) b)))))

通过选择div，我确保c始终是整数，并且是一半或比一半少一。因此(+ c 1)不会超过b。注意：代码假定(<= a b).