Всегда ли оптимизирована рекурсивная функция в Scheme?

Question

Я прочитал кое-что об оптимизации хвостового вызова в Схеме.Но я не уверен, понимаю ли я концепцию хвостовых вызовов.Если у меня есть такой код:

(define (fac n)
  (if (= n 0)
      1
      (* n (fac (- n 1)))))

, можно ли это оптимизировать, чтобы он не занимал стековую память?или можно применить оптимизацию хвостового вызова только к такой функции:

(define (factorial n)
    (let fact ([i n] [acc 1])
      (if (zero? i)
          acc
          (fact (- i 1) (* acc i)))))

Answer 1

Полезный способ думать о хвостовых вызовах - это спросить «что должно произойти с результатом рекурсивного вызова процедуры?»

Первая функция не может быть оптимизирована хвостом, потому что результат *Необходимо использовать 1004 * внутреннего вызова fac и умножить на n, чтобы получить результат общего вызова fac.

Во втором случае, однако, результат'внешний' вызов fact является ... результатом внутреннего вызова fact.Больше ничего с этим не нужно делать, и последнее значение может быть просто передано обратно непосредственно как значение функции.Это означает, что никакой другой контекст функции не должен быть сохранен, поэтому его можно просто отбросить.

Стандарт R5RS определяет «хвостовой вызов», используя понятие хвостовой контекст , которыйпо сути то, что я описал выше.

Answer 2

Нет, первое fac не может быть оптимизировано.

Когда вызывается функция, вам нужно знать место, из которого она была вызвана, чтобы вы могли вернуться в это место после завершения вызова и использовать результат вызова в будущих вычислениях (a fac функция).

fact реализовано по-разному.Последнее, что делает fact, это называет себя.Нет необходимости запоминать место, из которого мы звоним, - вместо этого мы можем выполнить устранение хвостовых вызовов.Других действий, которые следует выполнить после возврата fact, нет.