Как исправить рекурсивный поиск по списку

Question

Я сейчас пытаюсь выучить Clojure.Но у меня возникли проблемы при создании функции, которая рекурсивно просматривает каждый элемент списка и возвращает число «a», присутствующего в списке.

Я уже понял, как сделать это итеративно, но у меня возникают проблемы при рекурсивном выполнении.Я попытался изменить "seq" на "пусто?"но это тоже не сработало.

---

(defn recursive-a [& lst]
 (if (seq lst)
     (if (= (first lst) "a")
         (+ 1 (recursive-a (pop (lst))))
         (+ 0 (recursive-a (pop (lst)))))
     0))

Answer 1

Добро пожаловать в сообщество переполнения стека.

Ваш код в порядке, за исключением того, что вы допустили несколько мелких ошибок.

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

Вторым моментом является синтаксический параметр &. Вы не хотите использовать это, пока не будете уверены, как это повлияет на ваш код.

С этими изменениями код выглядит следующим образом:

  (defn recursive-a [lst]
 (if (seq lst)
     (if (= (first lst) "a")
         (+ 1 (recursive-a (pop lst)))
         (+ 0 (recursive-a (pop lst))))
     0))


(recursive-a (list "a" "b" "c"))

Вы можете запустить его в веб-среде: https://repl.it/languages/clojure

Answer 2

В духе обучения:

Вы можете использовать & или нет.Оба в порядке.Разница заключается в том, как бы вы тогда вызывали свою функцию, и вам нужно было бы не забывать использовать apply при повторении.

Также просто используйте first и rest.Они оба безопасны и будут работать как с нулевым, так и с пустым списками, возвращая ноль и пустой список соответственно:

(first [])  ;; -> nil
(first nil) ;; -> nil
(rest [])   ;; -> ()
(rest nil)  ;; -> ()

Итак, вот как я бы переработал вашу идею:

;; With '&'
(defn count-a [& lst]
  (if-let [a (first lst)]
    (+ (if (= a "a") 1 0)
       (apply count-a (rest lst)))  ;; use 'apply' here
    0))
;; call with variable args, *not* a list
(count-a "a" "b" "a" "c") 

;; Without '&'
(defn count-a [lst]
  (if-let [a (first lst)]
    (+ (if (= a "a") 1 0)
       (count-a (rest lst)))
    0))
;; call with a single arg: a vector (could be a list or other )
(count-a ["a" "b" "a" "c"])  

Однако это небезопасно, потому что они не используют хвостовую рекурсию, и поэтому, если ваш список большой, вы взорвете свой стек!

Итак, мы используем recur.Но если вы не хотите определять дополнительную «вспомогательную» функцию, вы можете вместо этого использовать loop в качестве «повторяющейся» цели:

;; With '&'
(defn count-a [& lst]
  (loop [c 0  lst lst] ;; 'recur' will loop back to this point
    (if-let [a (first lst)]
      (recur (if (= a "a") (inc c) c) (rest lst))
      c)))
(count-a "a" "b" "a" "c")

;; Without '&'
(defn count-a [lst]
  (loop [c 0  lst lst]
    (if-let [a (first lst)]
      (recur (if (= a "a") (inc c) c) (rest lst))
      c)))
(count-a ["a" "b" "a" "c"])

Все это, как я сказал, тожебудет использовать:

;; With '&'
(defn count-a [& lst]
  (count (filter #(= % "a") lst)))
(count-a "a" "b" "a" "c")

;; Without '&'
(defn count-a [lst]
  (count (filter #(= % "a") lst)))
(count-a ["a" "b" "a" "c"])

Answer 3

Добро пожаловать в переполнение стека.

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

Один из классических методов Lisp-y для обработки таких ситуаций, как, например, это предоставление второй реализации функции, которая передает счетчик выполнения в качестве входного аргумента в«внутренняя» функция:

(defn recursive-a-inner [cnt lst]
  (cond
    (seq lst) (cond
                (= (first lst) "a") (recur (inc cnt) (rest lst))
                :else               (recur cnt (rest lst)))
    :else cnt))

(defn recursive-a [& lst]
  (recursive-a-inner 0 lst))

Делая это, «внутренняя» версия позволяет толкнуть рекурсию в хвостовую позицию, чтобы можно было использовать ключевое слово Clojure recur.Это не такая чистая реализация, как оригинал, но у нее есть преимущество в том, что она не взорвет стек.

Еще один способ справиться с этим - использовать Clojure loop -ing, который позволяет рекурсию внутритело функции.Результат во многом совпадает с приведенной выше «внутренней» функцией:

(defn recursive-a [& lp]
  (loop [cnt  0
         lst  lp]
    (cond
      (seq lst) (cond
                  (= (first lst) "a") (recur (inc cnt) (rest lst))
                  :else               (recur cnt (rest lst)))
      :else cnt)))

И если мы отбросим требование явной рекурсии, мы можем сделать это немного проще:

(defn not-recursive-a [& lst]
  (apply + (map #(if (= % "a") 1 0) lst)))

Bestудачи.