Почему рекурсивные вызовы не заменяются автоматически на рекурсивные?

Question

В следующем (Clojure) ТАКОМ вопросе: моя собственная функция вставки в качестве упражнения

Принятые ответы говорят об этом:

Замените ваш рекурсивный вызов на вызов для повторения, потому что, как написано попадет в стек переполнения

(defn foo [stuff]
  (dostuff ... )
  (foo (rest stuff)))

становится:

(defn foo [stuff]
  (dostuff ...)
  (recur (rest stuff)))

чтобы не дуть в стек.

Это может быть глупый вопрос, но мне интересно, почему рекурсивный вызов foo не заменяется автоматически на recur ?

Кроме того, я взял еще один пример SO и написал это (без использования cond специально, просто чтобы попробовать):

(defn is-member [elem ilist]
  (if (empty? ilist)
    false
    (if (= elem (first ilist))
      true
      (is-member elem (rest ilist)))))

И мне было интересно, должен ли я заменить вызов is-member на recur (который также, кажется, работает) или нет.

Есть ли случаи, когда вы делаете рекурсию и, в частности, не должны использовать recur ?

Answer 1

Нет почти никакой причины , а не , чтобы использовать recur, если у вас есть хвостовой рекурсивный метод, хотя, если вы не находитесь в области кода, чувствительной к производительности, это просто не даст никаких результатов.Разница.

Я думаю, что основной аргумент состоит в том, что наличие recur явного делает очень ясным, является ли функция хвостовой рекурсивной или нет;все хвостовые рекурсивные функции используют recur, и все функции, которые recur являются хвостовыми рекурсивными (компилятор будет жаловаться, если вы попытаетесь использовать recur из не-хвостовой позиции.) Так что это немного эстетичнорешение.

recur также помогает отличить Clojure от языков, которые будут выполнять TCO при всех вызовах хвоста, таких как Scheme;Clojure не может сделать это эффективно, потому что его функции скомпилированы как функции Java, а JVM не поддерживает его.Делая recur особым случаем, мы надеемся, что нет завышенных ожиданий.

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

Answer 2

Я спросил Рича Хики, и его рассуждения были в основном (и я перефразировал)

"чтобы особые случаи выглядели особенными"

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

Answer 3

Мне было интересно, должен ли я заменить вызов is-member на recur

В общем, как говорит mquander, нет причин не использовать recur, когда это возможно. При небольших входах (от нескольких десятков до нескольких сотен элементов) они одинаковы, но версия без повторения будет взорвана при больших входах (несколько тысяч элементов).

Явная рекурсия (т. Е. Без 'recur') хороша для многих вещей, но повторение длинных последовательностей не является одним из них.

Есть ли случаи, когда вам не следует использовать recur?

Только когда вы не можете использовать его, когда

• это не хвостовая рекурсия - то есть он хочет что-то сделать с возвращаемым значением.
• рекурсия для другой функции.

Некоторые примеры:

 (defn foo [coll] 
  (when coll 
    (println (first coll))
    (recur (next coll)))   ;; OK: Tail recursive

(defn fie [coll]
  (when coll
    (cons (first coll)       
      (fie (next coll))))) ;; Can't use recur: Not tail recursive.   

(defn fum 
  ([coll] 
    (fum coll []))         ;; Can't use recur: Different function.
  ([coll acc] 
    (if (empty? coll) acc
       (recur (next coll)  ;; OK: Tail recursive
          (conj acc (first coll)))))) 

Относительно того, почему recur не вставляется автоматически, когда это уместно: я не знаю, но по крайней мере один положительный побочный эффект состоит в том, чтобы фактические вызовы функций визуально отличались от не-вызовов (то есть recur).

Так как это может быть различием между «работами» и «взрывами с помощью StackOverflowError», я думаю, что это справедливый выбор дизайна - сделать его явным - видимым в коде - а не неявным, с которого вам придется начинать второй - угадать компилятор, когда он не работает, как ожидалось.