Почему мой код застревает в рекурсивном вызове, когда передается отрицательный аргумент? - PullRequest
Новая
       24

Почему мой код застревает в рекурсивном вызове, когда передается отрицательный аргумент?

0 голосов
/ 13 апреля 2019

Я пытаюсь реализовать в Scheme рекурсивную процедуру, которая принимает квадрат числа без умножения, используя формулу n ^ 2 = 1 + 3 + 5 + ... + (n + n-1). Оператор if (

Когда вызывается (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))))))

1 Ответ

2 голосов
/ 14 апреля 2019

Проблема в том, что процедура застревает во втором if, никогда не достигая базового случая из-за того, как структурированы ваши условия. Мы должны разбить задачу на две части: одну процедуру для проверки случаев, когда n <= 0, и другую для выполнения цикла в общем случае.

Помните, что в процедуре Scheme только результат последнего выражения получает возвращенного - другие выражения выполняются точно, но их результаты игнорируются. В случае выражения if структурируйте его так, чтобы оно всегда имело часть «else». Сказав это, это должно работать: 

(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 с лучше использовать cond
  • Мы могли бы использовать существующие процедуры для общей задачи, такие как zero?, positive?, sub1
  • Для эффективности мы должны использовать хвостовую рекурсию , когда это возможно

Вот как может выглядеть более идиоматический ответ, он работает так же, как и первый: 

(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
...