сумма всех целых чисел от 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 равна половине суммы целых чисел от 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)))

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

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

Answer 2

Рекурсивный шаг неверен.Предполагая, что 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.