stuck in Clojure recursion

Question

I am trying to write a recursive function in clojure. The function returns the greatest number of given collection. If the collection is emty then it should return nil. My code is:

(defn gum [coll]
 (if (empty? coll)
  0 
  (max (first coll)
   (gum (rest coll)))))

Expected result:

(gum [1 2 98 -3]) => 98
(gum [1 9]) => 9
(gum []) => nil

But I am getting:

(gum [1 2 98 -3]) => 98
(gum [1 9]) => 9
(gum []) => 0 (not desired result - should be `nil`)

This is because I have kept the value of (empty? coll) as 0. If I keep it as nil then (gum [1 2 98 -3]) won't work. Any suggestion as how to bring the value of (gum []) as nil and (gum [1 2 98 -3]) as 98 at the same time?

score 3 · Answer 1 · edited May 23 '17 at 11:46

I think you want something like this:

(defn gum [[head & tail]]
  (if (empty? tail)
      head
      (max head (gum tail))))

I'm using destructuring here instead of first and rest, but it's the same as:

(defn gum [coll]
  (let [head (first coll)
        tail (rest coll)]
    (if (empty? tail)
        head
        (max head (gum tail)))))

But you should try to avoid constructions like (max head (gum tail)), because Clojure can't optimize it. Try using tail recursion with recur whenever possible:

(defn gum [[head & tail]]
  (if (empty? tail)
      head
      (recur (cons (max head (first tail))
                   (rest tail)))))

recur allows Clojure to use Tail Call Optimization to convert your recursive call into an iterative one, allowing it to be run in a constant stack space. It not only makes your code faster, but also protects it from stack overflow.

You should also consider using Higher Order Functions instead of recursion (as SaltyEgg suggested):

(defn gum [coll]
  (if-let [s (seq coll)]
    (reduce max s)))

In most cases they provide an easier solution. And they are pretty good optimized.

score 1 · Answer 2 · answered Oct 24 '13 at 09:50

1

Try this:

(defn gum [coll]
 (if (empty? coll)
  nil 
  (reduce max coll)))

answered Oct 24 '13 at 09:50

SaltyEgg

1,498
1
15
26

@user227666 If you want recursion, add a condition `(= 1 (count coll))` when returns the only element. – SaltyEgg Oct 24 '13 at 09:54
I am not able to get you, can you elaborate? – user227666 Oct 24 '13 at 10:48

score 0 · Answer 3 · answered Nov 30 '14 at 16:04

Looks like you are trying to redefine the max function ?

Now if you are looking to understand how the max function works, it ususally a good idea to look at the source (source max) in a repl :

(defn max
  "Returns the greatest of the nums."
  {:added "1.0"
   :inline-arities >1?
   :inline (nary-inline 'max)}
  ([x] x)
  ([x y] (. clojure.lang.Numbers (max x y)))
  ([x y & more]
   (reduce1 max (max x y) more)))

Note that (apply max []) will throw an exception rather than returning nil : ArityException Wrong number of args (0) passed to: core/max clojure.lang.AFn.throwArity (AFn.java:429)

Edit : That's why the approach to check first if we want to apply max and then (maybe) apply, as suggested by other answers :

(defn gum [coll]
  (if-let [s (seq coll)]
    (reduce max s)))

score 0 · Answer 4 · answered Mar 18 '17 at 13:18

0

You should not call the same function inside because Clojure does not have tail recursion optimization (TRO). Use (recur arg1 arg2 etc) to iterate on the next step. And don't forget to add an if statement to leave the recursion.

answered Mar 18 '17 at 13:18

Ivan Grishaev

1,583
10
15

a.k · Answer 5 · 2019-12-18T16:32:39.823

0

This would work, using same logic as you have described, returning singleton elements instead of zero:

(defn gum [coll]
  (if (or (empty? coll) 
          (singleton? coll))
    (first coll)
    (max (first coll) (gum (rest coll)))))

with:

(defn singleton? [coll]
  (if (first coll) (empty? (rest coll)) false))

edited Dec 18 '19 at 16:32

answered Dec 17 '19 at 09:55

a.k

1,035
10
27

stuck in Clojure recursion

5 Answers5