recursion - 为什么在传递否定参数时我的代码会卡在递归调用中？

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过程应该在主过程内部，因为它不会在其他任何地方使用
• 而不是嵌套 if s，用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