当负参数传递时，为什么我的代码卡在递归调用中？

Question

我试图在Scheme中实现一个递归过程，它采用数字的平方而不使用乘法，使用公式n ^ 2 = 1 + 3 + 5 + ... +（n + n-1）。如果负数是参数，则if（<n 0）语句。我知道我可以很容易地使用abs，但我想尝试编码而不用abs。

当调用（Square1 2）时，它返回正确的值，但是当我调用（Square1 -2）时，它会被卡在递归调用中。

我想我设法将它缩小到Square1（+ n -1）是造成问题的原因，但我不确定为什么这会导致问题。我尝试使用Java中的相同逻辑对此进行编程，看起来我的逻辑是正确的。这是我的第一个功能语言，所以可能有一些我不理解的东西。

(define Square1
  (lambda (n)
    (if (= n 0) 
        0)
    (if (< n 0)
        (Square1 (* -1 n)))
    (if (= n 1)
        1
        (+ (+ (+ n n) -1) (Square1 (+ n -1))))))

Answer 1

问题是程序陷入第二个if，由于你的条件结构的方式，从未达到基本情况。我们应该将问题分成两部分：一个用于检查n <= 0时的情况，另一个用于在一般情况下执行循环。

请注意，在Scheme过程中，只返回最后一个表达式的结果 - 其他表达式肯定会执行，但会忽略它们的结果。在if表达式的情况下，构造它以便它总是具有“其他”部分。话虽如此，这应该工作：

(define (aux n)
  (if (= n 1)
      1
      (+ (+ (+ n n) -1)
         (aux (+ n -1)))))

(define (square1 n)
  (if (= n 0)
      0
      (if (> n 0)
          (aux n)
          (aux (- n)))))

上面的解决方案是正确的，但不是那个惯用的。我们可以做得更好！

• aux程序应该是主程序的内部程序，因为它不会在其他任何地方使用
• 而不是嵌套ifs，使用cond更好
• 我们可以使用现有的常规任务程序，如zero?，positive?，sub1
• 为了提高效率，我们应尽可能使用tail recursion

这是一个更惯用的答案可能看起来如何，它与第一个相同：

(define (square1 n)
  (define (aux n acc)
    (if (= n 1)
        acc
        (aux (sub1 n) (+ acc (sub1 (+ n n))))))
  (cond ((zero? n) 0)
        ((positive? n) (aux n 1))
        (else (aux (- n) 1))))

无论哪种方式，它都按预期工作：

(square1 -4)
=> 16
(square1 -3)
=> 9
(square1 -2)
=> 4
(square1 -1)
=> 1
(square1  0)
=> 0
(square1  1)
=> 1
(square1  2)
=> 4
(square1  3)
=> 9
(square1  4)
=> 16