Сумма всех целых чисел от a до b, что не так с моим кодом?

Question

Цель состоит в том, чтобы создать код, который будет вычислять сумму всех целых чисел от a до b, и если a > b, то он должен иметь значение 0.

(define (sum-from-to a b)
  (if (> a b)
      0
      (+ a (sum-from-to (- a 1) b))))

Моя проблема в том, что когда я запускаю это, у меня заканчивается память. Что не так с моим кодом?

Answer 1

Рекурсивный шаг неверен. При условии, что a <= b исправить это так просто:

(define (sum-from-to a b)
  (if (> a b)
      0
      (+ a (sum-from-to (+ a 1) b)))) ; add 1, don't subtract

Подумай об этом, мы хотим a стать ближе к b на каждом шаге, пока он не перепрыгнет через него. Если мы уменьшаем aтогда он отойдет от b, полная противоположность того, что мы хотим. Вот почему вашей процедуре не хватает памяти, a никогда не достиг b,

Answer 2

Хорошо, вот один ответ, который даст математик: сумма всех целых чисел из a в b это половина суммы целых чисел из a в b плюс сумма всех целых чисел из b в a, А это a + b + a + 1 + b - 1 + ... + b + a который a + b + a + b + ... + a + b, И это в свою очередь (a + b) * (b - a + 1), Итоговая сумма (a + b) * (a - b + 1) / 2 следовательно. Так что просто напишите, что в Лиспе, с дополнительным условием, указанным, что для b < a:

(define (sum-a-b a b)
  (if (> a b)
      0
      (/ (* (+ a b) (+ (- b a) 1)) 2)))

Конечно, то, что, вероятно, ищется, является либо рекурсивным, либо итеративным ответом. Любой из них является ужасным решением проблемы: рекурсивный ответ ужасен как по времени, так и по сложности пространства, в то время как итеративный просто ужасен с точки зрения сложности времени.

Люди, которые учат Лисп, должны перестать активно пытаться научить людей плохо программировать.